← Stacks · guided lesson
Stacks & Monotonic Stack
the story
Stack (last in, first out)
Every tool here exists because something was too slow or broke without it. Here is what.
In Munich, from 1955, Bauer and Samelson wanted to translate formulas like a × (b + c) into machine code in one left-to-right pass. Their trick: put each operator that can't run yet into a "Keller" (German for cellar) and take out the most recent one first. They filed a German patent on this principle on 30 March 1957, and described it in English in "Sequential formula translation" (CACM, 1960). Bauer's 1988 IEEE Computer Pioneer Award reads simply: "For computer stacks."
the problem it solved
Translating formulas with nested parentheses and operator precedence in one left-to-right pass, by postponing each operator until it can be applied.
why it matters: without it
Every "most recent first" job — nesting, undo, method calls — would need its own bookkeeping, and bracket checks would be quadratic.
sources: Bauer & Samelson — German patent DE 1094019 (filed 30 March 1957) ↗ · Samelson & Bauer — Sequential formula translation (CACM, 1960) ↗ · IEEE Computer Society — Friedrich L. Bauer, Computer Pioneer Award ↗ · Wikipedia — Stack (abstract data type): History (the 1955 "Operationskeller" proposal) ↗
also in this chapter: Reverse Polish notation & the operand stack · Monotonic stack · ArrayDeque (and why not java.util.Stack)
the idea
The idea in 30 seconds
A stack only lets you touch the top: push adds there, pop removes from there, peek looks there. All O(1).
Use it whenever the most recent unfinished thing must be handled first: an open bracket, a pending number, a function call.
A monotonic stack keeps its items sorted, so each new item instantly answers "who was waiting for something bigger (or smaller) than me?"
picture this
Ctrl+Z in your editor. Every change is pushed onto an undo stack; Ctrl+Z pops the most recent one. To undo the change you made three steps ago, you must first undo the two that came after it.
watch it
Push, pop, peek — and what happens in memory
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Push, pop, peek — and what happens in memory
Top: the backing array and the `size` index. Bottom: the stack you reason about. Watch the array double when it fills up.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Matching brackets with a stack
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Matching brackets with a stack
Every closer must match the most recent unmatched opener — exactly what the top of the stack holds.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
LIFO — last in, first out. push, pop, peek, isEmpty are all O(1); searching inside is O(n) and almost never needed.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
In Java, use Deque<Integer> stack = new ArrayDeque<>(). Not the legacy Stack class (it extends Vector, is synchronized, and iterates bottom → top).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
An array-backed stack is just an array plus a size index. Doubling the array when full keeps push O(1) amortized.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Matching / nesting problems (brackets, tags, k[...], paths with ..): push when something opens, pop when it closes.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Monotonic stack: before pushing x, pop everything that x "beats". Each popped item has just found its answer — x.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Each element is pushed once and popped at most once, so a while inside a for is still O(n) in total.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Store indices, not values, on a monotonic stack — you can always read the value, and you'll need the index for distances and widths.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Recursion is a stack (the call stack). Any recursive DFS can be rewritten with an explicit Deque when depth might overflow.
spot the pattern
When you see this, think this
Brackets, tags or anything that opens and closes and can nest
Push openers; a closer must match the top
"Next greater / smaller", "how many days until warmer", "nearest taller to the left"
Monotonic stack of indices
Largest rectangle, maximal area under bars, "span" of a value
Increasing monotonic stack; measure when a bar is popped
Postfix / prefix expression, calculator, "evaluate"
Operand stack (plus an operator stack for infix)
+5 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Calling
pop()orpeek()on an empty stack. CheckisEmpty()first — a lone)or]is the classic test case. - Using legacy
java.util.Stackand then iterating it expecting top-first order. It iterates bottom → top.
quick check
One question. No pressure.
You push 1, 2, 3, then pop once, then push 4. What does peek() return?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Valid Parentheses
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Which stack operations are O(1), and what is slow?
Question 1: Which stack operations are O(1), and what is slow?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.