Stacks

A stack restricts access to one end, and that restriction is what makes a family of otherwise quadratic problems linear. This guide starts from the invariant — what the stack holds and why the newest entry is the one the next input resolves — and works through bracket matching, expression evaluation, the monotonic stack behind next-greater and histogram problems, and the amortised counting argument that justifies calling a loop with a nested pop linear. It also treats the call stack as the data structure it is, covering recursion depth limits, the conversion to an explicit stack, and the fact that unbounded recursion over untrusted nested input is a denial-of-service vector rather than a robustness detail.

the stack contract

A stack is defined by last-in-first-out access, and that single restriction is what makes it useful rather than limiting.

Push, pop, and peek are all constant time, and because only the top is reachable the structure can be implemented on a contiguous array with no bookkeeping beyond a length.

Push, pop and peek are O(1) on a plain Python list used at one end.

stack = []
stack.append(x)     # push, amortised O(1)
top = stack[-1]     # peek, O(1)
stack.pop()         # pop, O(1)
stack.pop(0)        # not a stack operation: O(n), every element shifts

Interview trap. Treating a stack as a list that happens to be used at one end invites code that indexes into the middle, which breaks the reasoning every stack algorithm depends on.

Engineering practice. Expose only the stack operations at the boundary of the algorithm, so the invariant about the stack's contents stays checkable.

the stack invariant

Every stack algorithm has an invariant describing what the stack holds at any moment, and that sentence is the proof of correctness.

For bracket matching it is the unclosed openers in order; for a monotonic stack it is the candidates still able to be the answer; for a parser it is the pending reductions.

Write the invariant, then derive the pushes and pops from it.

# Invariant: `stack` holds the indices of openers not yet closed, in order of opening.
# Push  -> an opener arrived and is now unclosed.
# Pop   -> a closer matched the most recent unclosed opener.
# Empty at the end -> every opener was closed.

Interview trap. Writing push and pop by trial until the tests pass produces code whose behaviour on unseen input nobody can predict.

Engineering practice. Write the invariant first, then derive when to push and when to pop from it, and assert it in tests on small inputs.

balanced-bracket validation

Matching nested delimiters requires a stack, because the structure is recursive and cannot be decided by counting alone.

Each opener is pushed and each closer must match the top; the input is valid when every closer matches and the stack is empty at the end.

Counting is not enough: ')(' has balanced counts and invalid structure.

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

valid("()[]{}")   # True
valid(")(")       # False - counts match, structure does not
valid("([)]")     # False

Interview trap. Counting openers and closers is not sufficient — a closer followed by an opener has balanced counts and invalid structure.

Engineering practice. Check both conditions: every pop matches, and the stack is empty at the end; a non-empty stack means unclosed openers.

the empty-stack guard

Popping from an empty stack is the most common defect in this family, and it corresponds to a real input condition rather than an internal error.

A closer arriving with nothing on the stack means the input is unbalanced, so the correct response is to reject the input, not to crash or to continue.

An empty stack means invalid input, not an internal error.

if not stack:
    return False          # a domain answer
# rather than:
stack.pop()               # IndexError: pop from empty list

Interview trap. Catching the exception and continuing conflates malformed input with a bug and hides the case where the answer should have been 'invalid'.

Engineering practice. Test for emptiness before popping and return the domain-level answer, reserving exceptions for genuine programming errors.

the monotonic stack

A stack kept in sorted order answers next-greater and next-smaller questions for a whole array in linear total time.

Before pushing, every element that the new one dominates is popped and resolved, because the new element is its answer; each element is pushed once and popped once.

Each index is pushed once and popped once: O(n), not O(n^2).

def next_greater(a):
    out, stack = [-1] * len(a), []          # stack holds indices, decreasing by value
    for i, v in enumerate(a):
        while stack and a[stack[-1]] < v:
            out[stack.pop()] = v            # v is the answer for everything it dominates
        stack.append(i)
    return out

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

Interview trap. Believing the nested pop loop makes the algorithm quadratic misreads the amortisation — the total number of pops is bounded by the number of pushes.

Engineering practice. State the stack's ordering direction explicitly, and derive the pop condition from it rather than from the example.

storing indices rather than values

A monotonic stack usually stores indices, because the answer to these problems is a distance or a position, not just a value.

The index gives access to the value when needed and additionally to the span between the resolved element and its answer.

The distance answer needs the index; the value alone cannot give it.

out[stack.pop()] = i - popped_index      # days until warmer - needs positions
# temperatures = [73, 74, 75, 71, 69, 72, 76, 73] -> [1, 1, 4, 2, 1, 1, 0, 0]

Interview trap. Storing values makes span calculations impossible and forces a second pass that reintroduces the cost the stack removed.

