A quack is an abstract data type that is part queue and part stack.

Specifically, a quack supports the following operations:

$$ Push$($x$)$ takes a value x and puts it at the $$top$$ of the stack;

$$ Pop$()$ removes and returns the element at the $$top$$ of the stack; and

$$ Dequeue$()$ removes and returns the item at the $$bottom$$ of the stack

$($the element that has been in the stack the longest$).$

Millisoft would like to implement a quack using only three stacks. However,

in order to conserve memory and energy, each item can only appear on one

of the three stacks at any given time!

a$.$ Describe an algorithm that implements a quack using three stacks such

that any sequence of n operations takes a total of O$($n$)$ time. Although you

are limited to three stacks, you may use a constant number of additional

variables $($e$.$g$.,$ counters$).$ You don$$t need to do the amortized analysis

in this part, just describe the algorithm. $($Generally$,$ you don$$t need to

analyze counters you use for this problem.$)$

b$.$ Prove that your algorithm takes O$($n$)$ time for any sequence of n opera$-$

tions using an accounting argument. That is$,$ define constant amounts of

credits charged for each of the three operations, and describe an invariant

about these credits such that all work is paid for across any sequence of

n operations.

$1$

c$.$ Prove that your algorithm takes O$($n$)$ time for any sequence of n oper$-$

ations using a potential argument. That is$,$ define a potential function,

show that it starts at zero and never goes negative, then show that the

amortized cost for all three operations is bounded by a constant.