First in, first out — add at the back, remove from the front. Swap a stack for a queue in a graph traversal and depth-first search becomes breadth-first, without changing another line.
Controls
The same traversal code, differing only in whether the pending list is a stack or a queue.
The Queue
step 0
front →
← back
DFS — stack
BFS — queue
Insight
A queue is open at both ends: you enqueue at the back and dequeue from the front. Order is preserved — fairness by construction.
Where queues are used
• Breadth-first search
• Task & job scheduling
• Printer / request queues
• Message brokers & buffers
• Rate limiting
size0
front–
back–
Complexity
Enqueue / DequeueO(1)
SearchO(n)
SpaceO(n)
Queues (FIFO)
Fair ordering by construction — and the one change that turns DFS into BFS.
Quick Context
A queue serves items in the order they arrived: FIFO, First In, First Out. You add at the back (enqueue) and remove from the front (dequeue). It is the queue at a shop, modelled exactly.
Why the Naive Implementation Is Wrong
If you implement a queue as a plain array and dequeue by removing element 0, every dequeue shifts all remaining elements down one position — that is O(n), not O(1).
Real implementations avoid this. A linked list with head and tail pointers gives O(1) at both ends. Or you keep the array and move pointers instead of data, which leads directly to the circular queue.
Circular Queues Reuse the Space
Switch to circular mode. Instead of shifting elements, two indices — front and rear — move forward and wrap around using modulo arithmetic:
Dequeue several items then enqueue more, and watch the queue wrap past the end of the array to reuse the freed slots. This is how fixed-size buffers work in networking, audio streaming and embedded systems, where allocating memory on the fly is not an option.
The Insight That Matters Most
Choose Stack vs queue traversal and step through. Both run identical code over the same graph. The only difference is where pending nodes are taken from:
Take from the end (stack, LIFO) → you dive deep down one branch first. That is depth-first search.
Take from the front (queue, FIFO) → you sweep level by level. That is breadth-first search.
One data-structure choice completely changes the traversal order — and with it, whether the algorithm finds the shortest path. BFS does; DFS does not.
Variants Worth Knowing
Deque (double-ended queue) — add and remove at both ends. Can act as either a stack or a queue.
Priority queue — serves the highest priority item rather than the oldest. Usually built on a heap, and the engine behind Dijkstra and A*.
Blocking queue — waits when empty or full. The standard tool for passing work between threads.
Interactive Exploration Guide
Enqueue A, B, C then dequeue. A comes out first — the opposite of a stack.
Switch to circular mode. Dequeue a few, enqueue a few more, and watch the indices wrap around to reuse slots instead of shifting data.
Fill the circular queue completely and try one more enqueue — it reports full, because a fixed buffer cannot grow.
Open Stack vs queue traversal and step through. Watch the two visit orders diverge from the very first branch.
Note the BFS order. It finishes each level before starting the next, which is exactly why it finds shortest paths in unweighted graphs.
Key Takeaway
A queue preserves arrival order with O(1) work at both ends, provided you move pointers rather than data. Its most important property in algorithms is level-by-level processing — swapping a stack for a queue turns depth-first search into breadth-first search and nothing else changes.
Cheat sheet
Queues (FIFO)
First in, first out — add at the back, remove from the front. Swap a stack for a queue in a graph traversal and depth-first search becomes breadth-first, without changing another line.