Exercise 10.1.6

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

Let the two stacks be A and B.

ENQUEUE pushes elements on B. DEQUEUE pops elements from A. If A is empty, the contents of B are transfered to A by popping them out of B and pushing them to A. That way they appear in reverse order and are popped in the original.

A DEQUEUE operation can perform in $\Theta(n)$ time, but that will happen only when A is empty. If many ENQUEUEs and DEQUEUEs are performed, the total time will be linear to the number of elements, not to the largest length of the queue.