Stack

Where this idea comes from

Let me show you a stack of plates.

You eat dinner. You wash a plate. You put it on top of the stack in the cupboard. Tomorrow morning you grab a clean plate — which one do you get? The one you washed last night. Always the one you washed last night.

Now here’s the thing I want you to notice about that cupboard. You never reach into the middle. You don’t pull from the bottom. The bottom plate has been sitting there since you moved in three years ago. It is still clean. It is still waiting. And every plate that came after it has come and gone — washed, used, washed, used — while the bottom plate has done absolutely nothing.

That’s it. That’s the entire data structure.

A computer scientist looks at that cupboard and writes down one rule: you can only touch the top. Three operations follow from that rule and only those three: push (put a plate on), pop (take the top plate off), and peek (look at the top plate without removing it). No “give me the plate at position 3”. No “is there a blue plate anywhere in there?”. No “insert this plate between the second and third one”. Only the top. Always the top.

When someone first told me this in a CS class, I remember thinking: that’s it? That’s the whole structure? It seemed almost cheating — like I was being handed a tool that had been deliberately weakened, and being told to be excited about it. And it took me embarrassingly long to see what’s actually going on, which is that the rule isn’t a limitation. The rule is what gives the stack its power.

Here is the whole picture in one diagram. Four moments in the life of the same stack:

Each panel is the same cupboard at a different moment. Bottom never moves. Top changes every time. The label “top” follows the most recent plate, which is also the next plate that will leave.

The textbooks call this LIFO — last in, first out. I want you to forget that acronym for a minute and just hold the cupboard in your head. We’ll earn the acronym in a second.

Why the rule pays for itself

When you commit to only ever touching the top, two things become true that feel almost too good. They are not obvious. I want to walk you through both because if you internalise just these two consequences, every interesting stack problem you’ll ever see will already make sense.

The first thing. The stack remembers, for free, the reverse of the order in which things were pushed. The last plate you washed is the first plate you’ll grab. The second-last plate you washed is the second plate you’ll grab. The cupboard, just by being a cupboard, is acting as a perfect chronological tape running backwards. You didn’t tell it to remember anything. You didn’t add a timestamp. The structure remembers because the structure had no other choice.

That’s where the LIFO acronym comes from, and I’ll grant the acronym is fine. But the thing is more interesting than the acronym. The thing is “order, for free, just by stacking.”

The second thing. Every operation is fast. Specifically: O(1). Constant time. The cost of pushing a plate is independent of how many plates are already in the cupboard. Same for popping. Same for peeking. Why? Because none of those operations involve searching, shifting, or rebalancing. Push touches the top. Pop touches the top. Peek touches the top. The top is one fixed place — the top of the cupboard or, in code, the end of an array, or the head of a linked list. You move one pointer, or you call one array method, and you’re done.

Compare this to, say, “insert this value into a sorted array at the right position”. That’s O(n) — the array has to shift everything after the insertion point one step to the right. Stack push? You don’t insert into anything. You drop on top. Nothing shifts. The cost doesn’t grow.

There’s a flip side, and it is the thing the rule costs you. You can’t ask “what’s the third plate from the bottom?”. You can’t ask “is there a salad plate in here somewhere?”. You can’t quietly slip a plate in between the fourth and fifth. The stack will refuse, because doing any of those things would require breaking the touch-only-the-top rule, and breaking the rule is what would make push and pop slow again. The constraints are the speed.

This is the part I think people miss when they first learn about data structures: the restrictions are not bugs. The restrictions are the feature. Every restriction a data structure imposes is trading expressiveness for some other property — speed, simplicity, predictability, correctness. A stack trades random access for two operations that are always fast and an order memory that’s automatic. If you find yourself wanting to reach into the middle of a stack, the right move is almost never “force the stack to let me do that”. It’s to ask: did I want a stack in the first place?

Building one, from scratch, in Python

A Python list is, secretly, already a stack. list.append puts a value at the end (the top). list.pop removes and returns the value at the end. list[-1] peeks at the end. This is not a coincidence — Python’s authors knew people would use lists as stacks, and they made the relevant operations fast on purpose.

