Java

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

Space Complexity on the Max Queue: O(n)

Include comments please!

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 implement this design using the ArrayDeque Class in Java. URL reference here: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html 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: 41 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: 41 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 deQueue 1 and 4 from the Queue. So, we insert it onto the Max Queue: MainQueue: 241