An UltraStack is an extended stack that supports eight main operations: the standard Stack

operations push$($x$)$ and pop$()$ and the following non$-$standard operations:

$$ get$($i$)$: returns the i $-$th element $($from the bottom$)$ on the Stack.

$$ set$($i$,$ x$)$: sets the value of the i $-$th element $($from the bottom$)$ on the Stack to x$,$ and

returns the element that was previously stored at the same position.

$$ doubleTop$()$: reads the top element x from the Stack and adds a new element $2*$x to the top

of the Stack.

$$ swapTop$()$: swaps the top two elements of the Stack.

$$ max$()$: returns the maximum value stored on the Stack.

$$ ksum$($k$)$: returns the sum of the top k elements on the Stack.

The zip file gives an implementation of UltraSlow, which correctly implements these operations so

that push$($x$),$ pop$(),$ get$($i$),$ doubleTop$(),$ swapTop$(),$ and set$($i$,$ x$)$ each run in $(1)$ time,

but max$()$ and ksum$($k$)$ run in $()$ time. The provided implementation of the UltraFast is just a

copy of UltraSlow implementation.

You must complete the implementation of UltraFast by correctly coding all eight operations and

optimizing their efficiency. For UltraFast, the running time for get$($i$)$ and max$()$ must be $(),$ and

for push$($x$),$ pop$(),$ set$($i$,$ x$),$ doubleTop$(),$ swapTop$(),$ and ksum$($k$)$ running time must not

exceed $().$

You may assume that the Stack elements will be in the range $[-3000000,3000000].$

As part of your implementation, you may use any of the classes in the Java Collections Framework and

you may use any of the source code provided with the Java version of the ODS textbook.

Remember to implement both the size$()$ and iterator$()$ methods. The iterator$()$ method

should return an Iterator that iterates over the values in order, starting from the bottom

and ending at the top of the Stack. Your iterator must support the following two methods:

$$ next$()$ that returns the next element in the iteration.

hasNext$()$ that returns true if this list iterator has more elements when traversing the list in

the forward direction. $($In other words, returns true if next$()$ would return an element rather

than throwing an exception.