Stacks: last in, first out — and why that's powerful

01 · Foundation

The LIFO idea

A stack supports exactly two moves: push (add on top) and pop (remove from the top). Nothing else is reachable — you can't grab the item underneath without removing everything above it first. That constraint sounds limiting, but it's precisely what makes a stack the right tool for a specific family of problems: anything where the most recently opened thing must be the first one closed.

Think about matching parentheses in { [ ( ) ] }. The ( that opened last is the one the very next ) has to close — not the { or the [, even though they opened earlier. HTML/XML tags nest the same way: <div><span>...</span></div> — the innermost, most recently opened tag closes first. Undo/redo history behaves identically: the last action you took is the first one "Undo" reverses.

02 · The pattern that shows up everywhere

The monotonic stack pattern

A monotonic stack is a plain stack with one extra rule enforced at all times: the values inside it are kept strictly increasing (or strictly decreasing) from bottom to top. The moment a new element would break that order, you don't just push it on top — you first pop off every element it violates, and each pop usually is the answer for the element being popped.

This is the mechanism behind Next Greater Element: keep a decreasing stack of "elements still waiting for something bigger to show up." When the current number is bigger than the stack's top, that top element has just found its answer — pop it, record the current number as its next-greater value, and repeat until the stack top is bigger than (or the stack is empty), then push the current element. The same shape — pop while a condition holds, then push — also drives sliding-window-maximum-style problems, where the stack (or deque) tracks "candidates that could still be the max of some future window."

03 · Method

A repeatable framework

Work through these five steps, in order, for any "stack-shaped" problem — plain LIFO or monotonic.

1. 1 Confirm it's a stack problemThe tell is "look back until something breaks a condition" — a closing bracket needs the most recent open one, a bigger number invalidates every smaller number still waiting behind it. If you need arbitrary random access into the history, a stack isn't enough.
2. 2 Decide what to storeThe value itself, its index, or both. Store the index whenever you'll later need a distance or gap (e.g. "how many days until a warmer temperature") — you can always look the value up via the index, but you can't recover the index from a bare value.
3. 3 Define the push/pop trigger preciselyWrite the exact condition, e.g. "pop while stack top's value < current value" for a next-greater search. Get the comparison direction and the strict/non-strict boundary (< vs ≤) right — this is where most bugs live.
4. 4 Process left to rightAt each element, apply the pop trigger in a loop (possibly zero times, possibly several) until it no longer holds, then push the current element.
5. 5 Handle what's left at the endAnything still on the stack when the scan finishes never found what it was waiting for — usually that means "no answer" (-1, or "invalid input" for unmatched brackets).

04 · Worked example

Next Greater Element, one index at a time

Array [2, 1, 2, 4, 3]. Stack holds indices (so we can report the answer against the original position), kept decreasing by value. Trigger: while the stack is non-empty and arr[stack.top] < arr[i], pop it and record arr[i] as its next-greater value — then push i.

At index 2, value 2 breaks the order set by index 1's value 1 (1 < 2), so index 1 pops with answer 2, and then index 0's value 2 is not less than 2 (equal doesn't count), so it stays and index 2 gets pushed. At index 3, value 4 is bigger than both remaining stack values (2 and 2), so both pop in the same step. Indices 3 and 4 never get popped by anything — they're still on the stack when the array ends, so their answer defaults to -1.

Final result: NGE = [4, 2, 4, -1, -1]. Open the Next Greater Element visualizer to watch this same trace animate step by step.

05 · Complexity

The amortized O(n) insight

A monotonic stack's code has a while loop nested inside a for loop, which looks like it could blow up to O(n²) in the worst case. It doesn't — and the reason is worth calling out explicitly, because it's easy to misjudge at a glance.

Every index is pushed exactly once across the entire run (the for loop pushes each index a single time), and every index can be popped at most once (once it's off the stack, it's gone for good). So across the whole algorithm, the total number of push operations is n, and the total number of pop operations is also bounded by n — never more than what was pushed. That caps total stack operations at roughly 2n, not n².

06 · A neat trick

Min Stack — an auxiliary-stack trick

A plain stack gives you O(1) access to the top, but not to the minimum — scanning the whole stack for min() every time getMin() is called costs O(n). The fix is to keep a second stack whose job is only to track "what was the minimum at this point in history."

The simplest robust version: whenever you push a value onto the main stack, push a pair (value, min(value, currentMinSoFar)) — so every frame carries a snapshot of what the minimum was at that moment. getMin() just peeks at the top frame's second element, in O(1). Popping is automatically consistent, because the frame beneath always remembers the minimum that was true before the popped value ever arrived — you never have to "recompute" a minimum after a pop.

Try tracing it yourself in the Min Stack visualizer to see the auxiliary stack update in lockstep with the main one.

07 · Before you start coding

Common mistakes

• Storing raw values instead of indices — if you'll need a distance or gap between two positions later (like "days until warmer"), you need the index; a bare value can't give it back to you.
• Getting the pop condition's comparison direction backwards — a decreasing monotonic stack (for next-greater searches) and an increasing one (for next-smaller searches) use opposite comparisons. Mixing them up silently produces wrong answers, not crashes.
• Forgetting that unmatched brackets left on the stack once the scan finishes mean invalid input — checking the stack is empty at the end is part of the algorithm, not an afterthought.
• Assuming a stack alone gives O(1) minimum — it doesn't. Calling min() over the whole stack on every query is O(n) per call; you need the auxiliary min-stack trick to actually get O(1).
• Off-by-one errors translating "the index sitting on top of the stack" back into "the position in the original array" — especially easy to get wrong when the stack holds indices into a different array than the one you're currently iterating.

08 · Practice

Try it in the visualizers

Each card below links to the matching interactive visualizer so you can watch the stack fill and drain in real time.