Past exam question: 2076 Baisakh (Back), Q3
Open in the Padhaiko appQuestion
Differentiate linear queue and circular queue with suitable example.
Solution
Linear Queue vs. Circular Queue:
| Aspect | Linear Queue | Circular Queue |
|---|---|---|
| Index Progression | rear = rear + 1, front = front + 1 | rear = (rear + 1) % MAX, front = (front + 1) % MAX |
| Memory Reuse | Freed slots at 0..front-1 cannot be reused | Freed slots before front are reused via wrap-around |
| Full Condition | rear == MAX - 1 (even when front > 0) | (rear + 1) % MAX == front |
| False Overflow | Occurs frequently after enqueues and dequeues | Eliminated completely |
Illustrative Example (MAX = 4): Enqueue 10, 20, 30, 40 front=0, rear=3. Now dequeue() twice removes 10, 20 front=2, rear=3 (slots 0 and 1 are empty!).
- In a linear queue, inserting
50fails with Overflow becauserear == 3 == MAX - 1, wasting 2 empty slots. - In a circular queue,
rear = (3 + 1) % 4 = 0, placing50cleanly intoQ[0]without wasting memory.
Answer:
A linear queue stops accepting elements once rear == MAX - 1 even if earlier dequeues freed front slots (false overflow), whereas a circular queue wraps rear and front around using % MAX so freed slots are reused immediately.