Past exam question: 2078 Baishakh (Back), Q3
Open in the Padhaiko appQuestion
What are the problems with linear queue? Explain different queue operations in circular queue.
Solution
Problems with Linear Queue (Array Implementation):
- False Overflow / Wasted Memory: Once
rearreachesMAX - 1, no more insertions are allowed (rear == MAX - 1) even if earlierdequeue()calls have freed slots at0..front-1. - Costly Shifting Workaround: Shifting all elements toward index
0on every dequeue turns operations into .
Circular Queue Operations (Ring Buffer of Size MAX): Initially front = -1, rear = -1.
isEmpty(): Returns true whenfront == -1.isFull(): Returns true when(rear + 1) % MAX == front.enqueue(x):- Check
isFull(). If full, report overflow. - If empty (
front == -1), setfront = 0, rear = 0; else setrear = (rear + 1) % MAX. - Store
Q[rear] = x.
- Check
dequeue():- Check
isEmpty(). If empty, report underflow. - Save
val = Q[front]. - If
front == rear(last item removed), resetfront = rear = -1; else setfront = (front + 1) % MAX. - Return
val.
- Check
display(): Start ati = frontand advancei = (i + 1) % MAXuntili == rear.
Answer:
A linear queue suffers from false overflow (unusable freed slots before front) or shifting overhead. A circular queue wraps front and rear with (index + 1) % MAX, supporting isEmpty, isFull, enqueue, dequeue, and display in per operation with full slot reuse.