A stack is a Last-In, First-Out (LIFO) container: the last element you put in is the first one to come out. Think of a stack of plates — you add to the top and take from the top. That single rule solves a surprising range of problems because it models the natural idea of “deal with the most recent thing first.”
Scan the problem statement for these trigger signals (from
01-patterns-overview.md):
| Signal in the problem | Stack flavor to reach for |
|---|---|
| “valid parentheses”, “balanced brackets”, “matching pairs” | Plain LIFO stack |
| “next greater / next smaller element”, “days until warmer” | Monotonic stack (decreasing or increasing) |
| “evaluate expression”, “reverse Polish notation”, “postfix” | Operand stack |
| “recent X”, “min/max so far in O(1)”, “design a …” | Auxiliary stack / pair-stack |
| “remove adjacent duplicates”, “backspace compare” | Builder stack |
If you hear any of those phrases, a stack is almost always the cleanest answer.
push(a) push(b) push(c) pop() -> c pop() -> b
| | | | |
a b c b a
a b a
a
top -> c b a
The element on top is always the most recent one still waiting. Two consequences make the pattern powerful:
A string of brackets is valid exactly when the most recent unclosed opener must close first. That is precisely LIFO order:
( [ { goes on the stack — it is “waiting” for its partner.) ] }, the opener it must match is the one on top of the
stack (the most recent unclosed one). If the top doesn’t match, or the stack is
empty, the string is invalid.This is the canonical “most-recent-first” stack use case, and the same idea powers expression evaluation and undo/backspace problems.
The trickiest and most reusable variant is the monotonic stack, used for
“next greater / next smaller” problems (LC 739, 496, 503, 84…). The whole
pattern is: every element gets pushed once and popped at most once, so the total
work is O(n) despite the nested-looking while loop.
function monotonic_stack(values):
initialize an empty stack # stores indices, kept in monotonic order
initialize an answer array of zeros
for i from 0 to length(values) - 1:
# While the current element is the "partner" the stacked elements wait for:
while stack is not empty AND values[i] relates to values[top of stack]:
j = pop top of stack # j is released by i
answer[j] = i - j # (or values[i], or whatever the problem asks)
push i onto the stack # i now waits for its own future partner
# anything left on the stack at the end never found a partner -> default answer (0)
return answer
Two knobs to set per problem:
answer[j] and
compute distance i - j), sometimes the values themselves.Memory aid: the stack is always monotonic in the opposite sense of what you are looking for. Looking for a bigger partner? The stack shrinks downward, waiting for something bigger.
| # | LC | Problem | Difficulty | Teaser |
|---|---|---|---|---|
| 21 | 20 | Valid Parentheses | Easy | The “hello world” of stacks — does every bracket find its partner? |
| 22 | 155 | Min Stack | Medium | Design a stack that returns the minimum in O(1). |
| 23 | 150 | Evaluate Reverse Polish Notation | Medium | Postfix expressions: push operands, pop on operators. |
| 24 | 739 | Daily Temperatures | Medium | “Days until warmer” — your first monotonic decreasing stack. |
| 25 | 22 | Generate Parentheses | Medium | Build all valid bracket strings; open/close counters act like a stack. (Bridge to the Backtracking pattern.) |
The list ramps from the plain LIFO idea (20) through a design problem (155) and expression evaluation (150), into the monotonic variant (739), and finally a generative problem (22) whose open/close counters are the logical equivalent of a stack of unmatched openers — a deliberate bridge to Pattern 10 (Backtracking).
a - b
is not b - a. Always pop into a temp b first, then a, then compute
a op b. Same trap for division.stack.isEmpty() at the end — extra openers mean invalid. In a
monotonic stack, leftover elements mean “no partner found” and must keep the
default answer (usually 0), so initialise the answer array to the right
default rather than leaving garbage.top/peek or pop, guard with
isEmpty(). Popping empty throws (or returns null) and is the #1 source of
crashes.answer[j] and compute distance. Storing the
value loses position.Stack class. In Java prefer ArrayDeque — it is faster
and not synchronized. Declare Deque<T> stack = new ArrayDeque<>(); and use
push / pop / peek.ArrayDeque, not StackThis book always uses
Deque<Integer> stack = new ArrayDeque<>(); // LIFO
stack.push(x); // add to top
int top = stack.peek(); // look at top
stack.pop(); // remove top
java.util.Stack is a legacy, synchronized class kept only for backward
compatibility; ArrayDeque is the modern, faster LIFO/FIFO container (see the
Java crash course, section 4).
Five questions ramping from recall to design. Try each before revealing.
Q1 (recall). In one sentence, what single rule makes a stack the right tool for so many different problems?
Q2 (pattern recognition). A new problem: “given a string, repeatedly delete pairs of adjacent equal letters until none remain” (e.g. abbaca -> ca). Which stack flavor fits?
Q3 (pattern recognition). A new problem: “for each element, find the distance to the NEXT SMALLER element.” Which stack do you use?
Q4 (apply). You evaluate the RPN expression tokens = ["2", "3", "*", "1", "+"]. What is the result?
Q5 (design). Sketch (in words, not code) a stack-based approach to a “baseball game score” problem: ops are an integer (record that score), D (double the previous score), C (invalidate the previous score), and + (record the sum of the previous two scores). The final answer is the sum of all recorded scores.
Next: 0020 - Valid Parentheses — start here.