Implement a FIFO queue with two LIFO stacks. Prove that enqueue and dequeue are O(1) amortised, then exhibit a sequence of n operations where a single dequeue costs Theta(n) and say when that matters on a latency-sensitive path.

Implement a FIFO queue with two LIFO stacks. Prove that enqueue and dequeue are O(1) amortised, then exhibit a sequence of n operations where a single dequeue costs Theta(n) and say when that matters on a latency-sensitive path.

Approach: Use an inbox stack and an outbox stack, pour one into the other only when the outbox is empty, then count how many times any single element can move.

O(1) amortised for both, with Theta(n) worst case for one dequeue. Push arrivals onto the in stack. On dequeue, if the out stack is empty, pop everything from in and push it onto out, then pop out. Each element is pushed to in once, popped from in once, pushed to out once and popped from out once, so n operations move elements at most 4n times. The potential function Phi equal to twice the size of the in stack gives it directly: an enqueue costs 1 actual and raises Phi by 2 for amortised 3, and a dequeue that pours k elements costs 2k + 1 actual while Phi falls by 2k, so its amortised cost is 1. Taking Phi as the size of the in stack rather than twice it leaves the dequeue at k + 1, which is why the factor of two is needed. Enqueue n items then dequeue once and that single dequeue does Theta(n) work, which is the worst case latency. On a latency-sensitive path the amortised figure is the wrong statistic, since tail latency is what makes a matching engine miss its deadline. A ring buffer gives O(1) worst case per operation instead.

Follow-up: How do you build a queue from stacks with O(1) worst case per operation rather than amortised?

Key concepts: amortised cost, potential function, worst case latency, tail latency.