Harvey Mudd College
Computer Science 60
Assignment 05

Abstraction and Implementation of

Queue and Deque

using Closed Lists

Extra credit: Implement class PriorityQueue.

Due Date: Midnight, morning of Monday, March 3

Reading: This assignment covers material in Chapters 5 and 7 of the text.

Queues, deques, and priority queues are data abstractions that serve multiple purposes. For example, a Queue is often used in breadth-first search, which in turn applies to a variety of artificial intelligence problems. A deque will be used in a future video game we will develop, and a priority queue has uses in the realm of simulation.

There are many ways to implement the queue and deque concept: Linked lists, arrays, etc. So it is appropriate that there be one interface for each but allowing for more than one class to implement the interface.

Requirement: Define interfaces and implementations of classes Queue and Deque using your own linked list implementation. Your list implementations should be “from scratch”. It would border on trivial if you were allowed to use standard Java libraries, such as LinkedList and Vector, so we don’t allow you to use them.

The Queue implementation will count for 25% and the Deque implementation for 75%. Extra credit will be worth another 50%.

The Queue implementation provides a stepping stone for the Deque. Clearly you could do Deque first and specialize to Queue, but you are discouraged to take this route. Instead implement a Queue without any of the additional mechanism required for Deque. Also, the Deque should be easier once you’ve done the Queue.

Definitions:

Queue: A queue is a data repository in which Objects are removed in order of insertion. The methods for a queue are:

· void enqueue(Object)

· Object dequeue()

· boolean isEmpty()

Deque: A deque (pronounced “deck”) is a data repository in which Objects are inserted and removed from either end of a list. The methods for a deque are:

· void enqueueBack(Object)

· Object dequeueFront()

· void enqueueFront(Object)

· Object dequeueBack()

· boolean isEmpty()

Thus the first two methods can be used for a queue and other two methods can be used for a queue in the opposite direction, but the methods can be freely mixed. So, for example, a deque can also serve as a stack, by using enqueueFront and dequeueFront.

Priority Queue: A priority queue is a data repository in which objects are removed minimum-value first, where minimum is defined with respect to a Comparator, which is specified in the constructor of the priority queue. The methods for a priority queue are

· void enqueue(Object)

· Object dequeueMin()

· boolean isEmpty()

Throw an EmptyQueueException in the case of attempting to dequeue from an empty Queue, Deque, or PriorityQueue. (Use the same exception class for all three.) This exception should extend RunTimeException. Refer to OpenListException as an example of how to define this exception.

To be done in lab:

· Define the interface Queue

· Complete the class SLQueue that implements Queue and test it with TestQueue.java

· SLQueue is an implementation using a singly-linked list, which you write.

To be done in or outside lab:

· Define the interface Deque

· Complete the class DLDeque that implements Deque and test and test it with TestDeque.java

· DLDeque is an implementation using a doubly-linked list, which you write.

To be done for Extra Credit:

· Define the interface PriorityQueue

· Complete the class MyPriorityQueue that implements PriorityQueue and test it with TestPriorityQueue.java.

· MyPriorityQueue can be implemented any way you choose.

Who Provides What and Where? The following files are involved:

File	Purpose	Provider
Queue.java	Queue interface	You
SLQueue.java	Singly-Linked Queue implementation	You
EmptyQueueException.java	Exception for any of your classes.	You
Deque.java	Deque interface	You
DLDeque.java	Doubly-Linked Deque implementation	You
TestQueue.java	Queue test implementation	Me
TestDeque.java	Deque test implementation	Me
TestPriorityQueue.java	Priority queue test implementation	Me
PriorityQueue.java	Priority queue interface	(You, E.C.)
MyPriorityQueue.java	Priority queue implementation	(You, E.C.)

Implementation Suggestions

Construct each type of queue from an inner class, Cell for Queue and Dcell for Dequeue. You need not take pains to keep access to the components of cells private, as they will only be used inside of the queue, not outside. So the data are already encapsulated in a sense.

I strongly encourage you to use a box diagram for reasoning about the method coding, especially for the Deque implementation. If you come in for help with null pointer exceptions, please have a box diagram with you to show your rationale.

You may wish to implement a toString method for each class, so that you can print out the contents of your object for debugging purposes. The default toString method in class Object will not know how to print the contents of your queues.

Commenting

As always, comment your code. Be sure your comments indicate what each method does, including what the inputs and outputs are. For non-obvious methods, comment how it works as well.

Testing your code

Compile and run the self contained test java sources, e.g.:

java TestQueue

java TestDeque

Submitting your code

You should submit all your Java files related to this assignment:

cs60submit *.java

Please DO NOT submit .class files. Do not submit test files, unless doing so to get help.