- 2073 Bhadra · 5 marks
Circular queue vs linear queue
Short answer
Linear queue does not reuse freed front cells; circular queue wraps rear modulo N. Example: N=5, insert 10,20,30,40,50, delete two, insert 60 — linear overflows despite free space; circular succeeds, rear wraps to 0.
Explain how a circular queue differs from a linear queue with suitable example.
A linear queue uses an array in a straight line: rear only moves forward and positions before front are never reused. A circular queue joins the last position to the first, so indices wrap around with (index + 1) % N.
| Linear queue | Circular queue |
|---|---|
rear increases up to N − 1 and stops | rear wraps to 0 using (rear + 1) % N |
| Freed cells at the front are not reused | Freed cells are reused |
Full test: rear == N - 1 | Full test: (rear + 1) % N == front |
Empty test: front > rear | Empty test: front == -1 |
| Can report overflow even when cells are free | Overflows only when all cells are used |
| Simple to implement | Slightly more complex |
| Poor memory use | Better memory use |
Example (N = 5): insert 10, 20, 30, 40, 50, delete two, insert 60
Linear queue
| Operation | Array contents (index 0 → N-1) | front | rear |
|---|---|---|---|
| enqueue(10) | 10 _ _ _ _ | 0 | 0 |
| enqueue(20) | 10 20 _ _ _ | 0 | 1 |
| enqueue(30) | 10 20 30 _ _ | 0 | 2 |
| enqueue(40) | 10 20 30 40 _ | 0 | 3 |
| enqueue(50) | 10 20 30 40 50 | 0 | 4 |
| dequeue() returns 10 | _ 20 30 40 50 | 1 | 4 |
| dequeue() returns 20 | _ _ 30 40 50 | 2 | 4 |
| enqueue(60): rear = 4 → Queue overflow | _ _ 30 40 50 | 2 | 4 |
Two cells are free, yet enqueue(60) fails.
Circular queue
| Operation | Array contents (index 0 → N-1) | front | rear |
|---|---|---|---|
| enqueue(10) | 10 _ _ _ _ | 0 | 0 |
| enqueue(20) | 10 20 _ _ _ | 0 | 1 |
| enqueue(30) | 10 20 30 _ _ | 0 | 2 |
| enqueue(40) | 10 20 30 40 _ | 0 | 3 |
| enqueue(50) | 10 20 30 40 50 | 0 | 4 |
| dequeue() returns 10 | _ 20 30 40 50 | 1 | 4 |
| dequeue() returns 20 | _ _ 30 40 50 | 2 | 4 |
| enqueue(60) | 60 _ 30 40 50 | 2 | 0 |
Here rear wraps to index 0 and 60 is stored.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Linear and circular queue operations · Data Structure and Algorithm, chapter 2
- Enqueue and dequeue in circular queue · Data Structure and Algorithm, chapter 2 · asked 2×
- Circular queue with display operation · Data Structure and Algorithm, chapter 2
- Circular queue algorithm with conditions · Data Structure and Algorithm, chapter 2
- Circular queue using linked list · Data Structure and Algorithm, chapter 4
- Linear queue using array · Data Structure and Algorithm, chapter 2 · asked 2×
- Linear convolution via circular convolution · Digital Signal Analysis and Processing, chapter 7
- Double refraction, linear and circular light · Engineering Physics, chapter 4
- TE vs TM mode in circular waveguide · RF and Microwave Engineering, chapter 4
- Angular vs linear precision in traversing · Surveying II, chapter 1 · asked 2×