stack: list[int] = []
stack.append(1)        # push
stack.append(2)        # push
top = stack[-1]        # peek → 2
value = stack.pop()    # pop  → 2, stack is now [1]
empty = not stack      # False

For 99% of stack problems, this is the implementation. There is no need to do anything fancier. If an interviewer asks you to “implement a stack” they’re usually checking that you know how the operations work, not that you have memorised some textbook scaffolding. Wrap a list, name the methods properly, and you’re done.

That said — I think it is worth seeing the class version once. Two reasons. First, naming the operations explicitly is what makes the next handful of problems write themselves. Second, when you start composing stacks (a stack of stacks, two stacks running in parallel, an undo stack alongside a redo stack), having a clean type saves you from getting tangled in raw list operations.

from typing import Generic, TypeVar

T = TypeVar("T")


class Stack(Generic[T]):
    """LIFO container. Every operation is O(1)."""

    def __init__(self) -> None:
        self._items: list[T] = []

    def push(self, x: T) -> None:
        self._items.append(x)

    def pop(self) -> T:
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self) -> T:
        if not self._items:
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def __len__(self) -> int:
        return len(self._items)

    def __bool__(self) -> bool:
        return bool(self._items)

Notice the IndexError on empty pop. This is the one place a stack can fail. Every real stack bug — and I mean every single one I’ve ever seen, including ones I’ve written myself — eventually traces back to forgetting to check if stack: before popping. Train your fingers to type that check. It is the only landmine in this entire chapter.

You can do the same wrapping with collections.deque, which is Python’s double-ended queue. For a pure stack the performance is identical to a list — Python’s list already uses an over-allocated array and amortizes append to O(1) — but the type signals intent more clearly. If you ever want O(1) operations on both ends of the structure, deque is what you need; a list’s pop(0) is O(n) because every other element has to shift down.

from collections import deque

class DequeStack(Generic[T]):
    def __init__(self) -> None:
        self._items: deque[T] = deque()

    def push(self, x: T) -> None:
        self._items.append(x)

    def pop(self) -> T:
        return self._items.pop()      # raises IndexError if empty

    def peek(self) -> T:
        return self._items[-1]

    def __len__(self) -> int:
        return len(self._items)

And finally, the version your data structures textbook will show you: a stack built out of raw linked-list nodes. Each push creates one node. Each pop unlinks one. This is the version you’d build if you didn’t have a list builtin at all — if you were sitting on a desert island with nothing but pointers and structs.

from dataclasses import dataclass
from typing import Optional

@dataclass
class _Node(Generic[T]):
    value: T
    next: Optional["_Node[T]"] = None


class LinkedStack(Generic[T]):
    def __init__(self) -> None:
        self._top: Optional[_Node[T]] = None
        self._size: int = 0

    def push(self, x: T) -> None:
        self._top = _Node(x, next=self._top)
        self._size += 1

    def pop(self) -> T:
        if self._top is None:
            raise IndexError("pop from empty stack")
        node = self._top
        self._top = node.next
        self._size -= 1
        return node.value

    def peek(self) -> T:
        if self._top is None:
            raise IndexError("peek at empty stack")
        return self._top.value

    def __len__(self) -> int:
        return self._size

I want to be honest with you about this one. It is the only implementation that gives you true O(1) push with no amortization caveat — every push allocates exactly one node, no array resizing, ever. But you pay for that by using more memory per element (one pointer per node), by scattering your data across the heap (terrible for cache locality), and by being significantly slower in practice for any realistic workload. The list-backed version wins every benchmark I’ve ever run.

So why learn the linked-list version? Because when an interviewer asks you to build a stack without using any builtins, this is the version. Because when you read about lock-free concurrent stacks, this is the structure they’re built on. And because seeing it once makes the idea of “what is a stack, fundamentally” click in a way the list-backed version doesn’t quite get to. The cupboard is real. The cupboard is made of plates, each one knowing only about the plate below it. That’s all.

When the stack isn’t what you actually want

