Stack Patterns

Beginner · 16 min read · Problem-Solving Patterns, Stacks & Queues

Matching brackets, evaluating expressions and simulating undo.

A stack is the simplest data structure there is — push on top, pop from top — and that's exactly why people miss it. The signal is nesting or "the most recent thing matters most": brackets inside brackets, an operation that undoes the previous one, an expression where the last operator seen decides what happens next.

The idea: the newest open thing must close first

Step through it. Each opener puts the closer it needs on top of a pile of plates; a closer must match the top plate. Try the broken examples to see the three ways it can fail.

Worked problems

Removing bb makes the two as adjacent — the "most recent survivor" is what matters. A stack of survivors handles chains of removals in one pass:

Practice ladder

Interview questions

• How do you design a stack that returns its minimum in O(1)?
• When does a problem call for a stack?

Further reading

Key takeaways

• Stacks handle nesting and "most recent first": matching, cancelling, undo, parsing.
• Push the expected closer to make bracket matching a single comparison; check empty both mid-scan and at the end.
• Store extra state per entry (the running minimum) or store indexes instead of values.
• Two stacks (counts + saved context) replace recursion for nested decoding.

Previous: In-Place Reversal & Dummy Nodes · Next: Monotonic Stack & Queue