Building a stack from two queues, which of push or pop do you make O(n), and why must one of them be?

## Why one side has to be linear A queue exposes three primitives: add at the back, remove from the front, and inspect the front. A stack must return the element added most recently. In a queue, that element is at the *back* — the one position the removal primitive cannot reach. The only way to expose it is to remove everything in front of it, one element at a time. There is no arrangement of two queues that avoids this, because no constant number of queue primitives brings a back element to the front while leaving the rest intact. So the linear cost exists; the only question is which operation carries it. ## The two arrangements **Costly push (also called eager rotation).** On insertion, add the new element to an empty queue, then move every element of the main queue behind it, then swap the roles of the two queues. The result is that the queue always holds elements in reverse arrival order, with the newest at the front. Removal and inspection then read the front directly. - push: `Θ(k)` for `k` stored elements - pop: `Θ(1)` - peek: `Θ(1)` **Costly pop (lazy rotation).** On insertion, just add at the back. On removal, move `k-1` elements from the main queue to the second queue, take the one that remains, and swap roles. - push: `Θ(1)` - pop: `Θ(k)` - peek: `Θ(k)` (the same rotation, and the element must be put back or the swap arranged carefully) Note that peek follows pop, not push. A workload that inspects the top frequently without removing is therefore much worse off under lazy rotation than the raw cost table suggests. ## Choosing a side The decision is entirely a function of the operation mix, and it is one of the few places where the answer really is "count your calls": - **Reads and removals dominate** (a small working set repeatedly inspected, a consumer that drains far more often than it fills): pay on push. Every inspection and removal is then constant time. - **Insertions dominate** (a bulk load followed by an occasional inspection): pay on pop. - **Balanced mix**: you lose either way, which is the honest answer and the one that should prompt the question of why a queue is the only available primitive at all. ## The trap: this does not amortize The reflex, having just seen a queue built from two stacks earn an amortized constant bound, is to claim the same here. It is false, and understanding why is the point of the exercise. The two-stack queue amortizes because the expensive pass leaves behind a **reusable** result: after one reversal, many later removals are constant time, and nothing undoes the arrangement. Here, the expensive rotation leaves behind nothing durable. Under eager rotation, the very next insertion has to rotate the whole structure again. Under lazy rotation, the very next removal does. A sequence that alternates insertion and removal pays the full linear cost on every expensive call, giving `Θ(m·n)` for `m` operations — no amortized bound exists, and none can, because there is no per-element ledger where each element pays a bounded number of times. This is the general principle worth taking away: **batching earns an amortized bound only when the expensive pass produces work that later cheap operations consume.** When the reorganisation is destroyed by the next call, batching is just a slower loop. ## The single-queue variant One queue suffices. Add the element at the back, then remove and re-add the first `k-1` elements — after that rotation the new element is at the front and the rest follow in reverse arrival order. Same `Θ(k)` insertion, same constant-time removal and inspection, one less structure to keep in sync. Being able to produce this on request is a good signal, because it shows you understood that the second queue was only ever a scratch buffer. ## What the construction is really testing Nobody builds this. The exercise is a test of whether you can reason from **primitives to achievable costs**: given only one-way access, which operation profiles are reachable, and what does the unavoidable reversal cost? The same reasoning transfers to real work — a log that can only be appended and read forwards, an interface that hands you elements in arrival order, a protocol with no random access — where the question "what does my access pattern make expensive, and can I batch the fix" has exactly this shape.