A circular queue is implemented using an array Q with six elements, indexed 0 to 5, and the variables front, rear and size. Initially the queue is empty with front = 0, rear = -1 and size = 0.
When an item is added, rear is updated using rear ← (rear + 1) MOD 6; when an item is removed, front ← (front + 1) MOD 6.
The following operations are carried out in order:
Enqueue(A), Enqueue(B), Enqueue(C), Enqueue(D), Dequeue, Dequeue, Enqueue(E), Enqueue(F), Enqueue(G)
(a) State the values of front, rear and size after these operations. [3]
(b) State the item stored at index 0 of the array. [1]
(c) Explain why a circular queue is a more efficient use of memory than a linear queue implemented in a fixed-size array. [1]
- (a) front = 2(1)
- (a) rear = 0(1)
- (a) size = 5(1)
- (b) G(1)
- (c) In a linear queue the spaces freed at the front by dequeuing cannot be reused (without shuffling every item forward), whereas the circular queue wraps round to reuse them(1)
- Answer: (a) front = 2, rear = 0, size = 5 (b) G (c) Freed positions at the start of the array are reused by wrapping round, with no need to shuffle items.
- Examiner tip: The MOD wrap-around is the whole point: after index 5 the next rear is 0, not 6.