Build an order intake queue from two stacks

Question

Orders must be processed strictly in arrival order (first-in-first-out). Using only two stacks (each supporting push and pop from the top), implement a queue with enqueue, dequeue, and peek.

enqueue 1, enqueue 2, enqueue 3
dequeue -> 1
dequeue -> 2

Implement a FIFO queue backed by two LIFO stacks, with amortized O(1) operations.

Accepted Answer

Keep an in stack for arrivals and an out stack for departures. Enqueue always pushes onto in. When you need the front and out is empty, pour the entire in stack into out, reversing the order so the oldest order ends up on top. Each order moves between stacks at most once, so the cost is amortized constant. Tracing: enqueue 1, 2, 3 fills in = [1,2,3]; the first dequeue pours it into out = [3,2,1] and pops 1; the next pops 2. Time O(1) amortized per operation (worst case O(n) on a transfer), space O(n). Edge cases: dequeue/peek on an empty queue raises from the empty pop, guard with empty() fir…

Build an order intake queue from two stacks

Your answer

More Coding questions