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).

Queue Using Stacks

Core idea: A stack reversed twice is back in its original order, so pour one stack into another only when the second runs dry and every element gets moved exactly once.

You only have stacks. You need a queue. A stack hands you the last thing you put in; a queue must hand you the first. They are mirror images. The whole puzzle is figuring out how to flip that mirror cheaply.

The problem, rephrased

Imagine a coffee shop with a single narrow tube for order tickets. Tickets can only go in the top and come out the top — that's a stack. But customers must be served in the order they arrived (FIFO). So the barista keeps a second tube. When the serving tube is empty, they tip the first tube into the second: the ticket at the bottom of the first tube (the oldest order) ends up at the top of the second, ready to serve.

We need a MyQueue class with four operations:

Method	Meaning	Queue semantics
`push(x)`	A new customer arrives	add `x` to the back
`pop()`	Serve and dismiss the next customer	remove + return the front
`peek()`	Who's next? (don't serve yet)	return the front, leave it
`empty()`	Any customers waiting?	`True` if no elements

Worked sequence:

Step	Operation	Returns	Queue (front → back)
1	`push(10)`	—	`[10]`
2	`push(20)`	—	`[10, 20]`
3	`peek()`	`10`	`[10, 20]`
4	`pop()`	`10`	`[20]`
5	`push(30)`	—	`[20, 30]`
6	`pop()`	`20`	`[30]`
7	`empty()`	`False`	`[30]`
8	`pop()`	`30`	`[]`
9	`empty()`	`True`	`[]`

Notice the front never changes identity just because we pushed to the back — push(30) at step 5 doesn't jump the queue. That ordering guarantee is exactly what makes this harder than it looks.

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