Stacks and Queues: The Structures Behind Undo Buttons and Print Queues

Imagine a stack of dishes drying by the sink. You pull the top one off to use it, even though it's not the oldest dish in the stack — pulling the bottom dish out from under the whole pile would be slow and awkward, so the top one, the most recently placed, is always the one that comes off next. That's the entire idea behind a stack as a data structure: Last In, First Out, usually abbreviated LIFO. Whatever got added most recently is the first thing to come back out.

A queue works on the opposite principle, and the everyday analogy is a checkout line: whoever got in line first gets served first, no matter how many people join behind them afterward — First In, First Out, or FIFO, also known as "first come, first served." The person who's waited longest is always next, which is exactly the opposite ordering rule from a stack's dish pile, even though both are, structurally, just an ordered list of items with rules about which end you're allowed to add to and remove from.

These two simple rules turn out to be exactly what a surprising amount of everyday software relies on. An undo button is a stack: every action you take gets pushed onto a stack of "things that happened," and pressing undo pops the most recent one off and reverses it — the most recent action is always the first one undone, which is precisely LIFO behavior. A printer's job queue is a queue: the first document sent to the printer is the first one that comes out, even if five more documents get added to the queue while the first one is still printing — FIFO, exactly like the checkout line.

A function call's "call stack" — the thing that produces a stack trace when a program crashes — is also a genuine stack, in the LIFO sense, and it's worth flagging one specific vocabulary collision here: "the stack" is also used, in a completely different but related sense, to describe a specific region of a program's memory used for storing function calls and local variables, covered in this site's "Stack vs. Heap" article. That memory-region sense and the LIFO data-structure sense described here are closely related — the memory region is called "the stack" precisely because it's managed with LIFO rules — but they're answering different questions, one about where data physically lives in memory, this one about the order items come in and out of a collection.

Recognizing which of these two simple orderings a real-world process follows is often the fastest way to pick the right structure for it in code: if the most recent thing should always be handled first, that's a stack; if the oldest waiting thing should always be handled first, that's a queue — the dish pile and the checkout line, translated directly into code.