Stacks: last in, first out

A stack allows three things: push onto the top, pop off the top, peek at the top. Nothing else, and that restriction is what makes it useful.

push(1)  push(2)  push(3)     pop() -> 3

   |   |    |   |    | 3 |      | 2 |
   |   |    | 2 |    | 2 |      | 1 |
   | 1 |    | 1 |    | 1 |      +---+

All three are O(1). An array or a linked list can implement it.

Where you have already used one

Your program's call stack. Every function call pushes a frame; every return pops one. That is why the last page's recursion diagram is a stack, and why the error is called a stack overflow.

Undo. Each action is pushed; undo pops the most recent.

The back button. Same shape.

Matching brackets

The classic problem, and it is three lines because a stack is exactly the right shape:

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

The final return not stack is the part people forget: "(((" never fails a check and is still unbalanced.

Expression evaluation

Infix, 3 + 4 × 2, needs precedence rules. Postfix, 3 4 2 × +, needs only a stack: push numbers, and on an operator pop two, apply, push the result. Compilers convert one to the other for exactly that reason.