Data Structures — Stacks (LIFO)

By the end of this lesson you can:

• Build a Stack class with push, pop, peek, size, is_empty.
• Recognise three classic stack problems: balanced brackets, undo/redo, function calls.
• Know that a Python list IS a stack — append and pop are both O(1).
• Spot "LIFO" in real systems and pick a stack as the data structure.

Imagine a stack of plates. You can only do three things: add a plate on top, take the top plate off, or look at the top plate. You can't reach into the middle.

push A    →  [A]
push B    →  [A, B]
push C    →  [A, B, C]   ← top is C
peek      →  C            (look, don't remove)
pop       →  C            (remove and return)
                          [A, B] now
pop       →  B

Last in (C), first out. LIFO.

A Python list is already a stack

stack = []
stack.append("A")    # push
stack.append("B")
stack.append("C")
print(stack[-1])     # peek — top is C
print(stack.pop())   # pop — returns C, stack is now ["A", "B"]
print(len(stack))    # size
print(stack == [])   # is_empty?

List append is O(1) amortised; list pop() with no index is O(1). Python lists are essentially dynamic arrays, and the end is fast.

A wrapper class · for the named interface

Often you want a class that only allows stack operations — restricting the API to push/pop/peek is the point:

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if not self._items:
            raise IndexError("peek into empty stack")
        return self._items[-1]

    def __len__(self):
        return len(self._items)

    def is_empty(self):
        return len(self._items) == 0

    def __repr__(self):
        return f"Stack(top → {self._items[::-1]})"

Encapsulated. Outside code can't poke into the middle. _items is private; the four methods are the contract.

Classic application 1 · Balanced brackets

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

print(balanced("(a + [b * c] - {d})"))       # True
print(balanced("(a + [b)"))                    # False — wrong type
print(balanced("(a + b"))                      # False — unclosed
print(balanced("a)"))                          # False — extra close

Every open bracket goes on the stack. Every close pops the top and checks. If the wrong type pops, or there's no opener, fail. If the stack isn't empty at the end, unmatched opens.

Classic application 2 · Undo/redo

class Editor:
    def __init__(self):
        self.text = ""
        self._undo_stack = []
        self._redo_stack = []

    def type(self, s):
        self._undo_stack.append(self.text)
        self.text += s
        self._redo_stack.clear()         # any new edit invalidates redo

    def undo(self):
        if not self._undo_stack:
            return
        self._redo_stack.append(self.text)
        self.text = self._undo_stack.pop()

    def redo(self):
        if not self._redo_stack:
            return
        self._undo_stack.append(self.text)
        self.text = self._redo_stack.pop()


e = Editor()
e.type("Hello "); e.type("world"); e.type("!")
print(e.text)        # Hello world!
e.undo()
print(e.text)        # Hello world
e.undo()
print(e.text)        # Hello
e.redo()
print(e.text)        # Hello world

Two stacks. Undo pops from undo, pushes to redo. Redo pops from redo, pushes to undo. Every text editor works this way.

Classic application 3 · The call stack itself

When a function calls another, Python pushes a stack frame. When it returns, Python pops. RecursionError happens when you exceed the maximum stack depth. Recursion is "using the call stack as data" — every recursive function builds and unwinds a stack.

Reverse Polish Notation is "operator after the operands". 3 4 + means 3 + 4. RPN is a poster child for stacks. Save as rpn.py:

# rpn.py — evaluate Reverse Polish Notation

class Stack:
    def __init__(self):
        self._items = []
    def push(self, x): self._items.append(x)
    def pop(self): return self._items.pop()
    def __len__(self): return len(self._items)


OPS = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "*": lambda a, b: a * b,
    "/": lambda a, b: a / b,
}

def evaluate(expr):
    stack = Stack()
    for token in expr.split():
        if token in OPS:
            b = stack.pop()
            a = stack.pop()
            stack.push(OPS[token](a, b))
        else:
            stack.push(float(token))
    return stack.pop()


# Examples
print(evaluate("3 4 +"))                      # 7.0
print(evaluate("5 1 2 + 4 * + 3 -"))          # 14.0
# (1 + 2) * 4 + 5 - 3
# = 3 * 4 + 5 - 3
# = 12 + 5 - 3 = 14

Read the diff

Number tokens get pushed. Operator tokens pop two values, apply, push the result. At the end, one value remains — the answer. No parser, no parentheses logic. RPN's genius is that it doesn't need them — the stack tracks the structure.

A stack is a collection with three operations — push, pop, peek — restricted to one end. Last in, first out. Python lists do this for free (append and pop). A wrapper class is useful when you want to forbid middle access. Stacks are everywhere: brackets, undo/redo, browser history, function frames, RPN. Whenever you see "most recent first", reach for a stack.