Laboratory: Double-Ended Queue (Dequeue)
 CSC 207 Algorithms and Object Oriented Design Spring 2011

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/2011S/labs/code/dequeue/Dequeue.java .
cp ~weinman/public_html/courses/CSC207/2011S/labs/code/dequeue/TestDequeue.java .```
This should place a class skeleton and a test suite into your directory.

# 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.removeRear()
dq.removeRear()
dq.removeFront()
dq.removeRear()
```

## 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()
---------------

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 to 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

Consider the method `addRear`, which you have already implemented. As mentioned above, `addFront` will be similar.
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

Now it's time for the last piece of the puzzle!
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 `Dequeue` called `ListDequeue`.
3. Copy `TestDequeue.java` to `TestListDequeue.java` and change all the references to `Dequeue` objects to `ListDequeue` objects.
4. Test your implementation of `ListDequeue` and fix any bugs.

# Notes on the Exercises

## Note on Exercise 1

When you add these things to the dequeue, the contents are (front at the left and rear at the right, without wraparound) [6 7 3 5]. Therefore, when you remove the items as shown, the results are 5 3 6 7.
Created: 18 March 2009
Modified: 14 April 2010
Modified: 18 January 2011