Engineering practice. Default to indices, and read the value through the array so both are available at no extra cost.

elements left on the stack

Elements still on the monotonic stack when the scan finishes are exactly those with no answer, and they must be handled explicitly.

For a next-greater problem these are the suffix maxima, whose answer is the sentinel value the problem specifies.

Initialise to the sentinel, or drain the stack after the loop.

out = [-1] * len(a)      # the sentinel is already in place for anything never resolved
...
# equivalently, after the loop:
while stack: out[stack.pop()] = -1

Interview trap. Leaving the remaining elements untouched works only if the answer array was initialised to the right sentinel, which is easy to forget.

Engineering practice. Initialise the answer array to the sentinel up front, or drain the stack after the loop, and make the choice visible in the code.

largest rectangle in a histogram

The largest rectangle is found with a monotonic increasing stack, because each bar's rectangle is bounded by the nearest shorter bar on each side.

Popping a bar resolves its rectangle: its height is the popped value and its width spans from the element below it on the stack to the current position.

The width spans from the new stack top, not from the popped index.

def largest(h):
    stack, best = [], 0
    for i, v in enumerate([*h, 0]):            # sentinel 0 drains the stack
        while stack and h[stack[-1]] > v:
            height = h[stack.pop()]
            left = stack[-1] if stack else -1  # the bar below, not the popped one
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

largest([2, 1, 5, 6, 2, 3])   # 10

Interview trap. Computing the width from the popped index rather than from the new stack top understates every rectangle that spans several popped bars.

Engineering practice. Derive the width from the element below the popped one, and use a sentinel of zero height at the end so the stack always drains.

sentinels to avoid special cases

Appending a sentinel element that forces the stack to drain removes the post-loop cleanup and the class of bugs that lives in it.

A value that dominates or is dominated by everything triggers the remaining pops inside the main loop, so the resolution logic exists in exactly one place.

A trailing zero forces the drain inside the main loop.

for i, v in enumerate([*h, 0]):   # heights are non-negative, so 0 cannot be a real bar
    ...

Without it the resolution logic exists twice: once in the loop and once after it.

Interview trap. The sentinel must be outside the value domain or it produces a spurious answer of its own.

Engineering practice. Choose the sentinel from the documented value range, and note in a comment why it cannot be a legitimate input.

expression evaluation

Postfix expressions evaluate with one stack, while infix expressions need either two stacks or a conversion step.

In postfix each operator pops its operands and pushes the result, so precedence is already encoded in the order and no lookahead is needed.

Pop the right operand first, or subtraction and division break.

b = stack.pop(); a = stack.pop()      # b is the right operand
stack.append(a - b)

# "5 3 -" -> 2. Reversing the pops gives -2, while "5 3 +" is correct either way.

Interview trap. Popping operands in the wrong order breaks subtraction and division while leaving addition and multiplication correct, so half the tests pass.

Engineering practice. Pop the right operand first, and cover non-commutative operators explicitly in tests.

infix to postfix conversion

The shunting-yard algorithm converts infix to postfix with an operator stack driven by precedence and associativity.

Operands are emitted immediately; an operator pops higher-or-equal precedence operators before being pushed, with associativity deciding the equal case.

Associativity decides the equal-precedence case, and exponentiation is the test.

PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
RIGHT = {"^"}
while ops and PREC.get(ops[-1], 0) >= PREC[tok] and tok not in RIGHT:
    out.append(ops.pop())

# 2 ^ 3 ^ 2 must parse as 2 ^ (3 ^ 2) = 512, not (2 ^ 3) ^ 2 = 64.

Interview trap. Ignoring associativity gives the wrong parse for right-associative operators such as exponentiation, which most test expressions never exercise.

Engineering practice. Encode precedence and associativity in one table, and test both left- and right-associative operators at equal precedence.

the call stack as a data structure

Recursion is a stack the runtime manages, so every recursive algorithm has an explicit-stack equivalent with the same complexity.

Each frame holds parameters, locals, and a return address, which is exactly the state an explicit stack would carry.

A frame holds exactly what an explicit stack entry would.

# Recursive
def dfs(node):
    if not node: return
    visit(node); dfs(node.left); dfs(node.right)

# The same traversal with the frames made explicit
stack = [root]
while stack:
    node = stack.pop()
    if not node: continue
    visit(node); stack.append(node.right); stack.append(node.left)

Interview trap. Assuming recursion is free of the stack's memory cost hides that deep recursion consumes a limited, often small, runtime stack.

Engineering practice. Convert to an explicit stack when depth can reach the input size, and state the depth bound when defending a recursive solution.

recursion depth limits

