public class MyDeque $$ Type $>-$ generic class declaration.

public MyDeque$()-$ a constructor that initializes an empty MyDeque.

public void addFirst$($Type item$)-$ adds the item to the front of MyDeque.

public void addLast$($Type item$)-$ adds the item to the back of MyDeque.

public Type removeFirst$()-$ removes and returns the item at the front of MyDeque $($or null

if MyDeque is empty$).$

public Type removeLast$()-$ removes and returns the item at the back of MyDeque $($or null

if MyDeque is empty$).$

public Type peekFirst$()-$ returns without removing the item at the front of MyDeque $($or

null if MyDeque is empty$).$

public Type peekLast$()-$ returns without removing the item at the back of MyDeque $($or

null if MyDeque is empty$).$

public int size$()-$ the current number of items in MyDeque.

public String toString$()-$ converts the contents of MyDeque to a String for display.

The doubly$-$linked node structure will be represented by the DLNode class, which must be local

to MyDeque $($hence only accessible by MyDeque$)$ and function according to the following

interface:

class DLNode $-$ local class declaration.

private DLNode next, prev $-$ forward and backward node pointers

DLNode$($T item$)-$ a constructor that creates a node containing the given item and points

forward and backward to null.

void link$($DLNode next, DLNode prev$)-$ links this DLNode forward and back $($the next

and$/$or prev pointers can be null$).$

The MyDeque and DLNode classes must not use or extend any other class $($except String and

possibly StringBuilder for creating a human$-$readable display of the data structure, and

java.io$.*$

and System for the actual $\frac{\text{I}}{O})$ nor plain arrays. MyDeque and DLNode must be both built from

scratch and doubly$-$linked allocation is required. Failure to do so will automatically award a

zero grade.

NB: The MyDeque class will be reused in later homework assignments $-$ design, implement and

test it carefully!

Your program will implement the Burger class using only the MyDeque class that must function

according to the following interface:

public class Burger $-$ plain class declaration.

Burger$($boolean theWorks$)-$ a constructor that initializes a Burger with only the buns and

patty if theWorks is false, or a Baron Burger if theWorks is true.

void changePatties$($String pattyType$)-$ changes all patties in the Burger to the pattyType.

void addPatty$()-$adds one patty to the Burger up to the maximum of $3.$

void addCategory$($String type$)-$ adds all items of the type to the Burger in the proper

locations.

void removeCategory$($String type$)-$ removes all items of the type from the Burger.