Question 2 Deque as DLL [55 points] In class, we have studied the Deque ADT, which is a generalization of a stack and a queue that supports inserting and removing items from either the front or the back of the data structure. The interface implemented by Deque is shown below. (Note, this interface contains an additional method not discussed in class - printOutContent(), which has a similar purpose as the same-named method from Q1.) public interface Deque public boolean isEmpty // is the deque empty public int size) public void addFirst(E item): 1/ insert the item at the front public void addLast(E item): // insert the item at the end public E removeFirst): public E removeLast public E firstO: public E last () void printOutContent) .)// print out the current content of deque // return the number of items on the deque // delete and return the item at the front // delete and return the item at the end // return but does not remove the first element // return but does not remove the last element Your task in this question is to implement the Deque interface using a doubly-linked-list (DLL) with a header and trailer as its underlying data structure. Your Deque class will be tested by running the following code import java.util.Scanner public class DequeTest /** A method that prints the explanation of what the program does. "/ public static void directions) String msg " This program stores first N integers in a deque, where N is provided by the user. " + "It removes integers one at a time until only one integer is left - the winner. "+ "However, removing an integer is a bit complicated. " + "An integer is removed from the remaining list as follows: " + "\t1) move the number at the front of the list to the end of the list: " + "\t2) move the next number to the end of the list; " + "\t3) now remove the integer at the front of the list and discard it." + "InWhen only one integer remains, it is declared the winner. "'. System.out.printIn(msg): ) public static void main(Stringl] args) Deque Integer> dq new DequeInteger ) directions) Scanner in new Scanner(System.in) System.out.printf("Enter N: "); int n in.nextInt()