Stacks — LIFO for "remember the recent past"

A stack is a Last-In-First-Out queue. In Python it's just a list — append to push, pop() to pop. Both are O(1).

Three classic patterns

1. Matching / balancing

Every open thing (paren, tag, quote) pushes onto the stack. Every closer must match the top of the stack. Balanced brackets, HTML/XML validation, expression evaluation.

2. Undo / history

Every state change pushes a snapshot. Undo pops. Used by editors, transactions, recursive descent parsers.

3. Monotonic stack (the interview trick)

Maintain a stack that stays monotonic (increasing or decreasing). Before you push, pop everything that violates the invariant. Solves in O(n) problems that look O(n²):

• Next greater element
• Largest rectangle in a histogram
• Daily temperatures
• Trapping rain water (harder variant)

Why monotonic stacks work

Each element enters and leaves the stack at most once. Total work is O(n) even though there's a nested loop. Amortized analysis is the interview's favorite gotcha.

Common bugs

• Pop-then-check. Order matters — check the top before popping.
• Empty stack access. Guard if stack: before stack[-1].
• Confusing stack of values vs indices. For "find the position of the next greater," store indices, not values.

Try it

1. Given a string s = "a(b(c)d)e", return the parenthesised substrings — ["(b(c)d)", "(c)"].
2. Implement daily_temperatures(temps) — for each day, days until a warmer temperature.