Stack Implementations

What is this?

So far you have used a stack as a tool; here you build new gadgets out of stacks. For example, you can make a stack that instantly tells you its smallest value by keeping a second pile of plates that always has the current smallest on top. Or you can build a waiting line (where the first to arrive is the first served) out of two plate-piles facing each other. The trick is doing a tiny bit of bookkeeping on every move so the answer you want is always ready.

flowchart TD A["Build a structure from stacks"] --> B["Keep an extra helper stack"] A --> C["Combine two stacks"] B --> D["Min Stack with instant smallest"] C --> E["Queue made from two stacks"]

💡 Fun fact: Two stacks placed back to back behave like a queue because reversing a pile twice puts it back in its original order — pour from one into the other and the oldest item ends up on top, ready to serve first.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: These are design problems — you don't use a stack to solve a puzzle, you build a data structure out of stacks. The trick each time is an auxiliary structure that maintains an invariant in lockstep with the main stack, so the operation you care about stays O(1).

A different kind of stack problem

Earlier chapters used a stack as a tool. Here the stack is the raw material, and the question is how to compose it into something more capable without losing O(1) speed. Two classic moves:

Track an aggregate alongside the data (Min Stack) — keep a parallel stack of "the min so far" so you never scan.
Compose two primitives into a new ADT (Queue Using Stacks) — turn two LIFO stacks into one FIFO queue with a lazy transfer.

Flowchart: stack-based design branches into augment-with-an-invariant (Min Stack) and compose-primitives (Queue from 2 stacks)

The two problems

Min Stack — O(1) getMin via a parallel invariant

Support push, pop, top, and getMin, all in O(1). The insight: the minimum of a stack is itself a stack — when you pop a value, the min must revert to whatever it was before that value was pushed. So keep a second "min stack" that, in lockstep, always has the current minimum on top.

Min Stack: parallel main and min stacks across push 5, push 3, push 7, pop; min stack keeps 3 on top and falls back to 3 after pop, getMin = min[-1] in O(1)
→ every operation O(1), space O(n).

Queue Using Stacks — FIFO from two LIFOs, amortized O(1)

A stack reversed twice is back in original order — so use an in stack for pushes and an out stack for pops. Pour in → out only when out is empty; that reversal restores arrival order, and each element is moved at most once.

Queue Using Stacks pseudocode: push x appends to in; pop/peek pours in into out only when out is empty (the lazy pour), then returns out.pop() or out[-1], amortized O(1)
Each element is pushed to in once, moved to out once, popped once — three touches total → amortized O(1) per operation.

The cross-cutting skill: maintain an invariant cheaply

Problem	Invariant	Kept by
Min Stack	`min_stack[-1]` = min of all current elements	push/pop the min in lockstep
Queue Using Stacks	`out` (reversed) holds the oldest elements on top	lazy pour only when `out` empties

The pattern is "spend a little work on every mutation to keep an invariant true, so the hot query stays O(1)." Min Stack pays one extra push/pop; the queue pays a bulk pour, but rarely — the heart of amortized analysis.

Where you'll meet it beyond the interview

Running aggregates under undo — a stack of editor states that also reports the cheapest/min state.
ADT adaptation — building the interface you need (FIFO) on top of the primitive you're given (LIFO), the everyday reality of constrained APIs.
Amortized hot paths — deferring a bulk cost (the pour, a resize, a flush) so the common operation stays cheap — the same reasoning behind dynamic-array growth and write buffers.

📓 Draw it yourself

Two parallel stacks. For Min Stack, draw the value stack and the min stack side by side; push a few values (including a new min and a duplicate), then pop the min and watch the min column fall back.
The lazy pour. For Queue Using Stacks, draw in and out; push 3, then pop — draw the one-time pour from in into out (reversing), and note the next pop touches nothing.

Snap photos and embed them with the /host-diagrams skill.

Complexity at a glance

Problem	Per-op time	Space
Min Stack	O(1) all ops	O(n)
Queue Using Stacks	O(1) amortized	O(n)

Key takeaways

These are design problems — build a structure from stacks rather than solving with one.
Min Stack: the min is itself a stack; track it in lockstep for O(1) getMin.
Queue from two stacks: reverse twice via a lazy pour; each element moves once → amortized O(1).
Amortized ≠ per-op: a rare bulk cost (the pour) keeps the common path cheap — be ready to prove it.
Why this chapter matters: it tests whether you can extend and compose data structures and reason about amortized cost — exactly the judgment real systems work demands.

Order: Min Stack (augment with an invariant) → Queue Using Stacks (compose + amortized analysis) → Design Browser History (two stacks as a timeline).

Core idea: A browser's history is just a current page with a stack behind it (pages you can go back to) and a stack ahead of it (pages you can go forward to). Going back pops from one stack and pushes onto the other; visiting a new page pushes the current page onto the back stack and throws the forward stack away — because once you branch off, the pages you'd skipped forward to no longer exist.

Problem, rephrased

You're building the navigation engine behind a browser tab. You start on some homepage, and three things can happen:

Visit a new URL (visit). You leave the current page and land on the new one — and any pages you could have gone forward to are gone, because you just took a different branch.
Back up to k steps (back). You walk backward through the pages you came from, but you can't go past the first page you ever opened. Return the URL you end up on.
Forward up to k steps (forward). You walk forward through pages you previously backed away from, but you can't go past the most recent page. Return the URL you end up on.

Implement the BrowserHistory class:

BrowserHistory(homepage) — start in the browser on homepage.
visit(url) — visit url from the current page; this clears all forward history.
back(steps) — move back up to steps times (stop at the oldest page); return the current URL.
forward(steps) — move forward up to steps times (stop at the newest page); return the current URL.

Both back and forward clamp: if you ask for more steps than exist on that side, you just stop at the end.

Here is a full sequence of operations (LeetCode's Example 1), with [ ] marking the current page:

Call	Returns	History after (current = `[ ]`)
`BrowserHistory("leetcode.com")`	—	`[leetcode.com]`
`visit("google.com")`	—	`leetcode.com [google.com]`
`visit("facebook.com")`	—	`leetcode.com google.com [facebook.com]`
`visit("youtube.com")`	—	`… facebook.com [youtube.com]`
`back(1)`	`"facebook.com"`	`… google.com [facebook.com] youtube.com`
`back(1)`	`"google.com"`	`leetcode.com [google.com] facebook.com youtube.com`
`forward(1)`	`"facebook.com"`	`… google.com [facebook.com] youtube.com`
`visit("linkedin.com")`	—	`… facebook.com [linkedin.com]` (youtube.com dropped)
`forward(2)`	`"linkedin.com"`	already newest — clamped
`back(2)`	`"google.com"`	`leetcode.com [google.com] facebook.com linkedin.com`
`back(7)`	`"leetcode.com"`	clamped at the oldest page

Notice the visit("linkedin.com") row: after forward(1) put us on facebook.com, youtube.com was still ahead of us. Visiting linkedin.com erases it — that forward branch is dead.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Foundations