$3,2$ Stacks $=1$ FIFO Queue

We implement a first$-$in$-$first$-$out $($FIFO$)$ queue using two stacks in the following awkward manner. We

can visualize the two stacks back$-$to$-$back:

Stack #$1$ is used for enqueuing. We push an item on Stack #$1$ to enqueue.

This takes $(1)$ actual time.

Stack #$2$ is used for dequeuing. We pop an item off Stack #$2$ to dequeue.

This takes $(1)$ actual time.

If the Stack #$2$ is empty when we want to dequeue, then we copy everything from Stack #$1$ to Stack

#$2$ by popping each item from Stack #$1$ and pushing the item on Stack #$2.$ This takes $(m)$ actual

time, where $m$ is the $$ number of items moved from Stack #$1$ to Stack #$2.$

Devise an amortized analysis using the accounting method to show that the enqueue and dequeue operations

are $(1)$ amortized time.

Questions:

When do you add credits to the data structure? How many credits do you add?

When do you remove credits from the data structure? How many credits do you remove?

Argue that enqueue takes $(1)$ amortized time in your analysis.

Argue that dequeue takes $(1)$ amortized time in your analysis.