Skip to content
Hari KharelStudy

Stacks

coreCommon atMetaAmazonGoogleBloombergLinkedInRead firstArraysPractise in the Sandbox →

A stack supports push (add on top), pop (remove the top) and peek (look at the top), all O(1). Use it whenever the most recent unfinished item is the one you must deal with next: undo, nesting, backtracking, and “pop while the new item beats the top” scans that run in O(n) total.

The idea in plain words

Section titled “The idea in plain words”

A stack of plates: you put plates on top and take them off the top. You never pull one from the middle. That restriction is the point. Whatever you added last is the first thing you’ll get back (LIFO, last in, first out).

That shape shows up whenever work nests. You open a function call, which opens another, which opens another; they must finish in the reverse order. You type, then undo the most recent edit first. You walk into a maze, and when you hit a dead end you back up to the most recent fork.

In code, a stack is just a dynamic array where you only touch the end. Pushing writes the next slot, popping shrinks the size. Nothing shifts, so both are O(1).

Stack sandbox: last in, first out
sandbox
the stack (top ↑)
4
7
what memory holds: an array + a size
4
7
·
·
·
·
·
·
·
·
0123456789
top
size2
top7
log (newest first)
Nothing yet. Try an operation.

See it

Section titled “See it”

The most useful stack pattern in interviews: for each new item, pop while the top “loses” to it, then push. Here, asteroids fly along a line (sign is direction, size is the number). A left-mover can only hit the most recent surviving right-mover, which is exactly the top of the stack. Edit the input and watch the inner while pop.

Pop while the top loses
step through
5→
10→
←5
8→
←12
3→
←3
←2
01234567
stack (top ↑)
empty
stack size0
total pops0
being processedsurvivesexplodesalready handled
Survivors so far live on a stack. Only the newest survivor (the top) can meet the next asteroid, which is why a stack fits.
1 / 21

When to reach for it

Section titled “When to reach for it”
The problem says… Why a stack fits
nested structure: brackets, tags, function calls, directories The most recently opened thing must close first.
“undo”, “back”, “backspace” Reverse the most recent action first.
“process items, but a new item can cancel or absorb earlier ones” Pop while the top is cancelled, then push. Each item in and out once.
“next greater / previous smaller element” A monotonic stack: a stack kept in sorted order.
depth-first search without recursion An explicit stack replaces the call stack. See DFS.
evaluate or convert expressions Operators and operands wait on stacks until precedence lets them run. See expression evaluation.

How it works

Section titled “How it works”
  1. Read the next item.
  2. While the stack isn’t empty and the top interacts with the new item (cancels, loses, matches), pop and handle it.
  3. If the new item survives, push it.
  4. At the end, the stack holds what’s left, bottom-to-top in arrival order.
survivors.py
def survivors(asteroids: list[int]) -> list[int]:
    """Sign is direction (+ right, - left), size is |x|. Smaller explodes; equal sizes both explode."""
    stack: list[int] = []  # 1. survivors so far, newest on top (the end of the list)
    for a in asteroids:
        alive = True
        # 2. only a left-mover meeting a right-mover on top can collide
        while alive and a < 0 and stack and stack[-1] > 0:
            top = stack[-1]
            if top < -a:
                stack.pop()  # 3. the top loses; keep checking the new top
            elif top == -a:
                stack.pop()  # both explode
                alive = False
            else:
                alive = False  # the incoming one loses
        if alive:
            stack.append(a)  # 4. push the survivor
    return stack




if __name__ == "__main__":
    assert survivors([5, 10, -5]) == [5, 10]
    assert survivors([8, -8]) == []
    assert survivors([10, 2, -5]) == [10]
    assert survivors([-2, -1, 1, 2]) == [-2, -1, 1, 2]
    assert survivors([]) == []
    print("ok")

The simplest case of the same template: the “interaction” is just “a backspace removes the previous character”.

