🧩 Data Structures & Algorithms · Chapter 6

Stacks

Undo in your editor, the back button in your browser, and the way your program remembers where to return after a function call are all the same tiny structure: last in, first out.

Study this lesson free in the app →

The basics

A stack is a collection where you only touch the top: you push an item onto it, and pop the most recently pushed item off. Last in, first out — LIFO.

The problem it solves: many tasks need to remember things and then deal with them in reverse order — the most recent unfinished thing first. Undo reverses your latest edit. A closing bracket must match the most recent unmatched opening bracket. When a function finishes, the program returns to the function that called it most recently. A stack gives you exactly that order, with every operation in O(1) time.

The mental model: a pile of plates in a kitchen. You put a clean plate on top, and you take from the top. You never pull from the middle.

In Python, a plain list is a stack: append pushes, pop() pops, lst[-1] peeks. Space is O(n) for n items.

Explained

You type a sentence, bold a word, then delete a paragraph. You press Undo three times.

The paragraph comes back first, then the bold disappears, then the sentence goes. Most recent first, every time.

That order — last in, first out — is a stack, and it's also how your program finds its way back out of every function call it makes.

Plates in a canteen

A canteen keeps clean plates in a spring-loaded stack. The dishwasher puts each clean plate on top; each diner takes the plate on top.

Nobody digs for the plate at the bottom — it's the one that's been waiting longest, and it will be the last one used.

Now imagine a waiter carrying nested trays: a big tray, on it a smaller tray, on that a saucer. To put them away, he must remove the saucer first, then the small tray, then the big one — the reverse of how they were stacked. Brackets in { [ ( ) ] } work the same way: the innermost one opened last must close first.

Precisely

A stack supports:

| Operation | Does | Time | | --- | --- | --- | | push(x) | add x on top | O(1) | | pop() | remove and return the top | O(1) | | peek() | return the top, leave it | O(1) | | is_empty() | any items left? | O(1) |

Space is O(n) for n items. There's no searching or indexing — that's the point: the restriction is what makes every operation constant-time.

Implementations:

• Dynamic array (Python list): the top is the end. append and pop() are O(1) amortised. Cache-friendly; the usual choice.
• Linked list: the top is the head. Push and pop are O(1) worst case, with an extra pointer per item.

collections.deque also works as a stack (append / pop). For multi-threaded producers and consumers, queue.LifoQueue adds locking.

Push, peek, pop

Three pushes build 3, 7, 1 with 1 on top. peek shows 1 but leaves it. pop removes 1. Push 9, then pop takes 9 — the newest — not 7. The last pop removes 7, leaving only 3, the first item in. Every operation touches only the top: O(1).

Brackets as a stack: { [ ( ) ] }

Read { [ ( ) ] } left to right, with 3 = {, 2 = [, 1 = (. Each opener is pushed. Each closer pops — and the popped item is always the most recent unmatched opener, which is exactly the one it must match: ) pops (, ] pops [, } pops {. Empty at the end → balanced.

A monotonic stack: next greater element

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []                         # indices still waiting for a bigger value
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x       # x is the answer for everyone smaller
        stack.append(i)
    return ans

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

The stack always holds values in decreasing order from bottom to top. When a bigger value arrives, it resolves every smaller value waiting on top.

There's a while inside a for, but every index is pushed exactly once and popped at most once — so it's O(n) time, O(n) space, not O(n²). The same shape solves "days until a warmer temperature", "stock span" and "largest rectangle in a histogram".

The stack you didn't create

Every running program has a call stack. Calling a function pushes a frame (its local variables and where to return); returning pops it.

main() → load() → parse() → parse_row()      ← top

When parse_row returns, control goes back to parse — the frame underneath. A crash prints this stack as the traceback.

Recursion pushes one frame per level. Python caps the depth at about 1,000 frames by default (sys.getrecursionlimit()), then raises RecursionError; C and Java crash with a stack overflow. So recursion over a 100,000-node linked list or a very deep tree will fail in Python — the fix is to convert it to a loop with your own stack, which lives on the heap and can grow as large as memory allows.

That's also why depth-first search is usually written with an explicit stack in production code.

Gotchas

• Popping an empty stack — [].pop() raises IndexError. In bracket matching, a closer with nothing to match (")(") must return False, not crash.
• Forgetting the final check — "(()" never mismatches, but leaves ( on the stack. Return not stack, not True.
• Using the front of a list — insert(0, x) / pop(0) give the same LIFO behaviour at O(n) per operation.
• Calling a monotonic stack O(n²) — count pushes and pops, not loops.
• Unbounded recursion — deep input turns elegant recursive code into a RecursionError. Know when to switch to an explicit stack.
• Reaching for a stack when order should be FIFO — serving requests or BFS needs a queue; a stack would starve the oldest items.

Words to know

In two minutes

• A stack is LIFO: push onto the top, pop from the top, peek at the top — each O(1). Space is O(n).
• In Python use a list: append to push, pop() to pop, lst[-1] to peek, if lst: to check empty. Never use the front of the list — insert(0, x) and pop(0) are O(n).
• Reach for a stack when the most recent unfinished thing must be handled first: undo, back buttons, matching brackets, evaluating expressions.
• Bracket matching: push openers; on a closer, pop and check it matches; at the end the stack must be empty. O(n) time, O(n) space.
• Your program's call stack is a stack: each call pushes a frame, each return pops one. Deep recursion overflows it — Python stops at about 1,000 frames by default.
• A monotonic stack keeps items in sorted order by popping smaller ones; it solves 'next greater element' in O(n), because each item is pushed and popped at most once.
• Depth-first search is a stack too — explicit, or hidden in recursion.

Test yourself

There are 9 questions, 4 puzzles and 5 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.