Please fill in the TODO's, Will rate!

import java.util.*;

public class DoublyLinkedDeque implements DequeInterface {

private int count; // The count variable private DoublyLinkedNode headInFront; // Head reference in the front of the queue private DoublyLinkedNode tailInFront; // Tail reference in the front of the queue private DoublyLinkedNode headInRear; // Head reference in the rear of the queue private DoublyLinkedNode tailInRear; // Tail reference in the rear of the queue public DoublyLinkedDeque(){// Constructor, iniatializing an empty linked queue count = 0; headInFront = tailInFront = headInRear = tailInRear = null; }

// Add an element to the front of this queue. public void enqueueFront(T element){ // Create a new node DoublyLinkedNode newnode = new DoublyLinkedNode(element);

if (isEmpty()){ // TODO Change all front and rear in both ends to be the new node } else { // maintain the head-to-tail linked list by operating on the head reference in the front of the queue newnode.setNext(headInFront); headInFront = newnode; // TODO maintain the tail-to-head linked list by operating on the tail reference in the front of the queue (two statements are missing)

} count++; }

// Add an element to the rear of this queue. public void enqueueRear(T element){ // Create a new node DoublyLinkedNode newnode = new DoublyLinkedNode(element);

if (isEmpty()){ // Change all front and rear in both ends to be the new node headInFront = tailInFront = headInRear = tailInRear = newnode; } else { // TODO Maintain the tail-to-head linked list by operating on the head reference in the rear of the queue (two statements are missing)

// Maintain the head-to-tail linked list by operating on the tail reference in the rear of the queue tailInRear.setNext(newnode); tailInRear = newnode; } count++; }

// Throws QueueUnderflowException if this queue is empty; // otherwise, removes front element from this queue and returns it. public T dequeueFront() throws QueueUnderflowException{ if (isEmpty()) throw new QueueUnderflowException("Deque is empty!"); // Retrieve the to-be-removed node DoublyLinkedNode objNode = headInFront;

// Move the head reference to its next headInFront = headInFront.getNext();

// Decrease the number of nodes in the deque count--;

// TODO Maintain the other references, tailInRear, headInRear, and tailInFront // The if-else statement and assignment statement are missing // TODO return the data element of the to-be-removed node (one statement is missing) } // Throws QueueUnderflowException if this queue is empty; // otherwise, removes rear element from this queue and returns it. public T dequeueRear() throws QueueUnderflowException{ if (isEmpty()) throw new QueueUnderflowException("Deque is empty!"); // TODO Retrieve the to-be-removed node (one statement is missing)

// TODO Move the head reference to its next (one statement is missing)

// Decrease the number of nodes in the deque count--;

// Maintain the other references, tailInFront, headInFront, and headInRear if (tailInRear == null){ tailInFront = headInFront = null; }else tailInRear.setNext(null); headInRear = tailInRear; // return the data element of the to-be-removed node return (T)(objNode.getElement()); }

// Returns true if this queue is empty; otherwise, returns false. public boolean isEmpty(){ if (count == 0 || tailInRear == null || headInRear == null || tailInFront == null || headInFront == null) return true; else return false; } // Returns the number of elements in this queue. public int size(){ return count; }

public void printDeque(){ System.out.println("Head-to-tail list: "); printLinkedList(headInFront, true); System.out.println("Tail-to-head list: "); printLinkedList(headInRear, false); } private void printLinkedList(DoublyLinkedNode start, boolean isHead2Tail){ if (start == null) return; boolean isFirst = true; DoublyLinkedNode p = start; while (p != null){ if (isFirst){ System.out.print(p.getElement().toString()); isFirst = false; }else System.out.print("-->" + p.getElement().toString()); if (isHead2Tail) p = p.getNext(); else p = p.getPre(); } System.out.println(); } public static void main(String[] argv){ DoublyLinkedDeque deque = new DoublyLinkedDeque(); Scanner sc = new Scanner(System.in); int choice = -1; boolean isExit = false; String data;

try{ do{ System.out.println("We provide the following operations on the Deque data structure:"); System.out.println("1) enqueue in the front"); System.out.println("2) enqueue in the rear"); System.out.println("3) dequeue in the front"); System.out.println("4) dequeue in the rear"); System.out.println("5) quit"); System.out.print(" Please choose an operation: "); choice = sc.nextInt();

switch (choice){ case 1: System.out.print("Please input your text-based data: "); data = sc.next(); deque.enqueueFront(data); break; case 2: System.out.print("Please input your text-based data: "); data = sc.next(); deque.enqueueRear(data); break; case 3: deque.dequeueFront(); break; case 4: deque.dequeueRear(); break; case 5: isExit = true; break; default: System.out.println("Wrong choice!"); }

} while (! isExit); deque.printDeque(); } catch (Exception ex){ if (ex instanceof QueueUnderflowException) System.out.println(ex.getMessage()); } } }

//---------------------------------------------------------------------------- // DequeInterface.java // // Interface for a class that implements a deque of T. // A deque is a linear structure allowing insertion/removal at both ends. //----------------------------------------------------------------------------

public interface DequeInterface { void enqueueFront(T element); // Throws QueueOverflowException if this queue is full; // otherwise, adds element to the front of this queue.

void enqueueRear(T element); // Throws QueueOverflowException if this queue is full; // otherwise, adds element to the rear of this queue.

T dequeueFront() throws QueueUnderflowException; // Throws QueueUnderflowException if this queue is empty; // otherwise, removes front element from this queue and returns it.

T dequeueRear() throws QueueUnderflowException; // Throws QueueUnderflowException if this queue is empty; // otherwise, removes rear element from this queue and returns it.

boolean isEmpty(); // Returns true if this queue is empty; otherwise, returns false. int size(); // Returns the number of elements in this queue. }

/** * Represents a node in a linked list. */ public class DoublyLinkedNode { private DoublyLinkedNode next; private DoublyLinkedNode pre; private T element; /** * Creates an empty node. */ public DoublyLinkedNode() { next = null; pre = null; element = null; } /** * Creates a node storing the specified element. * @param elem element to be stored */ public DoublyLinkedNode(T elem) { next = null; pre = null; element = elem; } /** * Returns the node that follows this one. * @return reference to next node */ public DoublyLinkedNode getNext() { return next; } /** * Sets the node that follows this one. * @param node node to follow this one */ public void setNext(DoublyLinkedNode node) { next = node; } /** * Returns the node that follows this one. * @return reference to next node */ public DoublyLinkedNode getPre() { return pre; } /** * Sets the node that follows this one. * @param node node to follow this one */ public void setPre(DoublyLinkedNode node) { pre = node; } /** * Returns the element stored in this node. * @return element stored at the node */ public T getElement() { return element; } /** * Sets the element stored in this node. * @param elem element to be stored at this node */ public void setElement(T elem) { element = elem; }

/** * Returns the representative content of the element */ public String toString(){ return element.toString(); } }

public class QueueUnderflowException extends RuntimeException { public QueueUnderflowException() { super(); }

public QueueUnderflowException(String message) { super(message); } }