The Canteen Queue That Says Full With 39 Orders Waiting
A school canteen introduces a token queue. Orders are kept in an array queue[100] with front = 0 and rear = 0. Enqueue does rear = rear + 1; queue[rear] = order; and dequeue does front = front + 1; return queue[front];. During the first hour, 99 orders are accepted and 60 are served; the program then reports “queue full” even though only 39 orders are actually waiting. Restarting the program clears the queue and lets it accept more orders, but the waiting orders are lost. The canteen also wants a “cancel last served order” feature and proposes using the same array for it. The computer teacher says the queue is a linear queue, not a circular queue, and that the cancel feature needs a different structure. You must analyse the symptoms, calculate the effective capacity, and recommend a fix.
1. Calculate `front`, `rear`, and the number of waiting orders. Explain why the program reports full despite free slots.
Read the worked answer
With 99 enqueues, rear = 99; with 60 dequeues, front = 60. The number waiting is rear − front = 99 − 60 = 39, not 99. The full test is probably rear == 99 before inserting, so the queue refuses a new order even though slots 0–59 are free. Those slots can never be reused because front and rear only increase. Restarting resets both to 0, which is why it appears to work but loses the 39 waiting orders. The array of 100 therefore has an effective usable capacity of only 99 orders over the program’s lifetime, not 99 simultaneous orders. This is the classic wasted-space problem of a linear queue.
2. Rewrite enqueue and dequeue as a circular queue using modulo arithmetic. State the full and empty conditions and the maximum number of orders held at once.
Read the worked answer
Use a circular queue with front as the index of the first element and rear as the index of the next free slot; leave one slot empty to distinguish full from empty.
#define N 100
int queue[N], front = 0, rear = 0;
int is_empty(void) { return front == rear; }
int is_full(void) { return (rear + 1) % N == front; }
void enqueue(int x) {
if (is_full()) { /* handle overflow */ return; }
queue[rear] = x;
rear = (rear + 1) % N;
}
int dequeue(void) {
if (is_empty()) { /* handle underflow */ return -1; }
int x = queue[front];
front = (front + 1) % N;
return x;
}
This holds at most 99 orders at once because one slot is reserved, but it reuses slots indefinitely. Alternatively keep a count variable and allow all 100 slots; then update count on every enqueue and dequeue. For the canteen, 99 simultaneous pending orders is ample; the key change is wraparound.
3. The canteen wants a “cancel last served order” feature. Explain why a stack is appropriate and why the queue array should not be reused for it.
Read the worked answer
Cancel-last-served is LIFO, so it needs a stack of served orders, not the FIFO queue. When an order is dequeued for serving, push its token onto a served_stack. “Cancel last served” pops the most recent token and can reinsert it at the front of the queue or mark it cancelled. If the same array were used as a stack while also holding the queue, the two structures would overwrite each other and destroy the queue order. Use a separate stack array with its own top, or a linked stack. A queue is for normal first-come-first-served waiting; a stack is for undo of the most recent action. If cancellations are frequent, a linked list for the served stack avoids a fixed-size overflow.