125. Why does a two-stack queue have amortized constant-time operations?
MediumStacks
Technical
Show model answer
Use an `inbox` stack for enqueue and an `outbox` stack for dequeue. Enqueue pushes onto `inbox`. Dequeue pops from `outbox`; only when `outbox` is empty, pop every element from `inbox` and push it onto `outbox`, which reverses them so the oldest is on top.
Enqueue is O(1). A single dequeue can be O(n) when it triggers a transfer, but each element is moved at most once, so dequeue is O(1) amortised. Never transfer while `outbox` still has items, or the order breaks.