IN PYTHON

PROBLEM STATEMENT:

In today$$s Lab we will explore ways to design a Queue with O$(1)$ lookup time of the Maximum

element.

You will solve the problem as stated below:

Here you will Maintain two Queues $-$ a Main Queue and a Queue holding the Maximum value$($s$)$

from the Main Queue $($AKA Max Queue$).$ The Main Queue contains the elements. The Max

Queue contains the elements with Maximum value. The Max Queue would have to be a double

ended Queue as you would like to be able to remove elements from both ends.

Example:

Let$$s say we have the following:

We add an integer $1$ into our Main Queue and I hope it is really obvious that when the Main

Queue contains a single element, the Max Queue can be popu$-$ lated without confusion :$)$

Main Queue: $1$ front of Queue

Max Queue : $1$ front of Queue

Now, let$$s say we insert a $4$ into the Main Queue. the Main Queue will look as follows:

Main Queue: $4->1$ front of Queue

In the Max Queue, we don$$t need $1$ anymore, since $1$ can never be the Max of this Queue now.

So we remove $1$ and insert $4.$

Main Queue: $4->1$ front of Queue

Max Queue: $4$ front of Queue

Say we insert $2$ into the Main Queue. We know $2$ is not the Max, but it can be the Max if we de$-$

Queue $1$ and $4$ from the Queue. So$,$ we insert it onto the Max Queue:

MainQueue:

This is because elements $<mtext\; id="EditorElement\_101373"></mtext><mn\; id="EditorElement\_101374">3</mn>$ could never be Max after $3$ is inserted. What I stated above is

exactly the algorithm for inserting an element in the Max Queue.

To lookup the Maximum Value $($AKA Max$),$ we just check the front of the Max Queue which

ensures O$(1)$ lookup time.

While de$-$queuing elements, we check if they are equal to the front of the Max Queue,and if so$,$

we de$-$Queue from the Max Queue too. For example, after de$-$queuing $1,$ lets say we want to de$-$

Queue $4.$ We see that $4$ is the front of the

Max Queue, so we remove both the $4$s$.$ This does indeed make sense as $4$ can no longer remain

the Maximum after it is removed from the Main Queue.

If the process described above is followed and you code up the example provided we end up with

the complexity stated below.

Time Complexity of the Max Queue lookup: O$(1)$

Space Complexity on the Max Queue : O$($n$)$

Submissions that don$$t meet the mentioned Time and Space complexities will have $50\%$ credit

taken off