Stack

Intuition

A stack is a pile of plates: you can only touch the top one. It supports three operations, all in O(1):

• push: put an item on top,
• pop: remove the top item,
• peek / top: look at the top item without removing it.

This order is called LIFO (last in, first out). Be precise about what it means: among the items currently in the stack, the newest one leaves first. If you push 1, pop it, then push 2 and pop it, the global order looks first-in-first-out, but at every moment the rule "newest present item leaves first" still holds.

The reason stacks show up everywhere is that many problems have the shape "the most recent unfinished thing must be resolved before anything older". An opening bracket waits for its closer, a function call waits for the calls it made, a [ in an encoded string waits for its ]. Whenever the thing you need next is the last pending one, a stack is the natural home for the pending items.

Language notes:

• Python: use a plain list. append pushes, pop() pops, stack[-1] peeks, if stack: checks emptiness. collections.deque also works but is not needed.
• Java: use ArrayDeque (push/pop/peek); avoid the legacy synchronized Stack class.
• C++: std::stack (backed by deque by default) or simply a vector with push_back/pop_back/back.
• Without a dynamic array you can simulate a stack with a fixed array plus a top index: push writes a[++top], pop does top--.

When to use it in interviews / OAs

Look for these signals in the statement:

• Matching and nesting: brackets, HTML/XML tags, nested encodings such as 3[a2[c]], nested lists.
• "Undo the last step": text editors with backspace, browser history, simplifying a path like /a/./b/../c (.. cancels the latest directory).
• Expression evaluation: postfix (reverse Polish) notation is a textbook stack; infix with + - * / and parentheses uses a stack of numbers (and signs or operators).
• Collapsing with the previous element: removing adjacent duplicates, asteroid collisions, merging until a condition stops. Each new element interacts with the latest survivor.
• Turning recursion into iteration: DFS, tree traversals, or any recursion that may exceed Python's default recursion limit (about 1000 frames).
• If the question asks for the next/previous greater or smaller element, you want the specialized monotonic stack (separate article).

Template

Bracket matching is the canonical example: push openers, and every closer must match the most recent unmatched opener.

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            # A closer must match the most recent unmatched opener.
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack  # Leftover openers mean the string is unbalanced.


assert is_valid("([]{})") and is_valid("")
assert not is_valid("(]") and not is_valid("((") and not is_valid("())")

A stack that also returns its minimum in O(1). The trick is to store, next to every value, the minimum of everything at or below it, so popping automatically restores the previous minimum.

class MinStack:
    def __init__(self) -> None:
        # Each entry is (value, minimum of the stack up to and including it).
        self.items: list[tuple[int, int]] = []

    def push(self, x: int) -> None:
        cur_min = min(x, self.items[-1][1]) if self.items else x
        self.items.append((x, cur_min))

    def pop(self) -> int:
        return self.items.pop()[0]

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

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


ms = MinStack()
for x in (5, 2, 2, 7):
    ms.push(x)
assert ms.get_min() == 2 and ms.pop() == 7
ms.pop()
assert ms.get_min() == 2  # The duplicate 2 is still on the stack.
ms.pop()
assert ms.get_min() == 5

Nested structure: when you meet [, save the "outer" state on the stack and start fresh; when you meet ], pop the outer state and combine. This is the general recipe for any bracketed grammar.

def decode_string(s: str) -> str:
    # Stack of (text built before '[', repeat count for the bracket).
    stack: list[tuple[str, int]] = []
    cur, num = "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append((cur, num))  # Save the outer context, start a new level.
            cur, num = "", 0
        elif ch == "]":
            prev, k = stack.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur


assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[ab]3[x]y") == "ababxxxy"
assert decode_string("10[z]") == "z" * 10

Complexity

• push, pop and peek are O(1). With a dynamic array, push is O(1) amortized: an occasional resize copies everything, but the average cost stays constant.
• Space is O(n) for n stored items.
• Most stack algorithms push and pop each input element at most once, so a full pass is O(n) even if an inner while loop pops many items at one step. Use this "each element enters and leaves once" argument in interviews to justify linear time.
• The decoder above is linear in the length of the output (string building dominates).

Common pitfalls

• Popping an empty stack. Always check if stack before pop() or stack[-1]. In bracket matching, a closer arriving at an empty stack means the string is invalid.
• Forgetting the final check. After the scan, leftover openers mean the input is unbalanced: return not stack, not True.
• Using the wrong end. list.pop(0) and list.insert(0, x) are O(n). A stack only touches the end of the list.
• Min stack with duplicates. If you keep a separate stack of minimums, push onto it when x <= current_min (not <), otherwise popping one copy of the minimum loses the other. Storing pairs, as above, avoids the issue entirely.
• Integer division in calculators. Python's // rounds toward negative infinity; problems usually want truncation toward zero, so use int(a / b) (or handle signs explicitly).
• Deep recursion in Python. A recursive DFS on a 10^5-node path graph crashes. Rewrite with an explicit stack instead of raising the recursion limit.
• Storing values when you need indices. Problems like "longest valid parentheses" or anything that measures distances need the stack to hold positions, not characters.

Interview variations

• Valid parentheses and its relatives: minimum insertions to balance, remove the minimum number of invalid brackets, longest valid substring (stack of indices with a sentinel -1).
• Min stack / max stack: the pair trick above; a max stack that also supports popMax needs a heap or ordered structure on the side.
• Evaluate reverse Polish notation: push numbers; on an operator, pop two operands (mind the order: second popped is the left operand).
• Basic calculator: for + - and parentheses, push the running result and sign when entering (; for * / precedence, push signed terms and apply *// to the top immediately.
• Decode string, simplify path, remove adjacent duplicates, asteroid collision, backspace string compare.
• Queue from two stacks and stack from queues (see the queue and deque article).
• Iterative DFS and tree traversals: push the root, then repeatedly pop a node and push its children; for in-order traversal, walk left while pushing, then pop and go right.