Stack

Core Concepts

Stack — a Last-In-First-Out (LIFO) abstract data type where elements are inserted and removed from the same end (the top). O(1) push, pop, and peek.

LIFO — the most recently pushed element is the first one removed. The defining invariant of a stack.

Top — the element at the accessible end; the only element directly readable or removable.

Underflow — popping or peeking on an empty stack; must be guarded against before every pop in problems where the stack may drain.

Call stack — the OS-managed stack tracking active function calls; each frame holds local variables and the return address. Stack overflow occurs when recursion depth exceeds the call stack limit.

Monotonic stack — a stack maintained under a monotonicity constraint (all elements strictly or non-strictly increasing/decreasing from bottom to top). Enables O(n) solutions to "next greater/smaller element" problems.

See monotonic-stack.md for full coverage of the monotonic stack pattern.

---

Structural Invariants

---

Internal Representation

Array-based (dynamic array) — the standard implementation. The top of the stack is the last element of the array (array[size-1]). Push appends to the end; pop removes from the end. O(1) amortized push because dynamic arrays resize by doubling. Cache-friendly due to contiguous memory. Python list and Java ArrayList-backed implementations use this.

Linked-list-based — a singly linked list with the head acting as the top. Push prepends a new node; pop removes the head. True O(1) worst-case (no resizing). Slightly higher constant due to heap allocation per node and pointer chasing. Used when worst-case O(1) is required or when the stack size is unbounded and resize pauses are unacceptable.

Deque as stack — Python collections.deque and Java ArrayDeque implement double-ended queues; used as stacks by restricting to one end. Java prefers ArrayDeque over the legacy Stack class (which is synchronized and slower).

---

Types / Variants

See monotonic-stack.md for monotonic stack full coverage.

---

Topic-Specific Operations

push(x) — O(1) amortized

Append x to the top. Array-based: array.append(x). Linked-list-based: allocate a new node pointing to the current head; update head. For a min stack, also push min(x, aux_stack.top()) onto the auxiliary stack.

pop() — O(1)

Remove and return the top element. Always check for empty stack first — underflow is the most common stack bug. Array-based: array.pop(). Linked-list: save head value, advance head to head.next, free node.

peek() / top() — O(1)

Return the top element without removing it. Array-based: array[-1]. Does not modify the stack. Guard against empty stack.

isEmpty() — O(1)

Return whether the stack has no elements. Array-based: len(array) == 0. A clean while stack loop in Python relies on this.

getMin() / getMax() — O(1) (augmented min/max stack)

Peek the top of the auxiliary stack that tracks the running min/max. The auxiliary stack must push a new entry on every push to the main stack (not only when a new minimum is reached) so that pops keep the two stacks in sync.

---

Key Algorithms

Balanced Parentheses Matching

Determine whether brackets are correctly nested and closed. Key insight: push open brackets; on close bracket, pop and verify the top is the matching open bracket. Stack is valid iff empty at end. Time O(n), space O(n).

match = {')': '(', ']': '[', '}': '{'}
for c in s:
    if c in '([{': stack.append(c)
    elif not stack or stack[-1] != match[c]: return False
    else: stack.pop()

Next Greater Element (Monotonic Stack)

For each element, find the first element to its right that is strictly greater. Maintain a monotonic decreasing stack of indices. When a new element breaks the monotone property, pop and record: the current element is the answer for the popped index. Time O(n), space O(n).

while stack and nums[stack[-1]] < nums[i]:
    res[stack.pop()] = nums[i]
stack.append(i)

Largest Rectangle in Histogram

Find the largest axis-aligned rectangle that fits within a histogram. Key insight: maintain a monotonic increasing stack of indices. When a bar shorter than the top is encountered, the top bar can no longer extend rightward — pop and compute its rectangle using the current index as the right boundary and the new top as the left boundary. Append a sentinel height 0 at the end to flush the stack. Time O(n), space O(n).

Evaluate Reverse Polish Notation (Postfix)

Evaluate an expression in postfix form. Push operands; on operator, pop two operands, apply operator, push result. Time O(n), space O(n). The stack depth is bounded by the number of operands.

Iterative DFS

Replace the recursive call stack with an explicit stack. Push the start node; while stack is non-empty, pop a node, process it, push its unvisited neighbors. Order of pushing affects traversal order (push right before left to visit left first). Time O(V+E), space O(V).

Decode String (Nested Encoding)

Decode strings like 3[a2[bc]]. Maintain two stacks: one for counts, one for partial strings. On [: push current count and current string, reset both. On ]: pop the multiplier and the prefix string, construct the repeated segment. Time O(n·max_k), space O(depth).

