Background:

It is possible to implement a queue using two stacks stack1 and stack2, by implementing the functions in the following manner:

• enqueue (x): push x on stack1.
• dequeue (): if stack2 is not empty, then pop from it. Otherwise, pop the entire contents of stack1, pushing each one onto stack2. Now pop from stack2.

Part (a)

Starting with an empty queue, indicate the contents of stack1 and stack2 after EACH of the following operations have occurred. Clearly indicate the top and bottom of each stack:

• enqueue 1
• enqueue 2
• dequeue
• enqueue 3
• enqueue 4
• dequeue
• enqueue 5
• enqueue 6

Part (b)

What is the worst-case runtime of enqueue(x) and dequeue(), assuming push and pop of the stack data structure run in O(1).

Part (c)

What is the amortized runtime per function call (i.e. amortized runtime of both enqueue(x) and dequeue(), as applicable)? Again assume push and pop of the stack data structure run in O(1).

Part (d)

Suppose the underlying stack structure is poorly implemented, with push(x) taking (1) time, and pop() taking (n) time, where n is the number of elements in the stack. Now what is the worst-case runtime of enqueue(x) and dequeue()? What is the amortized runtime per function call (i.e. amortized runtime of enqueue(x) and dequeue(), as applicable)?