Implement a MaxQueue data structure as a singly$-$linked list, that can store comparable ele$-$

ments. MaxQueue supports the usual FIFO Queue operations add$($x$),$ remove$(),$ and size $().$

In addition, it supports a max $()$ operation, which returns the maximum value currently stored

in the data structure. You have to modify the file MaxQueue.py that is included in the same

Beachboard folder as these instructions.

Hint: Consider storing elements into a singly$-$linked list and into a doubly$-$linked list using

the following algorithms:

Adding an element: When a new element is added to the MaxQueue, it is added to the

tail of the singly$-$linked queue, regardless of its value. Moreover,

if the element is larger than the current max $($which is stored at the head of the

doubly$-$linked list$)$ then the doubly$-$linked list is emptied out, and the new element

gets placed in the head as the new the max.

if the element is smaller than the current max, the element gets placed in the

doubly$-$linked list in decreasing order. Discard any elements existing in the doubly$-$

linked list that are smaller than this new element. This is because they will be re$-$

moved from the singly$-$list queue before the newly$-$added element, and thus will

never have the chance to be the max element of the queue.

Removing an element: When an element is removed, it is removed from the head of

the singly$-$linked queue. Moreover, if the removed element was the maximum element,

the head of the doubly$-$linked list must also be removed.

Example: