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.

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

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.

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

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

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

1. 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.
2. 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

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