Quiz
Warm-up from the lesson 2-3 cost table: which pair of list operations is O(1), making Python lists perfect for what this lesson builds?
The stack
A stack is a collection with one rule: items enter and leave from the same end, called the top. Like a stack of plates, the last plate you put on is the first one you take off: LIFO, last in, first out.
Only two core operations exist, and both are O(1):
- push: add to the top
- pop: remove from the top
In Python you don't need a new class. A plain list IS a stack if you discipline yourself to append (push) and pop() (pop), the two cheap end operations from the warm-up.
Stacks appear anywhere you must return to the most recent unfinished thing: undo history, the browser back button, and the call stack that tracks which function called which (the reason recursion too deep gives a stack overflow).
Code exercise · python
Run this tiny undo history. Each save pushes a draft, each undo pops the most recent one. Notice draft v4 is undone before the older draft v1 is ever touched.
The classic: matching brackets
Every editor and compiler checks that ( [ { close in the right order. The insight is pure LIFO: the most recently opened bracket must close first.
So: scan the text. Push every opener. On a closer, the top of the stack must be its partner: pop it. If the top is wrong, or the stack is empty on a closer, or anything is left open at the end, the text is unbalanced.
Walk ([)] by hand: push (, push [, then ) arrives but the top is [. Mismatch, unbalanced. One O(n) pass.
Code exercise · python
Your turn: implement `balanced(text)` with a stack. Push openers. For a closer, fail if the stack is empty or its top is not the matching opener (use the `pairs` dict), otherwise pop. After the scan, balanced means the stack is empty. Ignore all non-bracket characters.
Quiz
Why is a stack exactly the right structure for bracket matching?