Stacks

The mental model: a commitment to recency

Here is the core constraint: you can only touch the top. No indexing into position 3. No reading the middle. The only element you have access to at any moment is the one you put there most recently.

That sounds like a restriction, and it is. But the right framing is that it is a contract. When a problem has genuine LIFO structure — nested parentheses, function calls, recursive backtracking — a stack enforces that structure mechanically. You can't accidentally read the wrong element because the wrong element isn't accessible.

The two operations, formally:

• push(x) — place x on top of the stack.
• pop() — remove and return the top element.
• peek() / top() — return the top element without removing it.

All three are O(1). That is the defining characteristic. A stack is not interesting because it is fast in general — you cannot even search it without destroying it. It is interesting because it is an O(1) commitment machine for reversal and nesting.

Under the hood: two perfectly reasonable implementations

Array-backed (the default)

An array-backed stack appends to the end of a dynamic array and pops from the end. "Top of stack" is the last index.

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

    def push(self, val):
        self._data.append(val)   # O(1) amortized

    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()  # O(1)

    def peek(self):
        if not self._data:
            raise IndexError("peek at empty stack")
        return self._data[-1]    # O(1)

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

In Python you usually skip the wrapper entirely — list is a perfectly good stack. append pushes, pop() pops, [-1] peeks. Same in JavaScript with an Array. The wrapper is worth writing in a team codebase for clarity, but in interview code you do not need it.

The one nuance: dynamic arrays occasionally resize and copy, so push is O(1) amortized rather than strictly O(1). In practice this almost never matters — see the arrays article for why the amortized argument works — but if you have a hard latency constraint on every single push, reach for the linked-list implementation instead.

Linked-list-backed

A singly-linked list where the head is the top gives true O(1) push and pop with no resize spikes.

flowchart LR
    TOP["top → [1]"] --> N7["[7]"] --> N3["[3]"] --> NULL["null"]
    style TOP fill:#7c5cff,color:#0a0a0f
    style N7 fill:#1e1e2e,color:#cdd6f4
    style N3 fill:#1e1e2e,color:#cdd6f4

Push prepends a new node (makes it the new head). Pop removes the head. No copying, no resizing. The downside is pointer overhead and cache pressure — each node is a separate allocation, so the CPU cannot blast through memory linearly the way it can with an array. For most stacks this is irrelevant; for hot paths processing millions of items it can show up in profiling.

Rule of thumb: use the array-backed version unless you have a specific reason not to. Python list, JavaScript Array, Java ArrayDeque, C++ std::stack — all of these are array-backed by default for good reason.

The structure in action

Here is the stack visualizer again — this time think about what happens when you push three items, then pop them.

{ "type": "stack", "variant": "stack", "title": "LIFO order in practice", "data": [10, 20, 30] }

Push 10, push 20, push 30. Now pop three times: you get 30, 20, 10. The original order is reversed. If you were processing items in order 1 → 2 → 3 and need to handle them in order 3 → 2 → 1, a stack does that for free. That is why stacks show up in reversal algorithms, in DFS (you explore the most recently discovered node first), and in the call stack (the most recently called function returns first).

The call stack: the stack you already know

You have been using a stack since the first time you called a function. When your program calls foo(), the CPU pushes a stack frame containing foo's local variables, return address, and saved registers. When foo calls bar(), another frame gets pushed on top. When bar returns, its frame is popped and execution resumes in foo exactly where it left off.

flowchart TB
    subgraph "Call stack (grows down)"
        direction TB
        F1["main() frame"]
        F2["compute() frame"]
        F3["helper() frame  ← top (currently executing)"]
    end
    style F3 fill:#7c5cff,color:#0a0a0f
    style F2 fill:#22d3ee,color:#0a0a0f
    style F1 fill:#1e1e2e,color:#cdd6f4

This is why recursion and stacks are so intertwined — recursive algorithms are stack-based algorithms. The OS call stack is just an implicit one managed by your runtime. When you convert a recursive DFS into an iterative one, you are literally replacing that implicit OS stack with an explicit one you control. Same idea; you just get to see it.

Stack overflow? That is literally the stack overflowing — you pushed too many frames (usually an infinite recursion) and ran out of the memory region reserved for the call stack.

Three problems a stack solves immediately

1. Balanced parentheses

