Stacks

1One end, and only one end

A stack is a list with most of its abilities deliberately removed. That is the entire design.

A stack supports exactly two operations, both on the same end:

• push(x) — put x on the top
• pop() — remove and return the top

Usually plus peek() (look at the top without removing) and is_empty(). That is the whole interface. Last in, first out — LIFO.

# In Python you do not need a class. A list IS a stack:
stack = []
stack.append("A")      # push   — O(1) amortised
stack.append("B")      # push
top = stack[-1]        # peek   — O(1)
x = stack.pop()        # pop    — O(1), returns C
empty = not stack      # is_empty

# Use the END of the list, never the front. append/pop are O(1);
# insert(0, x)/pop(0) are O(n) and would make every operation linear.

2Matching brackets

The first problem where a stack is not merely convenient but necessary. Counting cannot solve it; remembering order can.

Is {[a+(b*c)]-d} correctly bracketed? A first instinct is to count: as many ( as ), and so on. That fails immediately:

"[(])"     # one of each kind of bracket — counts balance perfectly
           # and it is obviously wrong

The problem is that brackets have order: the most recently opened bracket must be the next one closed. “Most recent, first out” is the definition of a stack, so a stack is not one possible tool here — it is the shape of the problem itself.

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)              # we now owe a matching close
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False              # wrong closer, or nothing open
    return not stack                      # anything left open is a failure

# O(n) time, O(n) space in the worst case (H).
#
# Two failure modes, and both must be checked:
#   1. a closer that does not match the top     → I
#   2. openers left on the stack at the end      → J

3The call stack

You have been using a stack since your first program. It is the mechanism that makes function calls work at all.

When a function is called, the machine has to remember where to come back to and what the local variables were. It pushes a stack frame holding exactly that. When the function returns, the frame is popped and execution resumes where the frame said.

Why a stack and not something else? Because calls nest perfectly: the function that started most recently is always the one that finishes first. That is LIFO, and nothing else would work.

def a():
    print("a starts")
    b()                  # push a frame for b; a's frame WAITS below it
    print("a ends")      # ← the return address stored in b's frame

def b():
    print("b starts")
    c()
    print("b ends")

def c():
    print("c starts")
    print("c ends")

a()

# Stack over time (top on the right):
#   [a]  →  [a, b]  →  [a, b, c]  →  [a, b]  →  [a]  →  []
#
# Output: a starts, b starts, c starts, c ends, b ends, a ends.
# The G come out in exactly reverse order. That is the stack talking.

Turning recursion into iteration

Any recursive function can be rewritten with an explicit stack, because that is all recursion is. This matters when the depth would blow the call stack:

# Recursive — elegant, O(depth) call-stack frames
def sum_nested(x):
    if isinstance(x, list):
        return sum(sum_nested(item) for item in x)
    return x

# Iterative with an explicit stack — same result, no frames
def sum_nested_iter(x):
    total = 0
    stack = [x]
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(item)     # push all children
        else:
            total += item
    return total

# The list `stack` is doing precisely the job the machine's call stack
# was doing. The only difference is that it lives on the heap, where
# there is no 1,000-frame limit.

4The monotonic stack

The technique that makes stacks more than a data-structures-course exercise. It turns a family of O(n²) problems into O(n).

The problem: for each element of an array, find the next element to its right that is larger. Brute force checks every pair: O(n²).

The insight: keep a stack of elements still waiting for their answer, and maintain it in decreasing order. When a new value arrives, it is the answer for everything on the stack smaller than it — so pop them all and record it.

def next_greater(xs):
    result = [-1] * len(xs)
    stack = []                       # holds INDICES, in decreasing value order
    for i, x in enumerate(xs):
        while stack and xs[stack[-1]] < x:
            result[stack.pop()] = x  # x is the answer for that waiting index
        stack.append(i)
    return result                    # anything left has no greater element

next_greater([2, 1, 2, 4, 3, 5])     # [4, 2, 4, 5, 5, -1]

What the pattern looks like in the wild

Once you know the shape, you see it everywhere. All of these are the same algorithm with a different comparison:

5Undo, and other stack-shaped problems

A last sweep of places a stack is the right answer, to build the recognition reflex.

Undo and redo

Two stacks. Every action pushes onto the undo stack. Undo pops from it and pushes onto the redo stack. A new action clears the redo stack — which is exactly the behaviour you have always experienced in an editor and probably never wondered about.

class Editor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []
        self.redo_stack = []

    def type(self, s):
        self.undo_stack.append(self.text)
        self.redo_stack.clear()      # a new action invalidates the redo history
        self.text += s

    def undo(self):
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()

    def redo(self):
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()

Evaluating expressions

Reverse Polish notation — 3 4 + 2 * — evaluates with one stack and no parentheses at all. Push numbers; on an operator, pop two, combine, push the result. Compilers convert infix to postfix precisely so this becomes possible.

Depth-first search

Chapter 20 explores graphs two ways. The only difference between breadth-first and depth-first search is whether the frontier is a queue or a stack. Swap one for the other and the behaviour flips completely — same code, different container.

Backtracking

Chapter 27's “choose, explore, un-choose” loop is a stack of decisions. Un-choosing is a pop.

>_Playground

A stack class, a bracket matcher and a monotonic stack, all runnable. Try feeding the bracket matcher strings that should fail.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.