Summary: In this lab, you will practice implementing (and testing!) your own specific collection. Namely, a double-ended queue (aka Dequeue).

Preparation

1. Create a directory for this lab:

     mkdir somewhere/dequeue

2. Go to your new directory:

     cd somewhere/dequeue

3. Copy the files for this lab:

     cp ~weinman/public_html/courses/CSC207/2010S/labs/code/dequeue/*.java .

   This should place a class skeleton, Dequeue.java, a test suite, TestDequeue.java into your directory . (Don't worry if cp complains that it can't copy my solution file Dequeue.SOL.java... that's the idea.)

Background

As you should know from your reading of Weiss 16.5, a double-ended queue allows access at "both ends." In other words, it acts like both a queue (add to end, retrieve from front), and a stack (add to front, retrieve from front). Plus, it allows you to retrieve from the end as well. Thus, it is like a mini-Swiss army knife of data structures. (A list would probably be the full-on Swiss army knife, since it allows arbitrary access.)

Our dequeue implementation will support six core operations,

• two that "peek" at the collection without modifying it,
• two that modify it by removing from either end, and
• two that modify it by adding to either end.

void addFront( AnyType x ) // Insert x at front
void addRear( AnyType x )  // Insert x at rear
AnyType getFront()         // Return item at front
AnyType getRear()          // Return item at rear
AnyType removeFront()      // Return and remove item at front
AnyType removeRear( )      // Return and remove item at rear

Exercises

Exercise 1

1. What will be the results returned by the following sequence of remove operations? Write down your answers.

   dq.addFront(3)
   dq.addRear(5)
   dq.addFront(7)
   dq.addFront(6)
   dq.removeRear()
   dq.removeRear()
   dq.removeFront()
   dq.removeRear()
   

2. Check the notes on this exercise to verify your answers.

Exercise 2

1. Open the file Dequeue.java in Emacs.
2. Briefly examine the public methods
   • Dequeue
   • isEmpty
   • makeEmpty
   • getFront
   • getRear
   • removeFront
   • removeRear
   • addFront
   • addRear
   to be sure you understand what they are to do.
3. Briefly examine the private methods to be sure you understand what they do or are to do.
4. Examine the private fields and be sure to understand what they mean. (They are the same as for the dynamic array implementation of a queue used in the book.)
5. Open the file TestDequeue.java in Emacs. This contains a unit test suite using a testing library. Briefly scan the methods to see what is tested.
6. Compile the files Dequeue.java and TestDequeue.java from Emacs (remember the useful short cut C-c C-v C-c).
7. To run the suite of tests on your current dequeue implementation, you can use the JDE "Run App" command as usual (or the handy shortcut C-c C-v C-r).
8. Amidst all the output, you should see a summary near the top:

   TestDequeue:
   ---------------
   .  
      new TestDequeue:1()
   ---------------
   Found 17 test methods
   
   Ran 51 tests.
   43 tests failed.
   

   Hey, at least 8 things worked, right?

Exercise 3

1. Given the private fields front, back, and currentSize, what should the method makeEmpty do? That is, will it differ from the implementation in Figure 16.17 (p. 605)?
2. Implement makeEmpty in Dequeue.java
3. Given your private fields, will isEmpty differ from the implementation in Figure 16.13 (p. 603)?
4. Implement isEmpty in Dequeue.java
5. Verify that your code compiles.

Exercise 4

1. The method getFront is akin to the same method in Weiss's ArrayQueue class. Given your member variables, will the implementation differ substantially?
2. Implement getFront in Dequeue.java. Pay careful attention to the specification for the exception (the tester cares what the message is).
3. Verify that your code still compiles.
4. The method getRear is new. How will you implement it using your member variables?
5. Implement getRear in Dequeue.java. (Again, pay attention to the specification for the exception.)
6. Verify that your code still compiles.

Exercise 5

1. The method addRear is akin to enqueue in the original ArrayQueue class. Will the implementation for a dequeue differ substantially?
2. Implement addRear and compile your code.

Exercise 6

1. The method removeFront is akin to dequeue in the original ArrayQueue class. Will the implementation for your Dequeue class differ substantially?
2. Implement removeFront and compile your code.

Exercise 7

The method addFront is new the dequeue structure. It is essentially the "reverse" of addRear. The original queue has a method increment to implement wrap-around from the end of the array back to the beginning. In order to be able to add to the front of the queue, we'll need to also wrap-around from the beginning of the array back to the end.

1. Review the method increment and then review the documentation/specification for decrement.
2. Implement decrement and verify that your code compiles.

Exercise 8

1. How will front change when you add an item?
2. How will back change when you add an item?
3. Implement addFront based on your replies. (Don't forget to use decrement. Of course, by now you should be getting used to compiling your code frequently. So compile already!
4. Consider the following operations on an empty dequeue:

   dq.addFront(1)
   dq.getRear()
   

   This should work correctly and return 1. Consider carefully the status of front, and especially back in your code after the first operation.
5. Will your implementation function correctly? If you think so, it may be time to run the unit test suite. If both of these methods work correctly, you should pass test number 15.
6. Make sure you pass tests 15 and 16 before continuing.

Exercise 9

1. Consider the removeRear method. It acts like the "reverse" of the removeFront method.
2. How will the size change?
3. How will front change?
4. How will back change?
5. Implement removeRear based on your replies above.
6. Compile and test your code. You should now fix any outstanding test failures. This may require you to study the test cases more carefully.

For those with Extra Time

1. Copy the class weiss.nonstandard.ListNode to your current directory and remove the package specification.
2. Use the ListNode class to implement your own list-backed version of Deque called ListDeque.
3. Copy TestDeque.java to TestListDeque.java and change all the references to Deque objects to ListDeque objects.
4. Test your implementation of ListDeque and fix any bugs.

Notes on the Exercises

Note on Exercise 1