Stacks: Last In, First Out

Recall the cost table from lesson 2-3: the pair of O(1) list operations is append(x) and pop().

Both act on the end of the list, where an array is cheap. Append is amortized O(1) and popping the last item is O(1), while anything at the front is O(n) because of the shifting.

A structure that only ever touches one end can therefore ride those two cheap operations and never pay the shifting cost at all. That structure is the stack, and this lesson is about what it is good for.

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).

A tiny undo history

Each save pushes a draft, and each undo pops the most recent one.

stack = []
stack.append("draft v1")
stack.append("draft v2")
stack.append("draft v3")
print("undo:", stack.pop())
print("undo:", stack.pop())
stack.append("draft v4")
print("undo:", stack.pop())
print("left on stack:", stack)

Output

undo: draft v3
undo: draft v2
undo: draft v4
left on stack: ['draft v1']

The order of those undos is the point. Draft v3 goes first because it arrived last, then v2, and then v4, which was pushed after two undos had already happened.

Draft v1 is never touched. It sits at the bottom of the stack throughout, unreachable until everything above it has been popped, which is exactly the behavior an undo history needs.

Nothing here is a special stack type. It is a plain list plus the discipline of only ever calling append and pop, which is what makes the two cheap end operations the only ones in play.

The classic: matching brackets

Every editor and compiler checks that (, [, and { close in the right order, and the insight behind that check is pure LIFO: the most recently opened bracket must close first.

The procedure follows directly. Scan the text and push every opener. On a closer, the top of the stack must be its partner, so pop it. The text is unbalanced if the top is the wrong opener, if the stack is empty when a closer arrives, or if anything is still open at the end.

Walking ([)] by hand shows the failure clearly. Push (, push [, then ) arrives while the top is [, which is a mismatch, so the text is unbalanced.

That example is worth noticing because both bracket types appear the correct number of times. Counting brackets would call it balanced, and only the ordering check catches it, which is what the stack contributes.

The whole scan is one O(n) pass with at most n items on the stack.

The bracket checker

Openers get pushed, closers check the top and pop, and everything else is ignored.

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

for s in ["(a[b]c)", "([)]", "{[()]}", "((a)", "x)("]:
    print(s, balanced(s))

Output

(a[b]c) True
([)] False
{[()]} True
((a) False
x)( False

The pairs dict maps each closer to the opener it requires, which turns the partner check into a lookup rather than a chain of comparisons.

The closer test has two halves for two different failures. not stack catches a closer with nothing open, which is why x)( fails on its very first bracket, and stack[-1] != pairs[ch] catches a wrong-order match, which is the ([)] case.

The final line is the one people forget. Returning True inside the loop would accept ((a), since nothing in that string mismatches. It fails only because one ( is left over at the end, so the verdict has to be len(stack) == 0 after the scan completes.

A stack is exactly right for bracket matching because the most recently opened bracket must be the first to close, which is LIFO order.

Nesting reverses the sequence. Opening {[( requires closing )]}, so the last thing opened is the first thing that may close, and the phrase last opened, first closed is a restatement of last in, first out.

That correspondence means the stack's top is always the one bracket allowed to close next, so the check is a single comparison rather than a search through everything still open.

It also explains why no other structure fits as neatly. A counter loses the ordering, and a list scanned from the front would answer the wrong question, since the oldest open bracket is precisely the one that must close last.