Overview
A stack only lets you touch its top: push adds, pop removes, peek looks. That restriction is exactly what you want whenever the most recent unfinished thing must be resolved first — an opening bracket waiting for its partner, an operator waiting for its operands, a function call waiting to return.
The most powerful stack trick is the monotonic stack: a stack kept in increasing or decreasing order by popping anything that breaks the order before pushing. Each pop is the moment an element meets its "next greater" (or smaller) neighbour. Because every element is pushed and popped at most once, problems that look O(n²) — daily temperatures, largest rectangle in a histogram — fall to O(n).
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| push / pop / peek | O(1) |
| Monotonic stack over n elements | O(n) total — each element pushed and popped once |
Patterns to recognise
Match and cancel
Use it for: Valid parentheses, asteroid collision, removing adjacent duplicates.
Push; when the new item cancels the top, pop instead.
Next greater / smaller
Use it for: Daily temperatures, stock span, next greater element.
Store indices; pop while the current value beats the top, answering each popped index.
Nested structure
Use it for: Decode string, basic calculator.
Push the current context when you enter a bracket; pop and combine when you leave it.
Code template
def daily_temperatures(temps):
answer = [0] * len(temps)
stack = [] # indices; temperatures decreasing
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j # i is j's next warmer day
stack.append(i)
return answer
vector<int> dailyTemperatures(const vector<int>& temps) {
vector<int> answer(temps.size(), 0);
vector<int> stack; // indices; temperatures decreasing
for (int i = 0; i < (int)temps.size(); ++i) {
while (!stack.empty() && temps[stack.back()] < temps[i]) {
int j = stack.back();
stack.pop_back();
answer[j] = i - j;
}
stack.push_back(i);
}
return answer;
}
Common mistakes
- Popping or peeking an empty stack — check before you touch the top.
- Storing values when you later need positions; push indices and look values up.
- Strict (<) vs non-strict (<=) comparisons change how duplicates are handled.
Quick check
Three questions on Stacks. Get all three right to earn +15 XP.
-
A stack removes elements in which order?
The most recently pushed item is the first one popped.
-
When checking balanced brackets, what do you do on reading a closing bracket?
The most recent unclosed opener must be the matching one.
-
A monotonic stack solves "next greater element" for all n items in:
Each element is pushed once and popped at most once.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Valid ParenthesesLeetCode Easy +20
- Min StackLeetCode Medium +40
- Evaluate Reverse Polish NotationLeetCode Medium +40
- Daily TemperaturesLeetCode Medium +40
- Decode StringLeetCode Medium +40
- Asteroid CollisionLeetCode Medium +40
- Largest Rectangle in HistogramLeetCode Hard +70
- Basic CalculatorLeetCode Hard +70
Stuck on Stacks?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor