17.3

Exercises 17.3-6

---

Show how to implement a queue with two ordinary stacks (Exercise 10.1-6) so that the amortized cost of each ENQUEUE and each DEQUEUE operation is O(1).

Answer

First stack is used for ENQUEUE operation, second stack is used for DEQUEUE operation. In ENQUEUE operation, we push the element into first stack. In DEQUEUE operation, if second stack is not empty, pop the elements in the top of second stack. If second is empty, pop all elements in first stack, and push them into second stack. Because this procedure will reverse the order of elements, we can directly pop elements in the top of second stack. Because all elements only push and pop only twice, the amortized cost for eace ENQUEUE and DEQUEUE operation is O(1)