← All patternsStack for Matching and Undo · template
Pattern · Stacks & Queues
Stack for Matching and Undo
Push openers and pop when the matching closer arrives; anything left over or mismatched is an error.
Time O(n) · Space O(n)
Taught in Module 9: Stack and Monotonic Stack
Think of it like this
A stack of plates: the last plate you put down is the first you pick up, just like the last bracket opened must close first.
Clues that point here
- → Brackets or tags that must match
- → Undo / backspace behaviour
- → Evaluate expressions
- → Nested structures
Not this pattern when
- ✕ Order of arrival should be preserved (queue)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') stack.push(c);
else {
if (stack.isEmpty() || !matches(stack.pop(), c)) return false;
}
}
return stack.isEmpty();Common versions
- Valid parentheses
- Min stack
- Evaluate reverse Polish notation
- Decode string
- Backspace string compare
Practice problems with this pattern
9.1Valid ParenthesesEasymain pattern9.3Evaluate Reverse Polish NotationMediummain pattern9.4Decode StringMediummain pattern9.2Min StackMediumalso uses it10.2Implement Queue Using StacksEasyalso uses it13.6Generate ParenthesesMediumalso uses it