Given a string like "({[]})", decide whether every opening bracket has a matching closing bracket in the right order.

The insight: open brackets are deferred decisions. You see ( and you think "I will come back to this later." The most recently opened bracket is the one you must close next. That is LIFO.

def is_balanced(s: str) -> bool:
    stack = []
    match = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in '([{':
            stack.append(ch)          # defer it
        elif ch in ')]}':
            if not stack or stack[-1] != match[ch]:
                return False          # mismatch or nothing to close
            stack.pop()               # close the most recent open

    return len(stack) == 0            # unmatched opens remaining?

O(n) time, O(n) space (at most n/2 items on the stack if everything is opens). This is the single most common stack interview problem. Internalize it.

2. Undo / redo

Every text editor you have ever used has a stack hidden behind Cmd-Z. Every action you take gets pushed. Undo pops the top action and reverses it. If you keep a separate redo stack, undone actions push onto that — Cmd-Shift-Z pops from redo and pushes back onto undo.

undo_stack = []
redo_stack = []

def do_action(action):
    action.execute()
    undo_stack.append(action)
    redo_stack.clear()        # new action kills the redo history

def undo():
    if undo_stack:
        action = undo_stack.pop()
        action.reverse()
        redo_stack.append(action)

def redo():
    if redo_stack:
        action = redo_stack.pop()
        action.execute()
        undo_stack.append(action)

The stack gives you O(1) undo and redo at any depth, with no searching or scanning. Git's commit history follows the same pattern in spirit.

3. Iterative DFS

Depth-first search naturally recurses — go as deep as you can, backtrack, try the next branch. But the iterative version just makes the implicit call stack explicit:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()            # most recently discovered node first
        if node in visited:
            continue
        visited.add(node)
        process(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

    return visited

Swap the stack for a deque and change pop() to popleft() and you have BFS. The data structure is the only thing that changes between depth-first and breadth-first. That's worth sitting with for a moment.

The tell: when a problem wants a stack

You don't always recognize "this needs a stack" immediately. Here is the pattern recognition shortcut:

Signal in the problem	Stack pattern
"Matching" or "balanced" (brackets, tags, calls)	Push opens, pop on close
"Most recent" or "last seen"	Peek or pop to get it
Need to reverse something	Push everything, then pop
DFS / backtracking	Explicit stack for iterative version
"Previous greater/smaller element"	Monotonic stack
Undo/redo or history	Push to undo, pop to redo

The deepest tell: if the order of processing is the reverse of the order of arrival, it's a stack. The monotonic stack extends this to a whole class of problems where you maintain a sorted invariant as you go — "next greater element," "largest rectangle in histogram," and "trapping rain water" all collapse to the same 8-line pattern once you see it.

Anti-patterns and pitfalls

Forgetting to check empty before pop. Every single time. stack.pop() on an empty list in Python raises IndexError; in languages like C++ it is undefined behavior. The correct habit is always if stack: ... before you pop, or handle the exception explicitly.

Using a stack when you need both ends. If you find yourself peeking at the bottom of the stack or wanting to push to the bottom, you do not have a stack problem — you have a queue or deque problem. A stack only exposes one end; if you need both, you need a different structure.

Rebuilding the structure during search. There is no O(1) way to ask "is value x anywhere in this stack?" without popping until you find it. If you are searching a stack repeatedly, that is a sign either that you have the wrong data structure, or that you need to maintain a parallel set or hash map alongside the stack for lookups.

Over-using recursion when an explicit stack is clearer. This is the reverse of the DFS example — sometimes people write recursive code for inherently iterative problems because "it reads nicer," then hit stack overflow on large inputs. If your input could be 100,000 items deep, write the loop. Python's default recursion limit is 1,000; you will hit it.

When not to use a stack

Stacks are sharp but narrow. Do not reach for one when:

• You need to access elements in insertion order (first-in, first-out): use a queue.
• You need random access by index: use a plain array.
• You need the minimum or maximum element quickly: use a heap (or a stack augmented with a running min/max — a classic interview variant).
• You need to know if a value exists without consuming the stack: use a hash set alongside it, or rethink whether the stack is the right structure.

The boundaries are clean: if your problem fundamentally cares about the most recent element and only the most recent element, a stack fits perfectly. Once you need anything else, you need a different tool.