Stacks

Last in, first out: the structure behind bracket matching, expression evaluation and the monotonic stack for next greater and next smaller problems.

Overview

What a stack is

A stack keeps items in a pile. You add to the top (push), you look at the top (peek), and you take from the top (pop). The last item you pushed is the first one you get back, so a stack is called LIFO: last in, first out. All three operations cost O(1).

A stack is the right tool whenever the most recent unfinished thing is the one you must deal with next. An opening bracket waits for its closing bracket. A function call waits for the calls it made to return. A day waits for a warmer day.

Push — s.append(x) — s.push(x) — s.push(x) — O(1) amortized
Pop — s.pop() — s.pop() — s.pop() — O(1)
Peek — s[-1] — s.peek() — s[s.length - 1] — O(1)
Is empty — not s — s.isEmpty() — s.length === 0 — O(1)

Popping an empty stack is the classic bug. Python raises IndexError, Java's pop() throws NoSuchElementException while peek() returns null, and JavaScript returns undefined without complaint. Check for empty first.

How to spot a stack problem

Ask what the current element needs. If it needs the most recent earlier element that is still open or still waiting, a stack fits.

Brackets, tags, nested paths — Matching — Openers
Next warmer day, next greater element, histogram — Monotonic — Indices still waiting for an answer
Postfix tokens, calculator — Operand — Numbers (and sometimes operators)
Parentheses that reset a running total, iterative DFS, undo — Saved state — The context to return to

Pattern 1: matching brackets

The rule is short: push every opening bracket, and on a closing bracket the top must be its partner, and you pop it. At the end the stack must be empty. Counting brackets is not enough, because order matters: ([)] has balanced counts but is invalid.

Here is the trace for the valid string {[()]} and the invalid string ([)].

{[()]} — { — push — {
[ — push — { [
( — push — { [ (
) — top is (, pop — { [
] — top is [, pop — {
} — top is {, pop — empty: valid
([)] — ( — push — (
[ — push — ( [
) — top is [, not ( — stop: invalid

Pattern 2: the monotonic stack

A monotonic stack keeps its values in sorted order from bottom to top. Each new element pops every element it breaks the order with, and for each popped element the new one is the answer it was waiting for. Then the new element is pushed.

The trace for Daily Temperatures on [73, 74, 75, 71, 69, 72, 76, 73]: for each day, how many days until a warmer one. The stack holds indices of days still waiting, and their temperatures decrease from bottom to top.

0 — 73 — none — 0:73
1 — 74 — 0 (1 day) — 1:74
2 — 75 — 1 (1 day) — 2:75
3 — 71 — none — 2:75, 3:71
4 — 69 — none — 2:75, 3:71, 4:69
5 — 72 — 4 (1 day), 3 (2 days) — 2:75, 5:72
6 — 76 — 5 (1 day), 2 (4 days) — 6:76
7 — 73 — none — 6:76, 7:73

Days 6 and 7 are still on the stack at the end, so they never see a warmer day and keep the answer 0. The result is [1, 1, 4, 2, 1, 1, 0, 0].

The inner while loop looks quadratic, but it is not. Each index is pushed once and popped at most once, so the total work over the whole array is at most 2n steps: O(n).

Next greater — left to right — decreasing — smaller than current
Next smaller — left to right — increasing — larger than current
Previous greater — left to right — decreasing — smaller than or equal to current; the top after popping is the answer
Previous smaller — left to right — increasing — larger than or equal to current; the top after popping is the answer

Largest Rectangle in Histogram uses both at once. With an increasing stack, when a bar is popped, the current index is its next smaller bar (the right wall) and the new top is its previous smaller bar (the left wall). On [2, 1, 5, 6, 2, 3] the bar of height 5 is popped at index 4 with index 1 below it, so its width is 4 - 1 - 1 = 2 and its area is 10, the answer.

Pattern 3: evaluating expressions

In postfix form (Reverse Polish Notation), every operator comes after its two operands, so no parentheses are needed. Push numbers. On an operator, pop two numbers, apply it, and push the result. The first number popped is the right operand, which matters for - and /.

2 — push — 2
1 — push — 2, 1
+ — pop 1 and 2, push 2 + 1 — 3
3 — push — 3, 3
* — pop 3 and 3, push 3 * 3 — 9

For infix input with parentheses, like 1 - (2 + 3), a calculator keeps a running result and a sign. At ( it pushes the result and sign so far and starts fresh; at ) it pops them and combines. That is Pattern 4.

Pattern 4: saving state before a nested part

When a problem has nested parts, push the context you are leaving, work on the inner part, then pop the context and combine. The table shows what gets saved in common problems.

Basic Calculator — ( — result so far and the sign before ( — )
Decode String — [ — the repeat count and the string so far — ]
Iterative DFS — visiting a node — its unvisited neighbors — taking the next node
Min Stack — every push — the value and the minimum so far — every pop
Undo — every edit — the edit, or how to reverse it — undo

Recursion does the same thing with the call stack. Converting recursion to a loop with an explicit stack avoids hitting the recursion limit on deep inputs.

Picking the stack type in your language

Python — list with append and pop — list.pop(0): O(n), that is a queue; use collections.deque for queues
Java — Deque s = new ArrayDeque<>() — Stack: a legacy class built on synchronized Vector; its docs recommend Deque
JavaScript — an array with push and pop — shift/unshift: they move every element

Java's ArrayDeque does not allow null elements and is not thread-safe. Its docs say it is likely to be faster than Stack when used as a stack.

What you will be able to do

Recognize the four stack patterns from the wording of a problem.
Trace a monotonic stack by hand and explain why it runs in O(n).
Choose the right direction (increasing or decreasing) for next or previous greater and smaller.
Evaluate postfix and parenthesized expressions with a stack.
Pick the right stack type in Python, Java and JavaScript and avoid empty-stack bugs.

When to use it

Validating or matching nested structures: brackets, HTML tags, file paths
Finding the next or previous greater or smaller element for every position
Evaluating postfix expressions or building a calculator
Saving the outer context before handling a nested part
Turning recursion into a loop (iterative DFS) to avoid the recursion limit
Histogram problems: largest rectangle, maximal rectangle, trapping rain water

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio