Stack Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide
Use a stack when the most recent unfinished thing must be handled first — like matching brackets.
3 sub-patterns · 10 questions
What is this pattern?
A stack is a pile: you only ever touch the top. The last thing you put on is the first thing you take off (LIFO — last in, first out). In C++ that's stack<T>, or just a vector / string with push_back, back and pop_back.
The pattern is: things that can't be finished yet wait on the stack, and each new element only ever deals with the most recent unfinished one.
- An opening bracket can't be checked until its closer arrives — and the closer always belongs to the latest open one.
- A number can't be added yet because a
*might come next. - A right-moving asteroid survives until a left-mover hits it — and the left-mover hits the nearest one first.
Whenever "the most recent unresolved thing" is all you need to look at, a stack turns an O(N²) rescan into one O(N) pass: every element is pushed once and popped at most once.
A pile of plates in a cafeteria. You put clean plates on top and take plates from the top. You never pull one out from the middle. Or the Undo button: it always undoes your latest action first, then the one before it.
See it move
Bracket matching on "{[()]()}]". The second track is the stack, bottom on the left, top on the right. The first 8 characters match perfectly; the last ']' has nothing to close.
s = "{[()]()}]"step 1/10- stack size
- 0
Read left to right. Every opener waits on the stack; every closer must match whatever opener is on top right now.
Decode "3[a2[c]]b". The two stack tracks are one stack of pairs: each '[' saves (repeat count, text before it); each ']' pops one and glues the finished inner text back on.
s = "3[a2[c]]b"step 1/11- cur
- ""
- k
- 0
cur is the text of the level we are inside. The stack remembers every outer level we left unfinished.
How do I recognise it?
Brackets, tags or anything nested: "valid parentheses", "decode
3[a2[c]]", "remove the minimum to make it valid".Evaluate an expression:
+ - * /, parentheses, Reverse Polish Notation.Adjacent things cancel or collide: "remove adjacent duplicates", "asteroids moving left and right", backspaces.
Undo / go back:
..in a file path, browser history.Design a structure with an extra O(1) query on top of push/pop (Min Stack).
The brute force keeps rescanning from the start after each deletion or change.
Looks like Stack, but isn't
Still a stack, but the stack is kept sorted and you pop everything a new element beats. That's its own pattern with its own template.
With one bracket type, every ( is the same, so you only need how many are open (open++, open--, never below 0). A stack is needed once there are several types (([)]) or you must know which one is open (its index).
A stack serves the newest item first. If the oldest should go first — tasks in arrival order, levels of a tree — you want a queue.
You can push everything and pop it back reversed, but two pointers from both ends does it in O(1) extra space.
How would I discover it from scratch?
Don't memorise “use stack”. Ask these questions in order — the pattern falls out.
Find one thing that can be resolved (an innermost () pair, two equal neighbours, a *), resolve it, then scan again from the start. Each scan is O(N) and you may need N scans: O(N²).
Sub-patterns
Same core idea, different rule for “valid”. Learn them in this order.
Matching / nesting
4 questionsOpeners wait on the stack until their closer arrives. The closer must match the top. Variants push indices (to delete unmatched ones) or whole saved levels (to decode nested repeats).
Expression evaluation
3 questionsNumbers wait on a stack until their operator can be applied. * and / apply at once; + and - wait to be summed. A ( saves the current result and sign and starts a fresh level.
Stack simulation / design
3 questionsSimulate a process where each new item interacts only with the latest survivor: it may cancel it, be cancelled, or be pushed. Design questions keep extra info in each stack entry.
Don't mix these up
Do you pop because something was matched or resolved (a closer, an operator, a collision)? Plain stack. Do you pop because the new element is bigger/smaller and you want the next greater/smaller? Monotonic stack.
Only one kind of item and you only need how many are open → a counter is enough. Several kinds ((, [, {) or you need which one (its index, its saved text) → stack.
RPN has no precedence to think about: operators come after their operands, so pop two and push one. Calculator II is normal infix, so * must be applied before the + that came earlier.
Same save-and-restore shape. On the opener push what the outer level needs ((result, sign) vs (count, text)), reset, and on the closer combine: saved + sign * inner vs saved + inner × count.
Both compare the new item with the top. Duplicates: equal → both vanish, at most one pop. Asteroids: the bigger one survives and it's a while loop, because one big left-mover can destroy many.
Code templates (C++)
Matching brackets
Two checks people forget: the stack may be empty when a closer arrives, and it must be empty at the end. When you need to delete brackets later, push indices instead of characters.
// Do the brackets match? Openers wait on the stack; each closer must match the top.
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c); // opener: wait for its partner
} else {
if (st.empty()) return false; // closer with nothing open
char open = st.top(); st.pop();
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) return false; // wrong partner
}
}
return st.empty(); // something left open → invalid
}Nested levels (save and restore)
On an opener, push everything you'll need when you come back out (count, text so far, sign, result), then reset the current level. On the closer, pop and combine. Basic Calculator uses the same shape with (result, sign).
// Nested levels (Decode String): on '[' save where you were, on ']' finish the
// inner level and glue it back onto the saved outer level.
string decodeString(string s) {
stack<pair<int, string>> st; // (repeat count, text before '[')
string cur;
int k = 0;
for (char c : s) {
if (isdigit(c)) {
k = k * 10 + (c - '0'); // counts can have many digits
} else if (c == '[') {
st.push({k, cur}); // save the outer level
cur = "";
k = 0; // start the inner level fresh
} else if (c == ']') {
auto [times, before] = st.top(); st.pop();
string inner = cur;
cur = before;
while (times--) cur += inner; // glue inner level onto outer
} else {
cur += c;
}
}
return cur;
}Expression with precedence
Keep the operator before the current number. +/- push a term, *// change the top term right away. The fake + at the end makes sure the last number is processed.
// + - * / with precedence, no parentheses (Basic Calculator II).
// When a number is finished, apply the operator that came BEFORE it.
int calculate(string s) {
vector<long long> st; // terms waiting to be added
long long num = 0;
char op = '+'; // pretend the string starts with '+'
for (int i = 0; i <= (int)s.size(); i++) {
char c = i < (int)s.size() ? s[i] : '+'; // fake '+' at the end flushes the last number
if (isdigit(c)) { num = num * 10 + (c - '0'); continue; }
if (c == ' ') continue;
if (op == '+') st.push_back(num);
else if (op == '-') st.push_back(-num);
else if (op == '*') st.back() *= num; // * and / bind to the latest term now
else st.back() /= num;
op = c;
num = 0;
}
long long sum = 0;
for (long long t : st) sum += t; // only + is left
return (int)sum;
}Collide with the latest survivor
It's a while, not an if: one new item may destroy many on the stack. Write down exactly which pairs interact (here only → then ←) before coding.
// Asteroid Collision: the new item fights the latest survivor until one side wins.
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> st; // survivors so far, as a stack
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !st.empty() && st.back() > 0) { // only → ← collide
if (st.back() < -a) st.pop_back(); // top explodes, keep fighting
else {
if (st.back() == -a) st.pop_back(); // equal: both explode
alive = false; // new one explodes
}
}
if (alive) st.push_back(a);
}
return st;
}