Problem $3($Stacks and Queues, $10\%)$

It is possible to implement a queue using two stacks stack$1$ and stack$2,$ by implementing the functions in the following manner:

enqueue $($x$)$: push x on stack$1.$

dequeue $()$: if stack$2$ is not empty, then pop from it$.$ Otherwise, pop the entire contents of stack$1,$ pushing each one onto stack$2.$ Now pop from stack$2.$

As always, explain your answers thoroughly.

Part $($a$)$

Starting with an empty queue, indicate the contents of stack$1$ and stack$2$ 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 stack.push$()$ and stack.pop$()$ run in O$(1)?$

Part $($c$)$

What is the amortized runtime per function call $($i$.$e$.$ the worst$-$possible average runtime if you make n calls to some sequence of enqueue and dequeue$)?$ Note that dequeue can only be analyzed jointly with enqueue.

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?