Runtime stack depth is bounded, and the bound is far smaller than the heap, so linear-depth recursion fails on large inputs.

Interpreters impose an explicit recursion limit and compiled languages fail with a stack overflow, both of which occur at depths well below typical data sizes.

The default limit is 1,000 frames; raising it moves a clean error to a hard crash.

import sys
sys.getrecursionlimit()      # 1000
sys.setrecursionlimit(100_000)   # the C stack has not grown: segfault instead of RecursionError

A linked list of 10,000 nodes overflows a recursive traversal long before memory is a concern.

Interview trap. Raising the interpreter's recursion limit moves the failure from a clean exception to a process crash, because the underlying native stack is unchanged.

Engineering practice. Convert deep recursion to iteration with an explicit stack rather than raising the limit, and test at the maximum documented input size.

tail calls

A tail call could reuse the current frame, but most mainstream runtimes do not guarantee that optimisation.

Without the guarantee, a tail-recursive loop still consumes one frame per iteration and overflows at the same depth as any other recursion.

CPython does not eliminate tail calls, so the frame count is unchanged.

def count(n):
    if n == 0: return 0
    return count(n - 1)      # tail position, still one frame per call

count(2000)   # RecursionError - the position of the call buys nothing here

Interview trap. Writing tail-recursive code for depth safety in a language without the guarantee provides no protection at all.

Engineering practice. Check whether the runtime documents the optimisation; where it does not, write the loop.

iterative tree traversal

Depth-first traversal converts to an explicit stack directly, and the visit order is decided by the push order.

Pushing the right child before the left makes the left subtree pop first, reproducing preorder; the other orders need either a marker or a last-visited pointer.

Inorder needs the descend-then-pop shape; preorder does not.

stack, node, out = [], root, []
while stack or node:
    while node:                 # descend the left spine
        stack.append(node); node = node.left
    node = stack.pop()
    out.append(node.val)        # visit after the left subtree
    node = node.right

Interview trap. Assuming inorder is as simple as preorder leads to a loop that visits nodes twice or skips them, because the node must be revisited after its left subtree.

Engineering practice. Use the push-a-marker technique for in- and post-order, and verify against the recursive version on random trees.

the two-stack queue

Two stacks implement a queue with amortised constant-time operations.

Pushes go to the inbound stack; a dequeue pours the inbound stack into the outbound one only when the outbound is empty, which reverses the order exactly once per element.

Pour only when the outbound stack is empty; that is what makes it amortised O(1).

class Queue:
    def __init__(self): self.inbox, self.outbox = [], []
    def push(self, v): self.inbox.append(v)
    def pop(self):
        if not self.outbox:                 # guard - not on every pop
            while self.inbox: self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

Each element moves between the stacks exactly once, so n operations cost O(n) total.

Interview trap. Pouring on every dequeue makes each operation linear and destroys the amortisation; the transfer must happen only when the outbound stack is empty.

Engineering practice. Guard the transfer on emptiness, and state the amortised bound with the argument that each element moves between stacks at most once.

the constant-time minimum stack

A stack can report its minimum in constant time by storing, with each element, the minimum of the stack up to that point.

Pushing records the smaller of the new value and the current minimum, so popping restores the previous minimum without any recomputation.

Store the running minimum per entry; one variable cannot survive a pop.

stack = []
def push(v): stack.append((v, v if not stack else min(v, stack[-1][1])))
def get_min(): return stack[-1][1]

# push 3, 1, 4 -> [(3,3), (1,1), (4,1)]; pop 4 and 1 restores min 3 with no recomputation.

Interview trap. Keeping a single minimum variable is wrong, because popping the minimum leaves no way to recover the previous one.

Engineering practice. Store the running minimum per entry, or keep a parallel stack of minima, and test the sequence that pops the current minimum.

undo and history

Undo stacks are the production form of this structure, and redo is the second stack that the operation history moves between.

Performing a new action after an undo invalidates the redo stack, because the history has branched and the redone actions no longer apply.

A new action after an undo invalidates redo; leaving it lets a stale operation replay.

def do(action):
    undo_stack.append(action)
    redo_stack.clear()        # the history branched

Interview trap. Leaving the redo stack intact after a new action lets a user redo an operation whose preconditions no longer hold.

Engineering practice. Clear redo on any new action, and store inverse operations rather than snapshots when the state is large.

stack-based backtracking state

Backtracking is a stack of decisions, and the undo step is what makes the shared mutable state correct.

Each decision pushes its change and each return pops it, restoring the state exactly as it was before the branch was explored.

Pair every mutation with its undo in the same function.

path.append(v); visited.add(v)
explore(v)
path.pop(); visited.discard(v)      # adjacent to the change, so it cannot drift

