Show how to implement a stack using two queues. Analyze the runing time of the stack operations.

The idea is to keep one queue empty and one filled with values such that the top of the stack is in the head position. Popping is just a dequeue from the filled queue, and pushing involves shifting all values from the filled queue to the empty, enqueuing the pushed value, and then shifting all previous elements back again. In pseudocode:

PUSH(Q₁, Q₂, x)

1 while Q₁.head ≠ Q₁.tail:

2     ENQUEUE(Q₂, DEQUEUE(Q₁))

3 ENQUEUE(Q₁, x)

4 while Q₂.head ≠ Q₂.tail:

5     ENQUEUE(Q₁, DEQUEUE(Q₂))

POP(Q₁)

1 return DEQUEUE(Q₁)

POP runs in \(\Theta(1)\) constant time. Due to needing to manipulate the entire stack of length \(n\), PUSH runs in \(\Theta(n)\) time.