Stacks & Queues: LIFO vs FIFO, Explained

Hit Ctrl+Z and the last thing you typed disappears first. Join a queue at the bank and the person who got there first gets served first. Those two everyday rules, "last in, first out" and "first in, first out," are two of the most useful data structures in computing. They're almost embarrassingly simple, and they're hiding inside undo buttons, browser back buttons, print spoolers, and the way your code actually runs.

A stack is a pile: last in, first out

Picture a stack of plates. You add a plate to the top, and when you need one, you take it off the top. The plate you put down most recently is the first one you pick up. That's LIFO, last in, first out.

A stack has exactly two operations that matter:

• push: add a value to the top.
• pop: remove and return the value from the top.

You only ever touch the top. There's no reaching into the middle, no pulling from the bottom. That restriction is the feature, not a limitation. It's what makes a stack predictable.

Watch it run. Three pushes build the pile, then a pop peels the most recent value back off:

We pushed 1, 2, 3, so the pile reads 1 at the bottom, 3 on top. The pop returns 3, the value that arrived last. 1, the oldest, sits untouched at the bottom and would be the very last thing out.

Where you've already met a stack without knowing it: the call stack. Every time a function calls another function, the new call is pushed on top. When it returns, it pops off, and control goes back to whoever called it. Undo histories work the same way. The most recent action is the first one reversed.

A queue is a line: first in, first out

A queue is the bank line. You join at the back, you get served from the front, and the order is fair: whoever waited longest goes next. That's FIFO, first in, first out, the exact opposite of a stack.

A queue's two core operations:

• enqueue: add a value to the back.
• dequeue: remove and return the value from the front.

Same idea as a stack (add and remove), but the ends are different. You add at one end and remove from the other, so things come out in the order they went in.

We enqueued 1, 2, 3. The dequeue returns 1, the one that's been waiting longest, and 2 slides to the front, next in line. Compare that to the stack above: same three values in, but the stack handed back 3 and the queue handed back 1. That one difference is the whole point.

Queues show up wherever order and fairness matter: a print spooler runs jobs in submission order, a task queue processes work as it arrives, and the breadth-first search you'll meet in the trees lesson uses a queue to visit nodes level by level.

Build both in Python

Python's built-in list already behaves like a stack: append pushes onto the end, pop() removes from the end. For a queue, you could use a list, but removing from the front of a list is slow, because every other element has to shuffle down one slot. collections.deque (a double-ended queue from the standard library) fixes that with fast removal from either end. Run this:

The stack's pop() gave back 3. The queue's popleft() gave back 1. Same three values pushed in the same order, opposite values out. (For more on lists themselves, the Python series covers the basics.)

Two rules, endless uses

Stacks and queues are tiny, two operations each, but the rule for what comes out next changes everything. A stack reverses order (LIFO): undo, the call stack, back buttons. A queue preserves order (FIFO): task processing, print jobs, fair scheduling. Pick the one whose ordering matches your problem and the rest writes itself.

Next: Linked Lists, the pointer-and-node structure that stacks and queues are often built on, and where it beats a plain array.