Stacks

Think of a stack of plates in a cafeteria. Plates get added to the top. Plates get taken from the top. Nobody slides a plate out from the bottom. It’s not just awkward — the plates above it might come crashing down… and you don’t really want that to happen.. SO! the last plate placed on top of the stack is always the first one to be picked up. That’s how a stack works!

But you might think — what does that have to do with plates? It’s not like a computer program will handle how you stack plates. So here’s a more concrete example.

When you hit undo in a text editor, the last thing you typed disappears. Hit it again, the thing before that disappears. It always undoes in reverse order — the most recent action first. That’s exactly like stacking plates, the last character (or action) that is done, is the first character (or action) that is undoed.

The idea is simple.

A stack is a collection of items with one rule: the last item in is the first item out. This is called LIFO — Last In, First Out.

A stack only needs two operations to work:

Push — add an item to the top of the stack
Pop — remove the item from the top of the stack

In some implementations, a third operation is added::

Peek — look at the top item without removing it from the stack

Walking through it

Start with an empty stack. Push three values onto it one at a time.

push(10)   → [ 10 ]
push(20)   → [ 10 | 20 ]
push(30)   → [ 10 | 20 | 30 ]
                          ↑ top

Now pop twice.

pop()   → returns 30   [ 10 | 20 ]
pop()   → returns 20   [ 10 ]

Popular use of stacks

The undo example is the most intuitive, but stacks are everywhere in computing.

Function calls. When a program calls a function, it pushes the current state onto a call stack. When the function finishes, that state is popped and execution resumes where it left off. Every programming language uses this. The term “stack overflow” — which you may have heard — literally means the call stack ran out of space.

Browser history. The back button works like a stack. Each page you visit gets pushed. Hit back and the current page pops, revealing the one underneath.

Expression evaluation. When a calculator or compiler needs to evaluate something like (3 + 4) * (2 + 1), it uses a stack to track parentheses and operators in the right order.

Depth-first search. One of the core graph traversal algorithms uses a stack — explicitly or implicitly through recursion — to track which paths to explore.

In the next unit you’ll meet the stack’s counterpart: the queue — same idea, opposite order.