Theory
From token line to actual code
You know the concept from the Queue (FIFO) lesson: first token in, first served.
Now the canteen wants it running: an array of 5 token slots, an insert when a customer arrives, a delete when one is served, a display for the screen above the counter.
Everything hangs on two integers: front (who gets served next) and rear (where the newest token went). Watch them move, and watch what they leave behind.
Theory
Two clerks with pointers
Imagine two clerks at the token board:
- The rear clerk stamps each new arrival into the next empty slot, moving right.
- The front clerk serves whoever they point at, then steps right too.
Neither clerk EVER steps left. Arrivals push rear rightward, service pushes front rightward, and the gap between them is the actual waiting line.
Theory
The three operations, precisely
Array q[SIZE], with front = -1, rear = -1 (empty).
Insert (enqueue) x:
1. Full? If rear == SIZE - 1: Overflow, stop.
2. First element? If front == -1, set front = 0.
3. rear = rear + 1; q[rear] = x;
Delete (dequeue):
1. Empty? If front == -1 or front > rear: Underflow, stop.
2. Serve q[front], then front = front + 1;
Display: print q[i] for i from front to rear.
Practical
The token queue, in full
#include <iostream>
using namespace std;
#define SIZE 5
class TokenQueue {
int q[SIZE];
int front, rear;
public:
TokenQueue() { front = -1; rear = -1; }
void insert(int x) {
if (rear == SIZE - 1) { cout << "Overflow" << endl; return; }
if (front == -1) front = 0; // first ever element
q[++rear] = x;
cout << "token " << x << " joined" << endl;
}
void del() {
if (front == -1 || front > rear) { cout << "Underflow" << endl; return; }
cout << "serving token " << q[front] << endl;
front++;
}
void display() {
for (int i = front; i <= rear && front != -1; i++)
cout << q[i] << " ";
cout << endl;
}
};
int main() {
TokenQueue t;
t.insert(101); t.insert(102); t.insert(103);
t.del(); // serves 101 (FIFO)
t.display(); // 102 103
return 0;
}
Think first
Trace the two clerks
SIZE is 5. Operations: insert 1, insert 2, insert 3, delete, delete, insert 4. On paper, track front and rear after each step. Where do they end, and which array cells are now unreachable?
Show the answer
insert 1: front 0, rear 0. insert 2: rear 1. insert 3: rear 2.
delete (serves 1): front 1. delete (serves 2): front 2.
insert 4: rear 3.
End state: front = 2, rear = 3, queue holds 3 and 4.
Cells 0 and 1 are dead: both clerks are past them and neither steps left. The queue occupies 2 of 5 slots yet only 1 slot of future capacity remains. Remember this corpse trail; it becomes the exam question below.
Quiz
Continuing that trace (front=2, rear=3, SIZE=5): you insert 5, then insert 6. What happens on the second insert?
- Overflow is declared even though cells 0 and 1 sit empty
- Both succeed; the queue wraps into cell 0 automatically
- Underflow, because front never reset to 0
- The second insert overwrites token 3 at the front
Show the answer
Overflow is declared even though cells 0 and 1 sit empty
insert 5 puts rear at 4 (the last index). insert 6 then finds rear == SIZE-1 and reports Overflow, while two perfectly good cells lie dead at the start: the false overflow flaw of the simple queue. Wrapping into cell 0 (option B) is exactly what a simple queue canNOT do; that upgrade is the circular queue, next lesson.
Watch out
The conditions students scramble
Overflow check on INSERT: rear == SIZE - 1.
Underflow check on DELETE: front == -1 || front > rear.
Swapping them (checking front on insert) is the classic written-exam slip. Also do not forget the one-time if (front == -1) front = 0; on the first insert: without it, display and delete stare at index -1 forever, even though inserts "worked".
Theory
The flaw is the feature request
Every deletion strands a cell: given enough traffic, ANY simple queue drowns in its own dead space, no matter the size. Fixing it needs just one idea: let rear (and front) wrap around to index 0, turning the row into a ring. That is the circular queue, and now you know exactly why it was invented.
Summary
Key takeaways
- Simple queue on an array: front serves, rear receives; both start at -1 and only move right.
- Insert: overflow check (rear == SIZE-1), first-element fix (front = 0), then q[++rear] = x.
- Delete: underflow check (front == -1 or front > rear), serve q[front], front++.
- Display walks front to rear.
- Deleted cells become dead space: false overflow with empty cells at the start.
- That flaw motivates the circular queue's wrap-around.
- Memory hook: two clerks who never step left.