Java

Using Java Implement a referenced based Deque. Create an inner (inside the Deque class) class Node. The Node class will have the attributes:

T item

Node next

You will also create a class Deque that has the following attributes:

Node head

Node tail

int items

Also, it will have the following methods:

A constructor that creates an empty deque.

void addFirst(T item) - adds at the head

T removeFirst() - removes from the head

T getFirst() - returns the element at the head

void addLast(T item) - adds at the tail

T removeLast() - removes from the tail

T getLast() - returns the element at the tail

int size() - returns the number of items in the deque

boolean isEmpty() - true if empty false otherwise

String toString() - returns a String representation of the elements in the deque

void clear() - empties the deque.