A Minqueue is an abstract data type $($ADT$)$ that supports the following

operations:

enqueue$($x$)$: Inserts the number x into the Minqueue.

dequeue$()$: Removes the element that has been in the Minqueue for the

longest time.

find$-$min$()$: Returns the smallest value in the Minqueue but does NOT

remove it from the Minqueue.

Your officemate at Millisoft, Dr$.$ Anna Litik, has proposed a clever data

structure for this problem which she calls $$Real Queue and Helper Queue.$$

Here$$s how it works: When an element is enqueued, it is placed into a regular

queue $($implemented as a doubly linked list$).$ However, it is also placed at

the tail of a special $$helper queue$($also implemented as doubly linked list$).$

The helper queue will always contain a subset of those elements in the real

queue in sorted order from small elements at the front to large elements in

the back. In particular, when an element x is inserted at the tail end of the

helper queue, it checks to see if it is smaller than the element right in front of

it in the helper queue. If so$,$ it removes the element in front of it in the helper

queue and again compares itself to its predecessor. It repeatedly removes its

predecessors until it gets to a point that its predecessor is smaller than it$!$

To dequeue, we simply remove that element from the head of the real queue.

We also check to see if it is at the head of the helper queue, in which case

we remove it from that queue as well. Finally, to determine which element

is the minimum, we simply look at the front of the helper queue!

$1$

$($a$.)$ Use the accounting method to prove that the total running time of any

sequence of n operations is O$($n$).($Be careful to account for all of the

work performed by this data structure. Every constant piece of work

should be able to identify a credit that will be used to pay for that

work.$)$

$($b$.)$ Use the potential method to prove that the total running time of any

sequence of n operations is O$($n$).$ Make sure to show that your potential

function starts out at $0$ and remains nonnegative for the entire duration

of its existence!