What it is
A stack holds elements so that only the most recently added one is ever accessed or removed next. That single property — last in, first out — is exactly what you need whenever a problem has a notion of "nesting" (brackets, recursive groups, function calls) or "the most recent thing takes priority" (undo history, the last operator in an expression). Most solutions in this hub are a single pass over the input with one stack, pushing when you open something or make progress, and popping when something closes or resolves.
When it applies
- The input has nested or matched structure — brackets, parentheses, an encoding with repeat groups — and you need to know what the "current" open context is at each point.
- You're parsing an expression left to right and need to defer applying an operator until you know what comes after it (or need to hold intermediate results while resolving precedence).
- An action needs to be undoable, and undoing always means reversing the single most recent change, not an arbitrary earlier one — that's a stack of history entries, not a list you search through.
- Needing access to both ends of the sequence (the oldest and the newest) is something a stack alone won't do — reach for a deque or two stacks instead. And when order of processing doesn't actually matter (you just need membership or counts), a stack adds nothing over a set or a running variable.
Tells in the problem
- Matched or nested bracket characters, or a phrase like "well-formed," "balanced," or "closes in reverse order."
- An expression to evaluate with operator precedence or parentheses, especially "no built-in evaluator allowed."
- "Repeat this segment k times," where segments can nest inside each other.
- "Undo and redo," where only the single most recent action can be reversed at any moment.
- Comparing each element against a running "most recent unresolved" value — the next greater element, the next collision, the next thing this one interacts with.
The classic mistake
Popping from the stack without first checking it's non-empty, or without checking that what's on top actually matches what's expected, is the error interviewers report most — this crashes or silently returns the wrong answer on inputs like a lone closing bracket or a stray unmatched operator that a hasty test case never exercised. It happens because the "happy path" of the pattern (open something, later close it) is where all the attention naturally goes, while the failure paths (something closes with nothing open, or the wrong kind of thing is open) get treated as edge cases to handle "later." Catch it by writing the empty-stack and mismatch checks in the same breath as the pop, not as an afterthought once the main logic works.
Questions to start with
- Valid Parentheses — the cleanest version of the matching-and-mismatch check that every other stack question builds on.
- Min Stack — a stack that tracks extra state alongside each element rather than just the elements themselves.
- Evaluate Reverse Polish Notation — the stack holds operands waiting for an operator, the core idea behind expression evaluation.
- Decode String — nested repeat groups, where you push a partial result each time you enter a bracket and combine it back on the way out.
- Basic Calculator — full operator precedence and parentheses together, the most demanding expression-parsing question in this hub.