There is a particular failure mode I want to warn you about, because I’ve watched students hit it and I’ve hit it myself. You learn about stacks, you get excited about how clean and fast they are, and you start trying to use a stack for everything. Then your problem turns out to need “is value X in here?” or “give me the value at position 3” or “insert this in the middle”, and you twist the stack into knots trying to make it cooperate.

Here is the cheat-sheet I wish someone had handed me. When the problem needs one of these things, reach for the structure in the right column, not a stack:

The stack is a beautiful tool, but it is a sharp one. Use it for what it’s for.

Five problems where a stack is the moment of recognition

I want to walk you through five problems. Each one is a classic — they show up in interviews, in textbooks, in real production codebases. But I’m not going to give you a list of solutions. I want to show you the moment in each problem where, if you’ve internalised what a stack is for, you can feel the answer click. The code follows the click. The code is the easy part.

1. Valid Parentheses (LC 20)

The problem: given a string of ()[]{} brackets, tell me if every opener is closed by the matching closer in the right order. So "({[]})" is valid; "(]" is not; "(((" is not; "" is valid.

If you’ve never seen this problem before, try to think about it without reading the next paragraph. What would you do? You might think about counting opens minus closes, but that doesn’t work because it lets "(])" slip through. You might think about regex, but the language of balanced brackets is famously not regular. You might think about recursion, and you’d be right, but there’s a much cleaner mental model.

Here’s the moment. Each time you see an opener, you’ve started a new layer of nesting that has to be closed before anything outside it. Each time you see a closer, it has to match the most recent unclosed opener — not any opener, the most recent one. The most recent one. That phrase — “the most recent thing I haven’t dealt with yet” — is the stack pointing at itself.

So: push every opener you see. When you see a closer, pop and check it matches. If the pop fails (empty stack) or the pop returns the wrong opener, the string is broken. If at the end the stack is empty, the string is balanced. If at the end the stack still has unclosed openers in it, the string is broken in a different way.

Let me walk you through "({[]})" character by character. The diagram below shows the stack after each step. Watch the depth grow as the openers come in, then watch it collapse back down as the matching closers cancel them out.

Steps 1–3 are all pushes — depth climbs to three. Step 4 sees a ], pops [, checks they match. ✓. Step 5 sees }, pops {. ✓. Step 6 sees ), pops (. ✓. Stack is empty. String is balanced.

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    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

Time and space are both O(n). The thing I want you to notice in the code is the return not stack at the end. The case "(((" never triggers a False inside the loop — every character is a valid push. It only fails the balance check at the end, because the stack still has three things in it. Beginners write the inner check correctly and forget the outer one. Don’t be that beginner.

2. Min Stack (LC 155)

The problem: design a stack that supports the usual push, pop, top, and also a get_min() method that returns the current minimum of all values still in the stack — and it has to run in O(1).

The naive idea is to scan the whole stack on each get_min call. That’s O(n) per call. We want O(1). So we need to either store the min somewhere, or maintain a side structure that always knows the answer.

Here is the moment. We’re going to use two stacks in parallel. The main stack holds the actual values. The “min stack” — call it the shadow — always has the current minimum on top. Every time we push to the main stack, we also push to the min stack. Pop both at the same time. The min is always one peek away.

But here is the actual cleverness, the bit that takes some thought to see. When you push a new value to the main stack that isn’t a new minimum, what do you push to the min stack? You can’t push the new value (it would make the new value the “min”, which would be wrong). You can’t skip the push (then the min stack falls out of sync with the main stack, and pop breaks). The answer: you push the previous min again. The min stack repeats its top.

That repetition is the whole trick. It keeps the two stacks the same length, which keeps pop correct, while keeping the running minimum on top of the min stack at all times.

Watch panel 3. We push 7. The main stack now has [5, 3, 7]. The min stack does not push 7 — instead it pushes another 3, because 3 is still the running min. Now if we pop from both stacks, the main stack goes back to [5, 3] and the min stack goes back to [5, 3], and the min is still 3. Synchronisation preserved.

class MinStack:
    def __init__(self) -> None:
        self._main: list[int] = []
        self._mins: list[int] = []

    def push(self, val: int) -> None:
        self._main.append(val)
        # repeat the previous min if val isn't smaller
        self._mins.append(val if not self._mins else min(val, self._mins[-1]))

    def pop(self) -> None:
        self._main.pop()
        self._mins.pop()

    def top(self) -> int:
        return self._main[-1]

    def get_min(self) -> int:
        return self._mins[-1]

All four methods are O(1) — min of two values is constant time, and everything else is just touching the top. Space is O(n), one slot in _mins per slot in _main.

There’s a variant some interviewers prefer where you only push to _mins when the new value is a strict new minimum, and only pop from _mins when the popped main value equals the current min. That saves space on long monotonically-increasing inputs but adds two conditional checks, both of which are easy to get wrong under interview pressure. The “repeat the top” version above is asymptotically identical and impossible to break.

3. Evaluate Reverse Polish Notation (LC 150)

The problem: evaluate an expression written in Reverse Polish Notation. RPN puts operators after their operands, so (2 + 1) * 3 becomes "2 1 + 3 *". The tokens come in as a list of strings. Compute the result.

There is something deeply satisfying about this problem. The first time I worked through it, I remember a small moment of awe — RPN reads strangely, but if you walk through it with a stack you discover it’s been engineered, deliberately, to be evaluated by a stack with no parentheses, no precedence rules, no parsing tree. Just push numbers, and when you hit an operator, eat the top two values and push the result.

"2 1 + 3 *". Push 2 → stack is [2]. Push 1 → [2, 1]. See + → pop 1, pop 2, push 2 + 1 = 3 → [3]. Push 3 → [3, 3]. See * → pop 3, pop 3, push 3 * 3 = 9 → [9]. Done. The final stack has exactly one value, and that value is your answer.

import operator

OPS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": lambda a, b: int(a / b),   # LC 150 wants truncate-toward-zero
}

