How a Queue Actually Works
A queue serves the oldest waiting item first, which is the obvious fair policy and a surprisingly awkward thing to implement on an array. Removing from the front either shifts everything or leaves a hole, and the standard fix — wrapping the indices around — introduces an ambiguity that has its own well-known solution.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
vector<int> buf(5, 0);
int head = 0, count = 0;
for (int v = 1; v <= 4; v++) {
buf[(head + count) % 5] = v;
count++;
}
for (int i = 0; i < 2; i++) {
cout << buf[head] << ' ';
head = (head + 1) % 5;
count--;
}
buf[(head + count) % 5] = 99;
count++;
while (count > 0) {
cout << buf[head] << ' ';
head = (head + 1) % 5;
count--;
}
return 0;
}A circular buffer of capacity 5: head plus count locates the write slot, and both indices wrap with modulo so no element is ever shifted.
How it works, step by step
FIFO means two ends, not one
Items enter at the tail and leave at the head, so unlike a stack a queue must track both ends. Every implementation detail follows from that: you need two indices, or a head index plus a count.
The naive array queue is quadratic
Dequeuing by erasing element 0 shifts every remaining element left, costing O(n) per removal. Draining n items therefore costs O(n squared). Nothing about the queue abstraction requires that — it is purely an artefact of a bad layout.
Wrapping reuses the vacated space
Instead of moving elements back, move the head forward and let the tail wrap around to the freed slots. The modulo turns a linear array into a ring, so both operations become O(1) with no shifting at all.
count disambiguates full from empty
With only head and tail indices, head == tail means both empty and completely full — the ring gives no way to tell. Storing an explicit count resolves it; the alternative is to waste one slot so full and empty never coincide.
Where you meet queues
Breadth-first search, task schedulers, print spoolers, and any producer-consumer buffer. The defining property is that arrival order is the service order, which is what makes a queue explore a graph level by level rather than diving down one branch.
Complexity
Both ends are located by arithmetic rather than by scanning, so no operation depends on the number of items; the naive erase-from-front implementation is O(n) per dequeue and is the usual reason a queue-based solution runs slower than expected.
Common bugs
Using vector::erase(begin()) as dequeue
It works and is O(n), because every remaining element shifts down one slot. In a BFS over 100,000 nodes this alone turns a linear traversal into a quadratic one. Use std::queue or std::deque, or a circular buffer — the abstraction is right, the implementation is not.
head == tail meaning both full and empty
In a two-index circular buffer with no count, a full ring and an empty ring look identical. Enqueuing into a full queue then silently overwrites the oldest element, and the bug presents as mysteriously missing data much later. Track count explicitly or deliberately leave one slot unused.
Forgetting the modulo on one of the indices
It is easy to wrap head and forget the tail, or vice versa. The queue works perfectly until the first wraparound, so the failure only appears after roughly capacity operations — long after the code looked correct. Stepping through the wraparound in DryRun and watching head and tail cross the boundary is the fastest way to catch it.
Reading front() without checking empty()
Like a stack, an empty std::queue does not throw on front() or pop(); it is undefined behaviour. In a BFS this happens when the loop condition and the pop are out of sync, and it typically yields a garbage node id that indexes out of your adjacency list.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What does FIFO mean?
First In, First Out — elements leave in the same order they arrived, like people waiting in line. It is the opposite of a stack's LIFO discipline. FIFO ordering is what makes a queue-based graph traversal visit nodes in order of increasing distance from the start.
Why is a circular queue better than a normal array queue?
Because dequeuing from a plain array means either shifting every element (O(n) per removal) or abandoning the freed slots until the array is exhausted. A circular buffer advances the head index and lets the tail wrap around into the reclaimed space, making both operations O(1) with fixed memory.
How do you tell if a circular queue is full or empty?
Keep an explicit element count, or leave one slot permanently unused. Without one of these, a full ring and an empty ring both have head == tail and are indistinguishable, so the queue will happily overwrite live data. The count approach uses all capacity; the sacrificed-slot approach avoids an extra variable.
When should I use a queue instead of a stack?
When the oldest pending item should be handled first. Breadth-first search needs a queue to visit nodes in distance order; using a stack turns it into a depth-first search that finds paths but not shortest ones. Schedulers and buffers also want FIFO, because it bounds how long any single item waits.