Theory
Reusing the dead cells
Last lesson ended in an embarrassment: the token queue declared Overflow while two cells sat empty, because front and rear only ever march right.
The canteen's fix for its physical token board was beautifully simple: after token 999, the counter just starts again at 001. Nobody buys a longer board; the numbers wrap around.
One modulo operator gives your array the same superpower.
Theory
Bend the row into a ring
Picture the 5 array cells as chairs in a circle instead of a row. The rear clerk walks clockwise seating arrivals; the front clerk walks clockwise serving.
When either clerk passes the last chair, the next step lands naturally on chair 0: there is no "end" on a circle. Freed chairs come back into play the moment the clerks lap around. Dead space cannot exist on a ring.
Theory
The wrap, formally
The whole trick is replacing + 1 with modulo:
- Insert:
rear = (rear + 1) % SIZE; - Delete:
front = (front + 1) % SIZE;
With SIZE 5: after 4 comes (4+1)%5 = 0. The row is now a ring.
New tests come with it:
- Full:
(rear + 1) % SIZE == front(the next seat would crash into the front) - Empty:
front == -1
Why the odd full test? Keep reading; it is the exam's favourite part.
Practical
The ring, working
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue {
int q[SIZE];
int front, rear;
public:
CircularQueue() { front = -1; rear = -1; }
void insert(int x) {
if ((rear + 1) % SIZE == front) { cout << "Full" << endl; return; }
if (front == -1) { front = 0; rear = 0; } // first element
else rear = (rear + 1) % SIZE; // the wrap
q[rear] = x;
}
void del() {
if (front == -1) { cout << "Empty" << endl; return; }
cout << "serving " << q[front] << endl;
if (front == rear) { front = -1; rear = -1; } // served the last one
else front = (front + 1) % SIZE; // the wrap
}
void display() {
if (front == -1) return;
int i = front;
while (true) {
cout << q[i] << " ";
if (i == rear) break;
i = (i + 1) % SIZE;
}
cout << endl;
}
};
int main() {
CircularQueue c;
for (int t = 1; t <= 4; t++) c.insert(t);
c.del(); c.del(); // serves 1, 2: cells 0,1 freed
c.insert(5); c.insert(6); // 6 WRAPS into cell 0
c.display(); // 3 4 5 6
return 0;
}
Think first
Watch the wrap happen
SIZE 5, operations exactly as in main() above: insert 1..4, delete twice, insert 5, insert 6. On paper, track (front, rear) with modulo after every step. Which CELL does token 6 land in?
Show the answer
insert 1..4: front 0, rear 3. delete twice: front 2 (cells 0,1 free).
insert 5: rear (3+1)%5 = 4.
insert 6: rear (4+1)%5 = 0: token 6 lands in cell 0, the very cell the simple queue abandoned.
Final: front 2, rear 0, contents (walking the ring) 3 4 5 6. The false overflow from last lesson is simply gone.
Quiz
Why is the full test (rear + 1) % SIZE == front, deliberately wasting one slot, instead of just "rear meets front"?
- Because a completely full ring and an empty ring would both look like rear == front, so one slot is sacrificed to tell them apart
- Because modulo cannot compute the last index of an array
- Because the front clerk needs a chair to rest
- It is a mistake in most textbooks; rear == front works fine
Show the answer
Because a completely full ring and an empty ring would both look like rear == front, so one slot is sacrificed to tell them apart
On a ring, if you fill every seat, rear catches up to front: exactly the same picture as an empty queue. Ambiguity! The standard fixes: stop one seat early (this test) or keep a separate count variable. Option D is the trap: rear == front "works" until the first time your program cannot tell full from empty and serves garbage.
Watch out
The three circular slips
1. Writing rear + 1 == front without % SIZE: the wrap at the array's end silently breaks.
2. Forgetting the last-element reset: when front == rear and you delete, both must return to -1, or the queue believes one ghost element remains.
3. Displaying with an ordinary for (i = front; i <= rear...): after a wrap, rear is NUMERICALLY smaller than front, and the loop prints nothing. Walk with modulo, stop at rear.
Theory
Rings run the world
Round-robin CPU scheduling (each process gets a turn, then rejoins the ring), your keyboard's input buffer, audio/video streaming buffers, and yes, token displays: all circular queues. Any system that produces and consumes endlessly on finite memory ends up bending its array into a ring, exactly the way you just did.
Summary
Key takeaways
- Circular queue = array queue whose indexes wrap: rear = (rear + 1) % SIZE, front likewise.
- Freed cells are reused; the simple queue's false overflow disappears.
- Full: (rear + 1) % SIZE == front (one slot sacrificed); empty: front == -1.
- Deleting the last element resets front and rear to -1.
- Display must walk with modulo, never a plain front-to-rear loop.
- Applications: round-robin scheduling, keyboard and streaming buffers.
- Memory hook: bend the row into a ring.