Past exam question: 2078 Poush (Back), Q2(a)
Open in the Padhaiko appWhat is a queue? Explain circular queue as an ADT.
Solution
Definition of Queue: A queue is a linear data structure operating on the First-In, First-Out (FIFO) principle: insertions (enqueue) take place at the rear, and deletions (dequeue) take place at the front.
Circular Queue as an Abstract Data Type (ADT): A circular queue treats a fixed-capacity buffer Q[0..MAX-1] as a logical ring where index MAX - 1 wraps around to 0 via modulo arithmetic (index + 1) % MAX, eliminating false overflow in linear queues.
- Data Specification:
items[MAX]: array of elements.front: index of front item (or-1when empty).rear: index of rear item (or-1when empty).
- ADT Operations:
init(Q): setsfront = -1, rear = -1.isEmpty(Q): returnsfront == -1.isFull(Q): returns(rear + 1) % MAX == front.enqueue(Q, x): if not full, setsfront = 0(when empty), updatesrear = (rear + 1) % MAX, and storesitems[rear] = x.dequeue(Q): if not empty, readsx = items[front]; iffront == rear, resetsfront = rear = -1, else setsfront = (front + 1) % MAX; returnsx.peek(Q): returnsitems[front]without removing it.
A queue is a FIFO linear structure (enqueue at rear, dequeue at front). A circular queue ADT models a ring buffer using (index + 1) % MAX wrap-around with operations init, isEmpty, isFull ((rear+1)%MAX == front), enqueue, dequeue, and peek, achieving operations with full slot reuse.