topic: data structure

Part 1: Programming Assignment

For this assignment you will implement a deque data structure. A deque data structure is

like a combination of a queue and a stack where you can add and remove elements from

either end (i.e. from the head or the tail). We will use a doubly linked list to implement the

deque.

it also need to inlucde documentation or commenting

you should be using the Eclipse IDE. Create a workspace for

homework 1 and in that workspace create a project called hw1_proj, containing a package

called deque. Copy the starter files (Deque.java, DequeTest.java) into the package.

DequeTest.java is a JUnit 4 test file. You need to add JUnit 4 to your build path, see the JUnit

Setup section for instructions

The Deque.java file contains the beginnings of your implementation of the Deque. It

includes the Node inner class to hold the data and pointers to the previous and next Nodes

as well as two instance variables (head and tail) of the Deque. In addition, I have

implemented a few methods that you might find useful for implementation, debugging and

creating your own JUnit tests. Please do not modify these methods.

Commenting your Code (10 points)

It is important to understand how your entire program works. For each of the methods

below write a comment indicating which case you are handling and how you are handling it

(e.g., adding an integer to a list that already contains multiple elements or adding an integer

to an empty list).

Adding to the Deque (6 points)

Implement the following two methods. Make sure the method signatures are exactly as

described below.

public void insertHead(int i) : This method inserts a new Node in the Deque

with data equal to i that becomes the new head of the Deque.

public void insertTail(int i) : This method inserts a new Node in the Deque

with data equal to i that becomes the new tail of the Deque.

Removing from the Deque (6 points)

Implement the following two methods. Make sure the method signatures are exactly as

described below.

public int removeHead() : This method removes the current head of the Deque,

updates the head to be the next node in the Deque, and returns the value of the data in the

Node that was removed (the old head). If the Deque is empty a NoSuchElementException

is thrown.

public int removeTail() : This method removes the current tail of the Deque,

updates the tail to be the previous node in the Deque, and returns the value of the data in

the Node that was removed (the old tail). If the Deque is empty a

NoSuchElementException is thrown.

Peeking at the Deque (6 points)

Implement the following two methods. Make sure the method signatures are exactly as

described below.

public int peekHead() : This method returns the value of the data in the head of the

Deque. If the Deque is empty a NoSuchElementException is thrown.

public int peekTail() : This method returns the value of the data in the tail of the

Deque. If the Deque is empty a NoSuchElementException is thrown.

Sorting the Deque (6 points)

Implement the following methods. Make sure the method signatures are exactly as

described below.

public Deque sort() : This method returns a new Deque with the same values as the

original Deque, but with the data now in sorted order (from smallest to largest).

Testing Your Implementation (6 points)

I have given you a very limited set of JUnit tests to help determine if your implementation is

correct. You need to add at least 6 more JUnit tests that test typical and edge cases of the

different methods. You may want to add more than 6 JUnit tests, but if you add at least 6

JUnit tests (and your program passes them) you will receive full points for this part.

Submitting

Export your project and upload. You can export your project as either a jar or a zip file.

Make sure that the file you submit contains all your .java files ( and only your java files.

deque.java

package deque; import java.util.ArrayList; import java.util.NoSuchElementException; /* Name: FIll IN YOUR NAME * Enrollment Status: FILL IN YOUR ENROLLMENT STATUS * Resources Used (including students): FILL IN HERE */ public class Deque { /* * Nested inner class, that holds the Nodes of the Deque */ static class Node { int data; Node next; Node prev; public Node(int i) { data = i; next = null; prev = null; } } Node head; //front of the Deque Node tail; //back of the Deque public Deque() { head = null; tail = null; } /* * Returns true if the Deque is empty (contains no Nodes). Returns true otherwise. */ public boolean isEmpty() { return head==null&&tail==null; } /* * Converts an Deque to an ArrayList. * This method is useful for testing. */ public ArrayList toArrayList(){ ArrayList deq = new ArrayList<>(); Node current = head; while(current!=null) { deq.add(current.data); current = current.next; } return deq; } /* * Returns a String representation of the Deque. * This method is useful for testing. */ public String toString() { String s = ""; if(isEmpty()) return s; Node current = head; while(current!=null) { s = s+current.data + ","; current = current.next; } return s.substring(0,s.length()-1); } /* ******************************************************************************* * * ADD YOUR METHODS HERE * *********************************************************************************/ }

Deque.Test.java

package deque; import static org.junit.Assert.*; import java.util.ArrayList; import java.util.NoSuchElementException; import org.junit.BeforeClass; import org.junit.Test; public class DequeTest { static ArrayList toCompareOne; static ArrayList toCompareMany; static ArrayList sorted; @BeforeClass public static void setup() { toCompareOne = new ArrayList<>(); toCompareOne.add(1); toCompareMany = new ArrayList<>(); for(int i=0;i<10;i++) { toCompareMany.add((int)(Math.random()*i)); } sorted=new ArrayList<>(); for(int i=0;i<5;i++) { sorted.add(i); } } @Test public void oneElement() { Deque one = new Deque(); one.insertHead(1); assertEquals(one.toArrayList(),toCompareOne); } @Test public void ManyElementsTail() { Deque many = new Deque(); for(int i:toCompareMany) many.insertTail(i); assertEquals(many.toArrayList(),toCompareMany); } @Test(expected = NoSuchElementException.class) public void removeHeadFromEmpty() { Deque empty = new Deque(); empty.removeHead(); } @Test public void sorted() { Deque notSorted = new Deque(); for(int i: sorted) { notSorted.insertHead(i); } Deque sortTest = notSorted.sort(); assertEquals(sortTest.toArrayList(),sorted); } }