Harvey Mudd College
Computer Science 60
Assignment 05

Abstraction and Implementation of

Queues, Deques, and Priority Queues

Due Dates:

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.

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

Requirement: Implement classes Queue and Deque using your own linked list implementation. Your implementation should be “from scratch”. This 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%.

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, but if you have problems with the Queue, you would certainly have problems if you did the Deque first.

Extra credit: Implement class PriorityQueue.

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 (“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 enqueueFront(Object)

·          Object dequeueBack()

·          void enqueueBack(Object)

·          Object dequeueFront()

·          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 Comparable objects are removed minimum-value first. The methods for a priority queue are

·          void enqueue(Comparable)

·          Comparable dequeueMin()

·          boolean isEmpty()

Examples of classes that implement interface Comparable are: String, Number (which includes Integer, Long, Double).

Throw an EmptyQueueException in the case of attempting to dequeue from an empty Queue or Deque.

To be done in lab:

Who Provides What? The following files are involved:

File

Purpose

Provider

 
Queue.java

Queue interface

Me

 
Deque.java

Deque interface

You

 
PriorityQueue.java

Priority queue interface

(You, E.C.)

 
MyQueue.java

Queue implementation

You

 
EmptyQueueException.java

Exception for any of your classes.

You

 
MyDeque.java

Deque implementation

You

 
MyPriorityQueue.java

Priority queue implementation

(You, E.C.)

 
TestQueue.java

Queue test implementation

Me

 
TestDeque.java

Deque test implementation

Me

 
TestPriorityQueue.java

Priority queue test implementation

Me

Implementation Suggestions

Construct each type of queue from an inner class Cell. You need not take pains to keep access to the components of Cell private, as Cells 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 codings, 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.

Commenting

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

Submitting your code

You should submit your rex functions in two files: Quantity.java and OpenList.java using 

cs60submit MyQueue.java EmptyQueueException.java . . .

where . . . represents any other supported.java files needed. Do NOT submit .class files or test files.