When should you use a stack?

Interview problems never say "use a stack". You have to recognise the shape of the problem. The good news is that stack problems give themselves away with a handful of signals.

The signals

Matching or nesting. Brackets, HTML tags, [ and ] in an encoded string — anything where the latest opening must close first. (Valid Parentheses, Decode String)
The newest item reacts with the latest survivor. Each new item may cancel, merge with or destroy the item just before it — and then the one before that. (Asteroid Collision, removing adjacent duplicates)
Undo, go back, backtrack. You need to return to the most recent state or choice. (undo, browser history, depth-first search)
Reverse order. Something must come out in the opposite order it went in. (reversing, postfix → prefix)
"The nearest bigger or smaller one". For each element, find the closest element to its left or right that is larger or smaller. This is the monotonic stack, a lesson of its own. (Next Greater Element, Largest Rectangle, Trapping Rain Water)
Operators waiting for operands. Evaluating or converting expressions. (prefix, infix and postfix)

A decision list. Does the most recent item need handling first? Use a stack. Must items be handled in arrival order? Use a queue. Do you need to jump to any position? Use an array. Do you look things up by key? Use a hash map. Do you always need the smallest or largest of everything? Use a heap. — Ask the first question first — it is the stack signal.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 4 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

Worked example: remove adjacent duplicates
When a stack is the wrong tool
A quick self-test
Key takeaways

Prev Next

Mark completed

Was this helpful?

When should you use a stack?

The signals

Keep reading. It's free.

Keep exploring