Implement this using java programming language.

A dequeue is a double-ended queue. It enables the adding and removing of data elements from an underlying data structure from either front (head) or rear (tail). Thus it can be used either as a FIFO or a LIFO data structure.

(a) [50 points] Using an instance of doubly linked list as the underlying data structure, implement a double-ended queue data structure called MyDequeue that implements Dequeue interface:

public interface Dequeue{

public void addToFront(T e);

public void addToRear(T e);

public T removeFront() throws UnsupportedOperationException;

public T removeRear() throws UnsupportedOperationException;

public T peekFront() throws UnsupportedOperationException;

public T peekRear() throws UnsupportedOperationException;

public boolean isEmpty();

public int getSize();

public boolean search(T e);

public String toString() throws UnsupportedOperationException;

}

Note: The java.lang. UnsupportedOperationException is thrown if the dequeue instance is empty.

An instance of MyDequeue has the following behaviour: values can be inserted and removed from the front and the rear of the dequeue, and the contents of the queue can be printed from front-to-rear. You must implement the following methods or constructors:

public MyDeQueue()	Constructor: It creates an empty MyDequeue instance.
public void addToFront (T e)	Adds a new node containing e as data to the front of this dequeue.
public void addToRear (T e)	Adds a new node containing e as data to the end of this dequeue.
public T removeFront()	Removes the front node of this dequeue and returns it's data.
public T removeRear()	Removes the rear node of this queue and returns it's data.
public T peekFront()	Returns the front node's data without deleting the node.
public T peekRear()	Returns the rear node's data without deleting the node.
public int getSize()	Returns the number of elements in this dequeue.
public boolean search(T e)	Returns true if element e is present in the dequeue; otherwise it returns false.
public String toString()	Constructs a string representation of the dequeue, from front to rear, and returns it.

(b) [20 points] Write a menu driven console program to test MyDequeue.

Deletion Deletion 10 20 30 40 50 60 70 80 Insertion Insertion Front Rear