def eval_rpn(tokens: list[str]) -> int:
    stack: list[int] = []
    for tok in tokens:
        if tok in OPS:
            b = stack.pop()
            a = stack.pop()
            stack.append(OPS[tok](a, b))
        else:
            stack.append(int(tok))
    return stack[0]

Two pitfalls to watch for. First, the operand order on - and /. The second pop is the left-hand operand. The first pop is the right-hand operand. If you reverse them, "3 1 -" (which should give 2) silently passes; "1 3 -" (which should give -2) silently fails. Test with - and / specifically, not + and * — addition and multiplication commute and won’t catch the bug.

Second, the int(a / b) thing. Python’s // operator floors — -7 // 2 == -4 — but LeetCode wants truncate-toward-zero, where -7 divided by 2 is -3. Doing the float divide and casting to int truncates correctly. This is one of those problem-specific gotchas that looks like a bug in your code but is actually a difference between two reasonable definitions of integer division.

4. Asteroid Collision (LC 735)

The problem: each integer is an asteroid moving through space. Positive means moving right; negative means moving left. The absolute value is the size. When a right-mover and a left-mover collide, the bigger one survives (if they’re equal, both explode). Asteroids moving the same direction never collide. Return the asteroids that survive.

This is the problem where I want you to feel the stack as a physics simulator, not just a data structure. The stack holds the asteroids that are still alive and either moving right or already done with their collisions. When a new asteroid arrives moving left, it has to fight its way through whatever is on top of the stack that’s moving right — and the fight has three possible outcomes per round, which is what makes this problem trickier than it looks.

Let me walk the logic. We process asteroids in order. Right-movers (or anything that doesn’t have a fight) just go on the stack. When a left-mover arrives and the top of the stack is a right-mover, they collide. Three cases:

1. The left-mover is bigger. The top of the stack dies. We continue — the left-mover keeps fighting whatever’s now on top.
2. They’re equal. Both die. The left-mover stops, the top is popped.
3. The right-mover on top is bigger. The left-mover dies, the top stays.

There’s a fourth case implicit in all of this: if the left-mover survives and the stack is now empty, or the new top is also a left-mover, then there’s nothing left to fight and the left-mover gets pushed.

