Stack — Last In, First Out

What is it? #

A stack only lets you add and remove at one end. The last thing you put in is the first thing you take out — last in, first out.

There are just three operations worth naming: push (add), pop (remove and return the most recent), and peek (look at the most recent without removing it). All are O(1).

The restriction is the feature. Because you can only touch the top, the order is guaranteed, and a whole class of problems becomes simple.

Any time a problem involves "the most recent unfinished thing", a stack is probably the answer.

Think of it like this #

A pile of plates. You add to the top and take from the top. Nobody pulls a plate from the middle of the stack — and that restriction is exactly why the pile stays stable.

The undo button in your editor is the same idea. Ctrl+Z reverses the most recent change, not a random earlier one.

Simple example #

Checking whether brackets in an expression are balanced. Every opening bracket must be closed by the matching type, in the right order. A stack tracks which opening bracket is still waiting.

Code #

# A Python list is already a stack
stack = []
stack.append("a")        # push
stack.append("b")
print(stack[-1])         # peek -> 'b'
print(stack.pop())       # pop  -> 'b'
print(stack)             # ['a']


def brackets_balanced(text: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack          # anything left open means unbalanced


print(brackets_balanced("{[a + (b * c)]}"))   # True
print(brackets_balanced("{[a + (b * c]}"))    # False


# Undo history
class Editor:
    def __init__(self):
        self.text = ""
        self._history = []

    def type(self, chars):
        self._history.append(self.text)      # remember the previous state
        self.text += chars

    def undo(self):
        if self._history:
            self.text = self._history.pop()


editor = Editor()
editor.type("Hello")
editor.type(" world")
editor.undo()
print(editor.text)        # Hello


# Evaluating reverse Polish notation: "3 4 + 2 *"
def evaluate_rpn(tokens):
    stack = []
    for token in tokens:
        if token in "+-*/":
            b, a = stack.pop(), stack.pop()
            stack.append({"+": a + b, "-": a - b, "*": a * b, "/": a / b}[token])
        else:
            stack.append(float(token))
    return stack.pop()


print(evaluate_rpn("3 4 + 2 *".split()))      # 14.0

How it works #

A Python list already behaves as a stack: append pushes at the end, pop() removes from the end, and [-1] peeks. Both operations are O(1) because they touch the cheap end of the array.

In brackets_balanced, every opening bracket is pushed. When a closing bracket arrives, the top of the stack must be its matching opener — if it is not, the nesting is wrong. Popping is how you say "that one is now resolved".

The final return not stack catches unclosed brackets. An empty stack means everything opened was closed.

The Editor class stores each previous state before changing. Undo pops the most recent state back. Real editors store smaller diffs rather than whole documents, but the structure is identical.

evaluate_rpn pushes numbers and, on each operator, pops the two most recent values, applies the operation and pushes the result. Notice the order: b comes off first because it was pushed last, which matters for subtraction and division.

The deepest example is one you use constantly without seeing it: the call stack. Every function call pushes a frame with its local variables; every return pops it. Infinite recursion fills that stack, which is exactly what RecursionError means.

Real-world use #

Stacks are behind undo and redo, browser back buttons, expression parsing in compilers, syntax highlighting, and depth-first traversal of trees and graphs.

Every program you run uses one for function calls. Understanding that makes stack traces readable: the list you see is the stack, most recent call at the top.

Parsers and interpreters lean on stacks heavily — matching tags in HTML, nesting in JSON, operator precedence in expressions. If you ever write a small parser, you will reach for one immediately.

In Python the practical advice is simple: use a list. It is a stack already, and collections.deque is available when you also need fast operations at the other end.

Common mistakes #

• Popping from an empty stack. Always check first, or catch IndexError.
• Using pop(0) and turning a stack into a slow queue.
• Forgetting to check that the stack is empty at the end of a matching algorithm.
• Getting operand order backwards when popping two values for a binary operator.
• Deep recursion where an explicit stack would avoid hitting the recursion limit.

Practice #

Write a function that takes a string of HTML-like tags such as "