Stacks

A stack is a last-in-first-out container with constant-time push and pop, the natural structure for nested and reversible work.

Last in, first out

A stack exposes just two core operations: push adds an element to the top, and pop removes and returns the top element. The most recently added item is always the first removed, a discipline called LIFO. Both operations are O(1), and a peek that reads the top without removing it is also O(1).

Two ways to build one

A stack backed by a dynamic array pushes and pops at the high-index end, so no element ever shifts. A stack backed by a linked list pushes and pops at the head. Both give amortized O(1) operations; the array version has better cache behaviour, the list version never needs to resize.

Where stacks appear

• The call stack: every function call pushes a frame, every return pops one
• Expression evaluation and matching brackets
• Undo histories and browser back buttons
• Iterative depth-first search in place of recursion
• Backtracking search that must unwind choices

Recursion is a stack

Any recursive algorithm can be rewritten iteratively by managing an explicit stack that holds the state each call would have kept. This is exactly what the machine does under the hood, and it is how you convert a deep recursion that would overflow the call stack into a loop with a heap-allocated stack.

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

Why LIFO is the right tool

Whenever the most recent unfinished task must be resolved before older ones, a stack models the problem directly. That pattern covers parsing, tree traversal, and any process that opens contexts and must close them in reverse order.