def asteroid_collision(asteroids: list[int]) -> list[int]:
    stack: list[int] = []
    for a in asteroids:
        alive = True
        while alive and a < 0 and stack and stack[-1] > 0:
            top = stack[-1]
            if top < -a:           # top destroyed, a continues
                stack.pop()
                continue
            if top == -a:          # both destroyed
                stack.pop()
            alive = False          # a is destroyed (or matched)
        if alive:
            stack.append(a)
    return stack

The time complexity here is O(n), even though there’s a while loop nested in a for loop. That while only runs when an asteroid gets destroyed, and each asteroid can be destroyed at most once over the whole run. Adding up all the iterations of the inner loop across the whole input gives you O(n), not O(n²). This is called amortized analysis, and it’s a recurring theme in stack problems — the outer for-loop bound and the inner while-loop bound don’t compose the obvious way, because the inner loop is constrained by the total number of objects, not by the outer loop’s count.

5. Daily Temperatures (LC 739) — the bridge

The problem: given a list of daily temperatures, return a list where each entry says how many days you have to wait until a strictly warmer day. If no warmer day ever comes, the entry is 0.

The naive solution: for each day, scan forward until you find a warmer day. That’s O(n²). For a million days of input that’s a trillion operations and your laptop catches fire.

Here’s the moment, and this one is, I promise you, the most consequential moment in this entire chapter. Forget the days for a second and think about what you’re really doing. For each day, you’re trying to answer: “when does the first warmer day come?”. If a future day is colder than today, today’s answer is still unknown. If a future day is warmer than today, today’s answer is that day. So today’s answer is settled the moment you find a day that beats today, and not a moment sooner.

That suggests a stack of “days whose answer is still unknown”. We walk the temperatures left to right. When we see a new temperature, we check: does it beat the day on top of the stack? If yes, that day’s answer is today - that day, and we can pop. Repeat — does it beat the next day on the stack? Pop. Repeat until the stack is empty or the top day is warmer than today. Then push today onto the stack.

def daily_temperatures(t: list[int]) -> list[int]:
    n = len(t)
    out = [0] * n
    stack: list[int] = []   # indices, t[stack] strictly decreasing top-down
    for i, temp in enumerate(t):
        while stack and t[stack[-1]] < temp:
            j = stack.pop()
            out[j] = i - j
        stack.append(i)
    return out

Time is O(n) by the same amortized argument as Asteroid Collision: every index is pushed at most once and popped at most once across the entire run. Space is O(n) for the stack.

Two notes. First — and this matters every time you see this pattern — store indices, not values. The moment the problem asks “how many days” or “what position”, you need the index. If you stored values, you’d need a second lookup table to recover positions, which defeats the speed gain. Build the habit now.

Second, the stack here has a special structure I want to name. From bottom to top, the temperatures on the stack are strictly decreasing. Days that haven’t been beaten yet are, by definition, hotter than every day above them in the stack — if they weren’t, those upper days would have already been popped. This invariant — “the stack stays monotonic in one direction” — is its own pattern. It has a name. It solves a whole family of “first greater/lesser thing” problems. And it’s the natural next chapter from this one.

Where to go next

The next thing I’d read is the Monotonic Stack — the pattern that Daily Temperatures is a baby example of. Monotonic stack solves Next Greater Element, Largest Rectangle in Histogram, Stock Span, Sum of Subarray Minimums, and at least a dozen other problems that look superficially different. Same push-and-pop mechanics, plus one invariant.

If you want to keep going with the same shape — “structures with one rule that pays for itself” — the natural neighbours are queues (same shape, opposite end: O(1) at both ends instead of one) and the call stack itself (the runtime is doing exactly this when it tracks your function calls; iterative DFS is just you replacing the runtime’s stack with one of your own).

Stacks show up everywhere once you start looking. Function calls. Undo history. Bracket parsers. Browser back buttons. Compiler expression evaluators. Depth-first search. Memory allocation. The reason is the rule. The rule is what gives you the order, and the speed, and the simplicity. The cupboard is doing more work than the cupboard.