Asteroid Collision

Simulate collisions where right-moving asteroids (positive) explode left-moving ones (negative) of equal or lesser size. Maintain a stack of surviving asteroids. Time O(n), space O(n). The key is that the stack always holds right-moving asteroids at the boundary waiting for incoming left-movers.

Remove K Digits (Greedy via Stack)

Remove k digits from a number string to minimize the result. Maintain a monotonic increasing stack: pop the top whenever it is larger than the current digit and k > 0. After the loop, trim remaining digits from the top if k > 0. Time O(n), space O(n).

---

Advanced Techniques

Monotonic Stack for Range Queries

What it solves: "For each element, find the nearest greater/smaller element to the left or right" in O(n) total instead of O(n²) brute force. Mechanism: A single left-to-right pass with a monotone stack answers all "next greater to the right" queries simultaneously. A right-to-left pass answers "next greater to the left." The stack accumulates elements whose answers have not yet been found; an element is popped (and answered) the moment a qualifying element arrives. When to use over brute force: Any time the problem asks for "nearest" relationships between elements across an array — daily temperatures, trapping rain water, histogram rectangles, stock span. Complexity: O(n) time, O(n) space.

Two-Stack Trick for Queue Simulation

What it solves: FIFO queue using only stack operations, with amortized O(1) per operation. Mechanism: inbox stack receives all enqueues. outbox stack serves dequeues. When outbox is empty and a dequeue is needed, pour all of inbox into outbox (reverses order). Each element moves at most once between stacks. When to use over a deque: Only when the problem constraint explicitly requires "implement queue using stacks." Otherwise use collections.deque. Complexity: O(1) amortized enqueue and dequeue, O(n) worst-case dequeue on a pour.

Auxiliary Stack for O(1) Running Min/Max

What it solves: "Design a data structure supporting push, pop, and getMin in O(1)" — the Min Stack problem and its variants. Mechanism: Maintain a parallel min_stack. On each push of value x, also push min(x, min_stack[-1]) onto min_stack. On each pop, pop both stacks simultaneously. getMin() peeks min_stack[-1]. When to use over rescanning: Whenever minimum/maximum must be maintained under arbitrary pops, not just monotone updates. A simple variable tracks the current min but cannot restore the previous min after a pop — the auxiliary stack is the only O(1) solution. Complexity: O(1) all operations, O(n) extra space.

Stack-Based Iterative Tree Traversal

What it solves: Eliminates recursion for in-order, pre-order, and post-order traversal, preventing stack overflow on deep trees and enabling early termination. Mechanism: Pre-order: push root, then repeatedly pop-process-push(right)-push(left). In-order: push nodes while going left; pop-process-go-right. Post-order: either reverse of modified pre-order (push left before right, then reverse result), or a two-stack approach. When to use over recursion: Trees with depth up to 10⁵ where Python's recursion limit (1000) or Java's call stack size would overflow. Also for kth-element early-exit (stop after k pops without traversing the rest). Complexity: O(n) time, O(h) space where h = tree height.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Underflow on pop/peek — popping or peeking an empty stack is the most common runtime error in stack problems. Always guard with if not stack before accessing. Problems like "valid parentheses" must return false, not crash, when a close bracket arrives and the stack is empty.

• Stack not empty at end — a valid-bracket check must verify len(stack) == 0 after processing all characters. Unclosed open brackets leave the stack non-empty; returning just True because no crash occurred is wrong.

• Monotonic stack index vs. value — in next-greater-element problems, storing indices is almost always better than storing values, because you need to record the answer for each position. Storing values loses position information.

• Sentinel (dummy) element omission in histogram — without appending a sentinel height 0, elements remaining in the stack after the loop are not processed. They represent rectangles extending to the right boundary; the sentinel forces their computation.

• Min stack sync on pop — the auxiliary min stack must be popped on every main stack pop, not only when the popped value equals the current minimum. Failing to sync produces a stale minimum after pops.

• Two-stack queue empty dequeue — when outbox is empty and inbox is also empty, dequeue must raise an error or return a sentinel. Forgetting to check inbox when outbox is empty causes incorrect "empty queue" reports.

