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 (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)?