Past exam question: 2066 Bhadra (Regular / Back), Q3(a)
Open in the Padhaiko appQuestion
Can you always insert an item into an empty queue? Explain with possible reasons and example?
Solution
No — Not in a Naive Array-Based Linear Queue: In a standard array-based linear queue of size MAX using front = 0, rear = -1 (without circular wrap-around or resetting indices when empty), an item cannot be inserted even when the queue is logically empty if rear == MAX - 1.
Reason:
enqueueincrementsrear(rear++) and checksisFull()viarear == MAX - 1.dequeueincrementsfront(front++). Once allMAXitems have been enqueued and then dequeued,front == MAXandrear == MAX - 1.- At this point, the queue contains 0 items (empty), yet
rear == MAX - 1triggers Queue Overflow!
Example (MAX = 3):
- Enqueue
A, B, Cfront = 0, rear = 2. - Dequeue
A, B, Cfront = 3, rear = 2(queue is now empty!). - Attempt
enqueue(D):rear == 2 == MAX - 1Overflow, refusing insertion into an empty queue! (Resolved by resettingfront = rear = -1when empty, or using a circular queue.)
Answer:
No. In a linear array queue without wrap-around or empty-state reset, enqueuing MAX items and then dequeuing them all leaves the queue empty (front > rear) while rear == MAX - 1, triggering false overflow until a circular queue or index reset is used.