Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

The idea is to keep one stack empty and one filled with values in head to tail order. Dequeuing is simply a pop of the filled stack and enqueuing can be accomplished by shifting all values from the filled stack to the empty stack, inserting the enqueued value, and then shifting all previous elements back again. In pseudocode:

ENQUEUE(S₁, S₂, x)

1 while !STACK-EMPTY(S₁):

2     PUSH(S₂, POP(S₁))

3 PUSH(S₁, x)

4 while !STACK-EMPTY(S₂):

5     PUSH(S₁, POP(S₂))

DEQUEUE(S₁)

1 return POP(S₁)

DEQUEUE runs in \(\Theta(1)\) constant time. Due to needing to manipulate the entire queue of length \(n\), ENQUEUE runs in \(\Theta(n)\) time.