Background

A very useful type of Collection interface is a deque (pronounced "deck"). Java has classes implementing this interface built in. For example:

Deque d1 = new LinkedList(); 

A deque is simply a list of objects, but access is restricted to adding and removing only from the list's front and back, and these operations are designed to be fast. Later in the semester, we'll see many applications of such lists when we study stacks and queues. I'm having you write a deque now to give you some insight into how Java collection classes work behind the scenes.

Specification

Write a class named Deque20, placed in the file Deque20.java. Your deque should support the following public methods.

public void push(E x) // Adds x to the front of the deque public E pop() // Removes and returns the front of the deque public void add(E x) // Adds x to the back of the deque public E remove() // Removes and returns the front of the deque public E peek() // Returns the front of the deque without removing it public boolean isEmpty() // Returns true if the deque has no elements public int size() // Returns the number of elements in the deque 

If the client attempts to pop, remove or peek an empty list, your method should throw a NoSuchElementException. Some collection classes do not allow null to be added or pushed, but your LinkedDeque should allow this (ie, d.pop() should return null after d.push(null)). You may find it useful to write a toString method to help with your debugging, this is allowed, but is not a required element of your class.

None of the methods should use a loop to do its work. This means that you will need to keep two references as fields, one to the front of the list and one to the back, and that you'll need to keep the count of the number of items as a field too. You don't need any other fields besides these three.

Use the starter code at the end of this writeup. It includes as part of its specification. This is how you make a class generic, allowing it to be a deque of any reference type. It's easy to write such classes. Simply put E anywhere you need a type in your code. Conceptually all of those E's are replaced by the user's supplied type.

Do not modify the ListNode class and do not submit it. I will use this exact file when testing your code.

Testing

One of the starter classes below is Deque20Test. You should develop this into a comprehensive test that prints the single word "true" to the screen if all tests pass and the single word "false" if any test does not pass. You can look at Posting @23 on Piazza to get the idea of what I'm looking for.

You should test your classes in a variety of situations, some ordinary some extreme. You should study the specification carefully and ask yourself what are the weirdest inputs I can give to methods that is within spec, and then test your code to make sure it behaves correctly. That's what I will do and if your program fails any of my tests, you will get no credit. If you think the specification is ambiguous or unclear, it's your responsibility to ask for clarification.

Submission

What to submit: ONLY REQUIRES the files Deque20.java and Deque20Test.java.

Grading: You will get full credit for this program if: ~ it is submitted on time, ~ is formatted properly, ~ has complete simple javadoc documentation that compiles without warnings or error, and ~ fulfills all functional requirements. It will receive zero credit otherwise. You will get a chance to resubmit your program if it doesn't work the first time (or if you didn't get it done in time), but you will lose 25% per late grading period (to be announced).

Collaboration: The preparatory work for this module has allowed you to work with others, but this program is for a grade so you should write it yourself. It is okay for you to discuss the program with others, but you should not share or copy any actual code. Any significant help you receive from any source should result in a comment near the affected code giving credit to the source.

Starter Code

public class ListNode { public E data; public ListNode next; } 

public class Deque20 { private ListNode front; // Reference to the front of the list private ListNode back; // Reference to the back of the list private int numElems; public Deque20() { front = null; back = null; nemElems = 0; } } 

public class Deque20Test { public static void main(String[] args) { boolean pass = true; // Put comprehensive tests here return pass; } }