Both of these hold a collection of waiting things. They differ by one question: which one comes out next?
A stack: newest first#
A stack is a pile of plates. You add to the top, and you take from the top. The last thing in is the first thing out, which is why it is called LIFO.
Two operations, both O(1):
- push: put a value on the top
- pop: take the top value off
Plus a peek, which looks at the top without removing it.
A stack is usually just an array where you only ever touch the end. Adding at the end is cheap and removing from the end is cheap, so an array is a perfect fit and no linked list is needed.
push 3 push 7 push 1 pop pop
[3] [3,7] [3,7,1] [3,7] [3]
^ out: 1 ^ out: 7
A queue: oldest first#
A queue is the line at a shop. You join at the back, and you are served from the front. First in, first out, or FIFO.
- enqueue: add at the back
- dequeue: remove from the front
Here an array is a poor fit. Removing from the front of an array shuffles everything else along, which is O(n) every single time.
Two ways round it:
A linked list, holding a reference to both the head and the tail. Add at the tail, remove from the head, both O(1).
A circular buffer, which is an array plus two indexes marking where the queue starts and ends. Instead of shuffling, the indexes move, and they wrap round to 0 when they run off the end. This is what most standard libraries actually use, because it keeps the values next to each other in memory.
[ _ , b , c , d , _ ]
^front ^back
Why you should care which one you picked#
The choice decides what order your algorithm explores things in, and that changes the answer, not just the speed.
Walking a graph with a stack goes deep: it follows one path as far as it can before backing up. That is depth first search.
Walking the same graph with a queue goes wide: it visits everything one step away, then everything two steps away. That is breadth first search, and because it finishes each distance before starting the next, it finds the shortest path in a graph with equal step costs.
Same code. One line different. Completely different guarantee.
The stack you did not write#
Every time your program calls a function, the computer pushes a frame onto a stack: where to return to, and the local variables. When the function returns, the frame is popped.
That is why infinite recursion produces a stack overflow: frames pile up and never get popped. It is also why any recursive solution can be rewritten with a stack you manage yourself, which is the usual fix when the recursion gets too deep.
When each one turns up#
Stacks: matching brackets, undo history, evaluating expressions, depth first search, and the whole family of "next greater element" problems where the stack holds items still waiting for their answer.
Queues: breadth first search, shortest paths in unweighted graphs, task scheduling, buffering between a fast producer and a slow consumer, and sliding window problems where things leave from the far end.
Common mistakes#
- Popping without checking whether the structure is empty.
- Building a queue on a plain array and removing from the front, turning an
O(n)algorithm intoO(n squared)without noticing. - Using a stack for a shortest path problem. It will find a path, and it will not be the shortest.
- Forgetting that a circular buffer full and a circular buffer empty can look identical unless you track the count.