typed.py
def typed(keys: str) -> str:
    """Apply keystrokes where '#' is backspace: 'ab#c' -> 'ac'. Backspace on empty does nothing."""
    out: list[str] = []  # 1. a list used as a stack of characters
    for ch in keys:
        if ch == "#":
            if out:  # 2. guard: popping an empty stack raises IndexError
                out.pop()
        else:
            out.append(ch)  # 3. normal key: push
    return "".join(out)  # 4. bottom-to-top is the typed text




if __name__ == "__main__":
    assert typed("ab#c") == "ac"
    assert typed("ab##") == ""
    assert typed("#a#b") == "b"
    assert typed("a##c") == "c"
    assert typed("") == ""
    print("ok")

Stacks in each language

Section titled “Stacks in each language”
Python TypeScript C#
type list (or collections.deque) Array Stack<T>
push s.append(x) s.push(x) s.Push(x)
pop s.pop(), raises IndexError if empty s.pop(), returns undefined if empty s.Pop() throws if empty; TryPop(out x)
peek s[-1] s[s.length - 1] or s.at(-1) s.Peek() / TryPeek(out x)
empty? not s s.length === 0 s.Count == 0
iteration order bottom → top bottom → top top → bottom (also ToArray())

What it costs

Section titled “What it costs”
Operation Cost
push O(1) amortized (array growth), O(1) for a linked stack
pop / peek O(1)
search for an arbitrary value O(n): a stack isn’t for that
space O(n)

The “pop while” loop looks quadratic, but it isn’t: each item is pushed once and popped at most once, so across the whole input there are at most n pops. Total O(n). It’s the same amortized argument as the sliding window’s left pointer, and interviewers like hearing you make it.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Stack of pairs. Push (value, extra), such as an index or a repeat count, when you need to know where or how many when the item comes back off.
  • Monotonic stack. Keep the stack sorted; popping happens exactly when an element finds its “next greater”. See monotonic stack.
  • Two stacks. A queue from two stacks (amortized O(1) dequeue); undo/redo as two stacks that pass items back and forth. See undo/redo.
  • Explicit DFS stack. Push neighbours instead of recursing. Order differs from recursive DFS unless you push in reverse.
  • Linked-list stack. Push and pop at the head: O(1) worst case, no resizing, used in lock-free stacks.

Pitfalls

Section titled “Pitfalls”
  • Popping or peeking an empty stack. Python raises, C# throws, JS silently gives undefined (which then compares as false everywhere). Guard every pop.
  • Forgetting leftovers. After the loop, items still on the stack are part of the answer (or a sign of invalid input). Check them.
  • C# iteration order. foreach over a Stack<T> and ToArray() go top-first. Reverse if you need arrival order.
  • Using if where you need while. One new item can pop many.
  • Using a list’s front as the top (insert(0, x) / unshift): that’s O(n) per push.

In the interview

Section titled “In the interview”
  • Say why LIFO matches the problem: “Only the most recent unresolved item can interact with the new one, so I keep unresolved items on a stack.”
  • State what the stack holds (values? indices? pairs?) and the invariant it keeps (e.g., “all right-movers on top of all left-movers”).
  • Give the amortized argument for the inner loop.
  • Follow-ups: “what if the input is a stream?” (the stack is the state, fine), “what if it doesn’t fit in memory?”, “can you do it in O(1) space?” (sometimes, with a counter instead of a stack when only one kind of item ever waits).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
A loop pushes each of n items once, and before each push runs `while stack and stack[-1] < x: stack.pop()`. Worst-case total time?
Check yourself
pick one
Your recursive DFS works on the examples but crashes on a 100,000-node path graph in Python. Best fix?

Practice on your own

Section titled “Practice on your own”

Classic textbook exercises, not gym questions:

  • Remove all adjacent duplicate letters repeatedly ("abbaca" → "ca").
  • Decode "3[a2[c]]" → "accaccacc".
  • Implement a FIFO queue using two stacks; argue the amortized cost.
  • In-order traversal of a binary tree without recursion.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Monotonic stack / queueA sorted stack for next-greater questions.
Queues and dequesFirst in, first out instead.
Depth-first searchRecursion, or an explicit stack.
Expression evaluationOperator and operand stacks.