Interview trap. Forgetting to undo a change on the way out leaks state between branches, producing results that depend on exploration order.

Engineering practice. Pair every mutation with its undo in the same function, and prefer a structure where the pairing is visually obvious.

stack versus queue

Depth-first search uses a stack and breadth-first uses a queue, and the choice changes which answer is found first, not just the traversal order.

The queue explores in order of distance, so the first time it reaches a node it has found a shortest path in edge count; the stack offers no such guarantee.

Swapping the structure changes the guarantee, not just the order.

frontier.pop()        # stack: depth-first, finds *a* path
frontier.popleft()    # queue: breadth-first, finds a *shortest* path in edge count

Interview trap. Substituting a stack for a queue in a shortest-path search yields a path rather than the shortest path, and the difference is invisible on small graphs.

Engineering practice. Choose the structure from the guarantee needed, and state that guarantee when defending the choice.

array-backed versus linked stacks

An array-backed stack is faster in practice while a linked one has worst-case constant push, and the difference is amortisation versus locality.

The array grows geometrically, so pushes are amortised constant with occasional linear copies, while the linked version allocates per element and pays a cache miss per access.

Amortised copies beat per-element allocation in practice.

Backing	Push	Worst-case push	Memory per element
Dynamic array	amortised O(1)	O(n) on resize	8 bytes + spare capacity
Linked nodes	O(1)	O(1)	8 bytes + node header + pointer

The linked version buys a worst-case bound and pays for it with an allocation and a likely cache miss per element.

Interview trap. Choosing the linked version for its worst-case bound usually costs throughput without giving latency back, because allocation is itself unpredictable.

Engineering practice. Default to the array-backed stack, and reserve the linked one for genuine worst-case latency requirements with measured allocation behaviour.

stack overflow as a security boundary

Unbounded recursion on attacker-controlled input is a denial-of-service vector, not merely a robustness issue.

Deeply nested input — nested JSON, nested archives, nested expressions — drives recursion depth linearly in the input, and the crash costs the process.

Nesting depth is attacker-controlled in every nested format.

import json
json.loads("[" * 100_000 + "]" * 100_000)   # RecursionError - one request, one dead worker

Bound parse depth explicitly for untrusted input rather than relying on the interpreter's limit.

Interview trap. Treating nesting depth as naturally bounded is exactly the assumption an attacker violates.

Engineering practice. Impose an explicit depth limit on parsers over untrusted input and reject beyond it, rather than relying on the runtime's limit.

capacity and memory bounds

An unbounded stack over untrusted input is a memory risk, so production stacks usually carry a maximum depth.

The bound converts an out-of-memory failure, which takes down the process, into a rejected input, which does not.

A bound turns an out-of-memory kill into a rejected input.

MAX_DEPTH = 10_000
if len(stack) >= MAX_DEPTH:
    raise InputTooDeep(f"nesting exceeds {MAX_DEPTH}")

Interview trap. Assuming the stack stays shallow because it does in normal traffic ignores the input that makes it deep.

Engineering practice. Set the bound from the documented input limits, and return a domain error when it is exceeded.

amortised analysis of stack algorithms

Stack algorithms with an inner pop loop are analysed by counting total pushes, not by multiplying loop bounds.

Each element is pushed at most once, so the total number of pops across the entire run cannot exceed the number of pushes — which gives a linear bound however uneven the individual iterations are.

Count total pushes, not the nested loop.

for i in range(n):            # n pushes
    while stack and cond():   # total pops across the whole run <= n
        stack.pop()
    stack.append(i)
# Therefore O(n), not O(n^2) - and the argument breaks if an element can be pushed twice.

Interview trap. Reading the nested loop as multiplication produces a quadratic claim that is both wrong and hard to argue against without the amortised framing.

Engineering practice. Present the argument as a counting argument over the whole run, and be ready to say what breaks it — an element that can be pushed more than once.

recognising a stack problem

A stack is the right structure when the most recently seen unresolved item is the one the next input resolves.

Nesting, matching, nearest-previous, and undo all share that shape, which is why the same structure serves parsing, histogram, and traversal problems.

The newest unresolved item is the one the next input resolves.

Problem	Stack?
Match nested delimiters	yes - nesting is last-in-first-out
Nearest previous greater element	yes - monotonic stack
Shortest path in an unweighted graph	no - a queue gives the guarantee
Most recently used eviction	no - that is a queue with reordering

Interview trap. Reaching for a stack because the problem mentions order is too loose a test and leads to solutions with no stated invariant.

Engineering practice. Ask what the stack would hold and why the newest entry is the one to resolve first; if that has no answer, the structure is wrong.