Past exam question: 2073 Bhadra (Regular), Q2(a)
Open in the Padhaiko appQuestion
Explain how a circular queue differ from linear queue with suitable example.
Solution
Key Differences (Circular Queue vs. Linear Queue):
- Pointer Wrap-Around: A linear queue increments
rearandfrontlinearly (+1); a circular queue wraps them moduloMAX((idx + 1) % MAX). - Memory Reuse & Overflow: A linear queue triggers false overflow once
rear == MAX - 1even if slots0..front-1were freed bydequeue(). A circular queue reuses every freed slot until allMAXslots (orMAX - 1in sentinel indexing) are full.
Example (MAX = 4): Insert 10, 20, 30, 40 (front=0, rear=3), then dequeue 10, 20 (front=2, rear=3).
- Linear Queue: Inserting
50fails (rear == 3 == MAX - 1), leaving slots0, 1unusable. - Circular Queue:
rear = (3 + 1) % 4 = 0, storing50atQ[0]cleanly.
Answer:
A circular queue wraps front and rear with (index + 1) % MAX so freed front slots are immediately reused, avoiding the false overflow of a linear queue when rear == MAX - 1.