1.3Queues, deques and circular queues
The idea
A queue is first in, first out. A circular array queue reuses space with index arithmetic mod n.
Think of it like this: A line at a ticket counter: the person who arrived first is served first.
Why it exists
Queues drive BFS and scheduling, and the full/empty ambiguity of a circular queue is a classic question.
How it works
- Enqueue: rear = (rear + 1) mod n, store the item.
- Dequeue: read at front, front = (front + 1) mod n.
- With only two pointers, full and empty look the same.
- Fix by counting items, or by keeping one slot empty (capacity n − 1).
Worked example: Capacity-5 circular queue
Enqueue 5 items without dequeuing: front = 0 and rear = 4, the queue is full. Dequeue once, enqueue once: rear wraps to 0.
Now play with it
- →Fill the queue completely, then try one more.
- →Dequeue and enqueue to see rear wrap around.
With only front and rear, "full" and "empty" look the same (front = rear + 1 mod n). Fixes: keep a count, or sacrifice one slot (then capacity is n − 1).
Check yourself
With the one-empty-slot rule, a circular array of size n holds at most
Exam notes (the dense version)
A queue is FIFO: enqueue at the rear, dequeue at the front, both O(1). In an array of size n, a circular queue uses (rear + 1) mod n to reuse freed slots. With only front and rear pointers, full and empty look alike, so keep a count or leave one slot unused. A deque allows insertion and deletion at both ends. Two stacks can simulate a queue (amortised O(1)); two queues can simulate a stack.
Previous year questions: Arrays, Stacks, Queues & Linked Lists (14)
PYQs are grouped by topic, so this is the full set for Arrays, Stacks, Queues & Linked Lists; try the ones that match this subtopic. Open all 14 on the topic page.