Remember the difference between stacks and queues? Good.

$($a$)$ Describe how to implement a queue using two stacks and $O(1)$ additional memory, so that the amortized time for any enqueue or dequeue operation is $O(1).$ The only access you have to the stacks is through the standard subroutines Push and Pop.

$($b$)$ A quack is a data structure combining properties of both stacks and queues. It can be viewed as a list of elements written left to right such that three operations are possible:

QuackPush$(x)$: add a new item $x$ to the left end of the list;

QuAc$$Pop$()$: remove and return the item on the left end of the list;

QuackPull$()$: remove the item on the right end of the list.

Implement a quack using three stacks and $O(1)$ additional memory, so that the amortized time for any QUACKPUSH, QUACKPoP, or QUACKPULL operation is $O(1).$

In particular, each element in the quack must be stored in exactly one of the three stacks. Again, you cannot access the component stacks except through the interface functions Push and Pop.