Question
I need help with the following Java code
Use a two-part circular linked chain to implement the ADT deque. Name your class TwoPartCircularLinkedDeque. In this implementation each of your nodes will consist of three data fields, namely, previous (of type Node), data (of type T), and next (of type Node).
Here is the interface the class needs to implement
/**
An interface for the ADT deque.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public interface DequeInterface<T>
{
/** Adds a new entry to the front/back of this deque.
@param newEntry An object to be added. */
public void addToFront(T newEntry);
public void addToBack(T newEntry);
/** Removes and returns the front/back entry of this deque.
@return The object at the front/back of the deque.
@throws EmptyQueueException if the deque is empty before the operation. */
public T removeFront();
public T removeBack();
/** Retrieves the front/back entry of this deque.
@return The object at the front/back of the deque.
@throws EmptyQueueException if the deque is empty. */
public T getFront();
public T getBack();
/** Detects whether this deque is empty.
@return True if the deque is empty, or false otherwise. */
public boolean isEmpty();
/* Removes all entries from this deque. */
public void clear();
} // end DequeInterface
Explanation / Answer
class EmptyQueueException extends RuntimeException { public EmptyQueueException(String string) { super(string); } } class LLNode { private T value; private LLNode back; private LLNode next; public T getValue() { return value; } public LLNode getBack() { return back; } public LLNode getNext() { return next; } public void setValue(T val) { value = val; } public void setBack(LLNode n) { back = n; } public void setNext(LLNode n) { next = n; } } interface DequeInterface { /** Adds a new entry to the front/back of this deque. @param newEntry An object to be added. */ public void addToFront(T newEntry); public void addToBack(T newEntry); /** Removes and returns the front/back entry of this deque. @return The object at the front/back of the deque. @throws EmptyQueueException if the deque is empty before the operation. */ public T removeFront(); public T removeBack(); /** Retrieves the front/back entry of this deque. @return The object at the front/back of the deque. @throws EmptyQueueException if the deque is empty. */ public T getFront(); public T getBack(); /** Detects whether this deque is empty. @return True if the deque is empty, or false otherwise. */ public boolean isEmpty(); /* Removes all entries from this deque. */ public void clear(); } // end DequeInterface public class TwoPartCircularLinkedDeque implements DequeInterface { private LLNode front; private LLNode last; private int size; TwoPartCircularLinkedDeque() { front = new LLNode(); last = new LLNode(); front.setNext(last); last.setBack(front); size = 0; } public int getSize() { return size; } public void addToFront(T string) { LLNode n = new LLNode(); n.setValue(string); n.setNext(front.getNext()); n.setBack(front); front.getNext().setBack(n); front.setNext(n); size++; } public void addToBack(T string) { LLNode n = new LLNode(); n.setValue(string); n.setBack(last.getBack()); n.setNext(last); last.getBack().setNext(n); last.setBack(n); size++; } public T removeFront() { if(size == 0) throw new EmptyQueueException("Queue Empty"); LLNode n = front.getNext(); front.setNext(n.getNext()); n.getNext().setBack(front); size--; return n.getValue(); } public T removeBack() { if(size == 0) throw new EmptyQueueException("Queue Empty"); LLNode n = last.getBack(); last.setBack(n.getBack()); n.getBack().setNext(last); size--; return n.getValue(); } public T getFront() throws EmptyQueueException { if(size == 0) throw new EmptyQueueException("Queue Empty"); return front.getNext().getValue(); } public T getBack() throws EmptyQueueException { if(size == 0) throw new EmptyQueueException("Queue Empty"); return last.getBack().getValue(); } public boolean isEmpty() { return (size == 0); } public void clear() { front = new LLNode(); last = new LLNode(); front.setNext(last); last.setBack(front); size = 0; } }