P-4.3 Stacks and Queues
Standard restricted containers, as in Sedgewick and Wayne — written September 2026
What this is and why it exists
These are the two most restricted containers there are, and the restriction is the entire point. Allow only one place to add and one place to remove, and the implementation becomes tiny and the reasoning becomes straightforward.
They are worth knowing less as data structures than as a way of recognising a shape. Function calls, undo history, breadth-first search and job scheduling are all one or the other underneath.
Once you can see the shape, a surprising number of problems answer themselves.
The vocabulary
- Stack — add and remove at the same end. Last in, first out.
- Queue — add at one end, remove at the other. First in, first out.
- Push and pop — the stack's two operations.
- Enqueue and dequeue — the queue's two operations.
- Circular buffer — an array whose front and back positions wrap around.
- Call stack — the region holding one frame per active function call.
The mental model
A stack matches anything that nests. Function calls nest: the one you entered most recently is the one you leave first. Brackets nest. Undo history nests. Backtracking searches nest. If a problem has that shape, a stack is not a clever choice, it is the natural one.
A queue matches anything served in arrival order. Breadth-first search visits in arrival order. Every job scheduler serves in arrival order, or in some variation on it. Print jobs, message handling, task pipelines: same shape.
Both structures can sit on either foundation — an array or linked nodes — and the choice changes only the constants. Writing each one both ways is worth an afternoon. It makes something clear that is quick to say and slow to feel: the interface and the implementation are separate decisions. A stack is defined by what you may do to it, not by how it stores anything.
The circular buffer deserves its own paragraph. Building a queue over an array runs straight into a problem: removing from the front would shift everything, which is the expensive operation arrays have. The answer is to leave the data where it is and let the front and back positions wrap around the end of the array instead. That is the standard fixed-capacity queue, and it turns up everywhere in systems code, from network buffers to audio.
Finally, a connection worth making explicitly, because it ties this module to the memory one. The call stack is a stack. Every function call pushes a frame; every return removes one. That is precisely why deep recursion runs out of room — you are filling a stack of bounded size, and the limit is not arbitrary.
What you should now be able to explain or do
Implement both structures over an array and over linked nodes. Recognise a nesting problem and an arrival-order problem on sight. Say why the interface and the implementation are separate decisions. Explain what a circular buffer solves and why a queue over an array needs one. Connect the call stack to recursion depth and say why the limit exists.
Check yourself
What kind of problem has a stack shape?
Anything that nests — function calls, brackets, undo history, backtracking. The most recent thing opened is the first thing closed.
What kind of problem has a queue shape?
Anything served in arrival order — breadth-first search, job scheduling, message handling.
Why does a queue built on an array need a circular buffer?
Removing from the front of an array would shift every remaining element. Wrapping the positions around avoids the shift entirely.
What does implementing each structure twice teach you?
That the interface and the implementation are separate. A stack is defined by the operations allowed, not by how it stores things.
Why does deep recursion run out of room?
Each call pushes a frame onto the call stack, which has a bounded size. Enough nested calls fill it.
Go deeper
We haven't checked most of these for screen reader use yet.