Stack vs queue

Anyone who has sat through the definitions can already recite them: a stack hands back whatever went in last, a queue hands back whatever went in first. That was never the part anyone actually gets stuck on. The part that stalls is picking, for the job in front of you, which of those two orders is the correct one — and the definitions alone do not answer that. The working test is simpler than either definition: does the job have to unwind, most-recent-first, before anything underneath it can proceed? Or does it have to be fair, oldest-first, because letting a later arrival cut ahead would be the actual bug?

Unwinding versus waiting#

A stack fits any problem where the thing added most recently is also the thing that has to finish first, because everything underneath it is waiting on it. Matching brackets is the clean case: a closing bracket has to pair with the most recently opened one, not the oldest one still open, and a stack gives exactly that comparison for free. Undo history works the same way — the last change made is the first one a person expects back. So does a running program’s own call stack: a function that calls another has to wait for that call to return before it can continue, and whichever call is deepest in progress is always the next one to finish.

A queue fits the opposite shape: arrival order is the rule, and nothing later is allowed to go first just because it happened to show up on top of something. A pool of workers pulling jobs from a shared list is the obvious version — a job submitted an hour ago should not still be waiting behind one submitted a minute ago merely because the newer one landed nearer the front. Requests queued on a connection, print jobs waiting on a printer, tickets waiting on the next free agent: in each of these, being served in the order you arrived is not a nicety, it is the specification.

Both give O(1) at the end each structure actually works from — for the usual implementations. A stack backed by a dynamic array (appending and popping its last element) or by a linked list (pushing and popping at the head) does this in amortised O(1) — the complexity a community-maintained CPython complexity reference records for list.append() and list.pop(). A queue matches that only when it is actually built to work from both ends — a linked list keeping pointers to head and tail, or a ring buffer sized for the job. A plain array that only ever grows at one end and dequeues by removing its first element is not that: every removal shifts every remaining element down one slot, which the same reference records as O(n), not O(1). So the cost is genuinely equal for a queue built for the role and genuinely unequal for an array pressed into a queue’s job without the second end to match. Either way, cost is not the reason to prefer one shape over the other — the correct order is.

The jobs that pick for you#

The clearest case where the problem picks the structure for you is a search over a tree. Depth-first traversal wants a stack — an explicit one, or the call stack borrowed for free through recursion — because it has to follow one branch all the way down before backing up to try the next: finish the child before starting the sibling, which is unwinding applied to a search. Breadth-first traversal wants a queue, because it has to finish everything at the current distance from the start before moving one step further out: a node reached through an earlier neighbour has to be visited before one reached through a later neighbour, which is arrival order applied to the search itself. A look at the four ways to walk a tree makes the same point about the underlying mechanism: the depth-first orders get their bookkeeping for free from the call stack, while level order — breadth-first — has to keep its own queue of what is left to visit, in the order those nodes were found.

The everyday version of the same test needs no tree at all. An undo history is a stack, because reversing the newest change first is what “undo” means. A job queue is a queue, because a worker pool exists to serve submissions in the order they arrived, not to let a newly submitted job cut ahead of one that has been waiting. Different domain, same question — does the next thing out have to be the newest in, or the oldest in — and the answer picks the structure both times.

Python’s standard library makes the boundary between the two literal instead of conceptual. Its deque is, in the library’s own words, “a generalization of stacks and queues” — a container open at both ends, with matching O(1) appends and pops on either side. The same object becomes a stack when every push and pop stays at one end, and a queue when pushes go in one end and pops come out the other; nothing about the type changes, only which end each call uses. That is also where the previous section’s caveat lands concretely: a plain list used as a queue pays to shift every remaining element on every removal from the front, and a deque does not, because it was built to work from both ends rather than just one.

A queue where a stack belonged#

The recurring mistake runs the other direction from the one people expect: reaching for a queue when the work actually has to unwind. The shape looks reasonable at first glance — a task spawns subtasks, and all of them get pushed onto one shared work list, then pulled off and processed in the order they were pushed. That is fine as long as nothing depends on completion order. It stops being fine the moment some later step needs a task’s whole subtree finished before it can run, because arrival order and completion order are not the same thing: a parent’s siblings get pulled off the shared list and processed before the parent’s own children have finished, since the children were only just pushed and sit behind everything that arrived earlier. Any step that assumes a subtree is complete because its parent was already handled is looking at a half-finished one.

Nothing raises an error when this happens. The results are just wrong, in a way that looks like a data problem rather than an ordering one, which is what makes it hard to place. The tell is in when it shows up: the bug appears only once a task spawns deeply enough that its children queue up behind a meaningful amount of sibling work, and it vanishes the moment someone shortens the input to reproduce it, because a shallow work list never puts enough between a parent and its own children to expose the gap.

Nothing here is an argument against queues: a queue is not the wrong structure for parallel work handed to a pool of workers — it is usually the right one, and arrival-order fairness across independent jobs is exactly what a worker pool needs. The mistake is not choosing a queue; it is choosing arrival order for a job that required completion order instead, and no amount of tuning the pool fixes that, because the ordering rule itself is wrong for the dependency the code actually has.