For this assignment, you will be writing a Deque ADT (i.e., LastnameDeque). A deque is closely related to a queue - the name deque stands for "double-ended queue." The difference between the two is that with a deque, you can insert, remove, or view, from either end of the structure. Attached to this assignment are the two source files to get you started:

Deque.java - the Deque interface; the specification you must implement.

BaseDeque.java - The driver for Deque testing; includes some simple testing code.

Your first step should be to review these files and satisfy yourself that you understand the specification for a Deque. Your goal is implement this interface. Implementing this ADT will involve creating 9 methods:

public LastNameDeque() - a constructor [3 points]

public void enqueueFront(Item element) - see interface [4 points]

public void enqueueBack(Item element) - see interface [5 points]

public Item dequeueFront() - see interface [4 points]

public Item dequeueBack() - see interface [5 points] 1

public Item first() - see interface [1 points]

public Item last() - see interface [1 points]

public boolean isEmpty() - see interface [1 points]

public int size() - see interface [1 points]

public String toString() - see interface [3 points]

From Section 1, be sure that you:

Make all operations (except toString) work in O(1).

Do not import any packages other than java.util.NoSuchElementException.

Use a doubly linked list data structure.

Hint: you may need to create a node class.

A few simple test operations have already been provided. These are very simple tests - passing them is necessary but not sucient for knowing that your program works properly. The sample output from these tests is:

s i z e : 3

contents :

8 9 4

4

8

9

1

11

s i z e : 2

contents :

1 11

When you set about writing your own tests, try to focus on testing the methods in terms of the integrity of the overall linked list. If you compare the tests that you given, with the parts of your program that they actually use (the code coverage), you'll see that these tests only use a fraction of the conditionals that occur in your program. Consider writing tests that use the specific code paths that seem likely to hide a bug. You should also consider testing things that are not readily apparent from the interface specification. For example, write a test that prints your list starting at the head, and another that starts at the end. See if they give the same result.

Deque.java:

import java.util.NoSuchElementException;

public interface Deque { /** * Adds one element to the front of this deque. * @param element the element to be added to the front of the deque */ public void enqueueFront(Item element); /** * Adds one element to the back of this deque. * @param element the element to be added to the back of the deque */ public void enqueueBack(Item element);

/** * Removes and returns the element at the front of this deque. * Throws an exception if the deque is empty. * @return the element at the front of this deque * @throws NoSuchElementException if the deque is empty */ public Item dequeueFront() throws NoSuchElementException; /** * Removes and returns the element at the back of this deque. * Throw an exception if the deque is empty. * @return the element at the back of the deque. * @throws NoSuchElementException if the deque is empty */ public Item dequeueBack() throws NoSuchElementException;

/** * Returns, without removing, the element at the front of this deque. * Should throw an exception if the deque is empty. * @return the first element in the deque * @throws NoSuchElementException if the deque is empty */ public Item first() throws NoSuchElementException; /** * Returns, without removing, the element at the back of this deque. * Should throw an exception if the deque is empty. * @return the last element in the deque * @throws NoSuchElementException if the deque is empty */ public Item last() throws NoSuchElementException; /** * Returns true if this deque is empty and false otherwise. * @return if deque empty */ public boolean isEmpty();

/** * Returns the number of elements in this deque. * @return the number of elements in the deque */ public int size();

/** * Returns a string representation of this deque. The back element * occurs first, and each element is separated by a space. If the * deque is empty, returns "empty". * @return the string representation of the deque */ @Override public String toString(); }

BaseDeque.java

import java.util.NoSuchElementException; //TODO: implement. public class BaseDeque implements Deque {

/** * Program entry point for deque. * @param args command line arguments */ public static void main(String[] args) { BaseDeque deque = new BaseDeque<>();

//standard queue behavior deque.enqueueBack(3); deque.enqueueBack(7); deque.enqueueBack(4); deque.dequeueFront(); deque.enqueueBack(9); deque.enqueueBack(8); deque.dequeueFront(); System.out.println("size: " + deque.size()); System.out.println("contents: " + deque.toString());

//deque features System.out.println(deque.dequeueFront()); deque.enqueueFront(1); deque.enqueueFront(11); deque.enqueueFront(3); deque.enqueueFront(5); System.out.println(deque.dequeueBack()); System.out.println(deque.dequeueBack()); System.out.println(deque.last()); deque.dequeueFront(); deque.dequeueFront(); System.out.println(deque.first()); System.out.println("size: " + deque.size()); System.out.println("contents: " + deque.toString()); } }