Stack
Push items as they open and pop them as they finish, so the most recent unfinished item is always on top.
Bracket matching, nested or encoded strings, postfix and calculator evaluation, and designs that carry extra state per element (min stack). For next-greater or next-smaller queries, use Monotonic Stack.
Each element is pushed and popped at most once, and each push or pop is O(1), so the scan is linear. In the worst case, such as a string of only opening brackets, the stack holds every element.
A stack is last-in, first-out: the only item you can reach is the most recent one that hasn't been finished yet. That is exactly the shape of nested structure. In Valid Parentheses, the next closing bracket must match the most recently opened bracket that is still open, so you push on every opener and pop on every closer. The string is valid only if every pop matches and the stack ends empty. Decode String works the same way: each '[' saves the text built so far and the pending repeat count, and each ']' pops them to expand the innermost section first. Push and pop are O(1), and each item is pushed and popped at most once, so the whole scan is O(n).
Expression evaluation is the second family. In postfix notation (Reverse Polish), an operator always applies to the two most recent values, so a stack of operands evaluates the expression in one pass: push numbers, and on an operator pop the right operand, then the left, and push the result. Infix calculators extend the idea with a second stack for operators or for the running total saved at each parenthesis. Design problems form the third family. Min Stack keeps a second stack in lockstep that records the minimum at every height, so getMin stays O(1) even after pops. Undo history and iterative depth-first traversal use the same mechanism: an explicit stack standing in for work you will come back to.
This pattern is distinct from Monotonic Stack even though both push and pop. A monotonic stack keeps its contents sorted and pops whenever a new value breaks that order, and each pop answers a "next greater" or "next smaller" question for the popped element, as in Daily Temperatures or Largest Rectangle in Histogram. A plain stack never pops because of value order. It pops because the input says an item is finished: a closing bracket, an operator, or an explicit pop call. If the problem asks for the nearest larger or smaller element, reach for the monotonic variant. If it asks about matching, nesting, or evaluation order, this is the pattern.
Whenever the item you must deal with next is the most recent one still open (the last unmatched bracket, the last two operands, the enclosing section), the problem has last-in, first-out order, and a stack handles each item in O(1) during a single left-to-right scan.
- Popping or peeking an empty stack: a closer with nothing open, like the first character of ")(", must return false instead of throwing.
- Checking that every pop matched but not that the stack is empty at the end, so leftover openers like "((" slip through as valid.
- Popping operands in the wrong order for - and /: the first pop is the right operand. In Python, also use int(a / b) rather than a // b, which floors instead of truncating toward zero.
- Reading a multi-digit number one character at a time, so 12[a] is treated as a stray 1 followed by 2[a]; accumulate digits until a non-digit arrives.
- Mixing up the two stack patterns: a pop-while-smaller loop has no place in a matching problem, and a plain stack can't answer next-greater queries efficiently. Pop because the input closes something, not because of value order.
- Bracket matching: Valid Parentheses, Minimum Remove to Make Valid Parentheses; push openers (or the closers you expect), pop on closers.
- Nested decoding: Decode String, Simplify Path; push the enclosing context at each open, pop and combine at each close.
- Expression evaluation: Evaluate Reverse Polish Notation, Basic Calculator; an operand stack, plus an operator or sign stack for infix input.
- Auxiliary-stack design: Min Stack, Max Stack, Implement Queue using Stacks; carry extra state per element or pair two stacks.
// import java.util.*;
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (/* c opens something */) {
stack.push(c); // or push the context you need to restore later
} else {
if (stack.isEmpty() /* || top doesn't match c */) return false;
stack.pop(); // close the most recent open item
}
}
return stack.isEmpty(); // nothing left openProblems using this pattern
4Easiest first · Blind 75 above NeetCode 150