Stacks in Practice
LIFO in action: matching brackets, evaluating expressions, and the monotonic stack for next-greater-element problems.
On this page
A stack is the simplest useful data structure - add and remove from one end only, last in, first out - yet it unlocks a whole category of interview problems. The tell is almost always "match each thing to the most recent unmatched thing." This lesson covers the classic uses, including the powerful monotonic stack.
LIFO and the Java tools
A stack supports push (add to top), pop (remove from top), and peek (look at the top),
all O(1). In Java, use ArrayDeque as a stack - it's faster than the legacy Stack class:
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // top: 1
stack.push(2); // top: 2
int top = stack.peek(); // 2, without removing
int out = stack.pop(); // removes and returns 2Matching: the bracket problem
The archetypal stack problem is checking balanced brackets. Push every opener; on each closer, pop and verify it matches. The "most recent unmatched opener" is exactly what a stack gives you:
// valid parentheses — O(n) time, O(n) space
boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) stack.push(c); // opener
else if (stack.isEmpty() || stack.pop() != pairs.get(c)) // closer must match top
return false;
}
return stack.isEmpty(); // nothing left unmatched
}Any problem about nesting, undo history, or "process the most recent first" (like DFS, or evaluating an expression) is a stack in disguise.
The monotonic stack
A step up: a monotonic stack keeps its elements in sorted order (increasing or decreasing) by popping violators before pushing. It solves "next greater/smaller element" problems in O(n) - each element is pushed and popped at most once:
// next greater element to the right for each index — O(n)
int[] nextGreater(int[] a) {
int[] result = new int[a.length];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // holds indices, values decreasing
for (int i = 0; i < a.length; i++) {
while (!stack.isEmpty() && a[i] > a[stack.peek()])
result[stack.pop()] = a[i]; // a[i] is the answer for popped indices
stack.push(i);
}
return result;
}Each index enters and leaves the stack once, so despite the inner while, the whole thing is O(n) -
the same amortized argument as the sliding window.
The tell for a stack
Reach for a stack when a problem involves nesting or matching ('valid parentheses,' 'decode a nested string'), needs the most recent element ('undo,' 'backspace'), or asks for the next greater/smaller element or a span (monotonic stack). If you're pairing each item with a recent earlier one, it's a stack.
A stack of plates only lets you add or take from the top - the last plate you set down is the first you pick up. That constraint is exactly what you want for matching brackets: each closing bracket must pair with the most recently opened one still waiting, just as you clear the top plate before the ones beneath. Trying to pull a plate from the middle (or match a bracket to an old, buried opener) would topple the stack - which is precisely the mismatch a bracket-checker rejects.
Given daily temperatures, for each day output how many days you'd wait until a warmer day (0 if none). Explain why a monotonic stack solves this in O(n), and what the stack holds.
What makes a monotonic stack solve 'next greater element' in O(n) despite its inner while loop?
Key takeaways
- A stack is LIFO with O(1) push/pop/peek; use ArrayDeque, not the legacy Stack class.
- The classic use is matching: push openers, pop and verify on closers (balanced brackets).
- Any 'most recent first' problem - undo, DFS, expression evaluation - is a stack.
- A monotonic stack keeps elements ordered by popping violators, solving next-greater/smaller in O(n).
- Store indices (not just values) when you need distances or spans, as in daily temperatures.