• Off-by-one in "span" problems — the stock span (number of consecutive days ≤ today's price) is i - stack[-1] where stack[-1] is the last index of a day with a strictly greater price, not the index of the previous day. Using i - stack[-1] - 1 or i - stack[-1] + 1 is wrong.

• Popping the wrong element in bracket matching — a common mistake is checking stack[-1] without actually popping it on a close bracket. The check and the pop must both happen on every close bracket.

• Global vs. local counter in decode string — when nesting is involved (3[a2[bc]]), resetting the current number after pushing it onto the count stack (and resetting the current string after pushing it onto the string stack) is mandatory; forgetting to reset means the inner value bleeds into the outer.

---

Implementation Notes

• Python: use list as a stack — append() for push, pop() for pop, [-1] for peek. Never use list.insert(0, x) or list.pop(0) — these are O(n).
• Python: if not stack is idiomatic for the empty check; while stack for drain loops.
• Java: prefer ArrayDeque over the legacy Stack class. Stack extends Vector and is synchronized (slow); ArrayDeque is faster and not thread-safe (which is usually fine).
• Java ArrayDeque as stack: push()/pop()/peek() all operate on the head (LIFO); offer()/poll()/peek() operate on the tail (FIFO). Use the stack API consistently.
• Python recursion depth limit is 1000 by default — iterative DFS via explicit stack avoids RecursionError on deep trees or graphs.
• When storing tuples in a Python stack for state (e.g., (node, index) for iterative traversal), named tuples or dataclasses improve readability.
• Stack space for DFS is O(h) (tree height / DFS depth), not O(n) — on a balanced tree this is O(log n), but on a skewed tree it is O(n), the same as recursion.

---

Cross-Topic Relations

See monotonic-stack.md for the full monotonic stack pattern. See depth-first-search.md for iterative DFS patterns.

---

Interview Reference

Must-Know Problems

Bracket Matching

• Valid Parentheses (Easy) — canonical push/pop
• Minimum Add to Make Parentheses Valid (Medium)
• Longest Valid Parentheses (Hard) — stack of indices
• Remove Invalid Parentheses (Hard) — BFS or stack-based pruning

Next Greater / Smaller Element

• Next Greater Element I (Easy) — hash map + monotonic stack
• Next Greater Element II (Medium) — circular array; double the array or use mod
• Daily Temperatures (Medium) — return days until warmer temperature
• Online Stock Span (Medium) — monotonic stack with accumulated span

Histogram and Area

• Largest Rectangle in Histogram (Hard) — monotonic increasing stack + sentinel
• Maximal Rectangle (Hard) — reduce to histogram row by row
• Trapping Rain Water (Hard) — monotonic stack or two-pointer

Expression Evaluation

• Evaluate Reverse Polish Notation (Medium)
• Basic Calculator II (Medium) — handle +, -, *, / with precedence
• Basic Calculator (Hard) — handle parentheses; recursive or stack of partial results

String Manipulation

• Decode String (Medium) — two stacks (counts and strings)
• Remove All Adjacent Duplicates in String (Easy)
• Remove All Adjacent Duplicates in String II (Medium) — (char, count) stack
• Simplify Path (Medium) — split on /, stack of directory names
• Backspace String Compare (Easy) — simulate # with stack

Greedy via Stack

• Remove K Digits (Medium) — monotonic increasing stack with budget
• Remove Duplicate Letters (Medium) — smallest lexicographic result; monotonic stack + seen set
• 132 Pattern (Medium) — monotonic stack with running min

Design

• Min Stack (Medium) — auxiliary min stack
• Implement Queue Using Stacks (Easy) — two-stack simulation
• Design Browser History (Medium) — two stacks (back, forward)

Additional LeetCode Coverage

• Baseball Game (LC 682)

Clarification Questions to Ask

• Are there only parentheses, or also [, ], {, }? (Affects the bracket-match lookup table)
• Can the stack be empty when pop/peek is called? (Underflow handling)
• Is "adjacent duplicates" removal applied iteratively until no change, or just one pass? (Changes whether a stack or a loop is needed)
• What should be returned if the string is empty or already valid?
• Is the histogram guaranteed to have non-negative heights? (Affects sentinel choice)
• Can heights be zero in the histogram? (Zero-height bar splits the rectangle; stack must handle it)
• For expression problems: are there spaces? Negative numbers? Parentheses? (Each adds a case to the parser)

Common Interview Mistakes

• Not checking for empty stack before pop() or peek() — crashes on problems where the stack may fully drain.
• Returning True from bracket matching without checking len(stack) == 0 — open brackets at the end go undetected.
• Storing values instead of indices in the monotonic stack — loses position information needed to compute distances or spans.
• Forgetting the sentinel in histogram problems — bars remaining in the stack at end of loop are never processed.
• In min stack: popping only when the value equals the current min, rather than on every pop — the auxiliary stack falls out of sync.
• In decode string: not resetting current_num and current_str after pushing them onto their stacks — inner values bleed into outer scope.
• Using a deque/list as a queue (popping from index 0) inside a stack problem, accidentally introducing O(n) operations.

Typical Follow-Up Escalations