MINI-LAB #3
Queues

By Autumn C. Spaulding autumn@max.cs.kzoo.edu with Alyce Brady abrady@kzoo.edu

---

A Queue interface, and an implementation

Read through the KQueue interface, a simplified version of the standard Java Queue interface that specifies four methods: isEmpty, enqueue, dequeue, and peekFront. Become familiar with the methods and their specifications.

Now consider implementing a class that implements the KQueue interface with O(1) performance for all four methods.

---

Stage 1

Create a class, LLQueue, that implements the KQueue interface using a java.util.LinkedList internally. Remember that the LLQueue class extends Object as well as implementing KQueue, so it inherits methods such as toString and equals (and hashCode) unless it redefines them. Provide an implementation of the toString method that returns a string showing the current state of the queue.

---

Testing and Using KQueue and LLQueue

Client code should be able to use a queue according to the interface, without caring how it is implemented internally. In fact, well-written client code depends only on the interface, except when constructing the queue. When an object is constructed, of course, it is necessary to specify the object's class.

For example, consider a variable, called colorQueue, representing a queue containing color information. The established way of using an interface implementation is to use the interface name for the variable declaration, and to use the actual class name only when constructing the object. For example, in the statement:

KQueue colorQueue = new LLQueue();

colorQueue is declared to be a KQueue (interface), but constructed as an instance of LLQueue (implementation). The statement could be written:

LLQueue colorQueue = new LLQueue();

but this is less flexible. The first version says, "Create a KQueue object called colorQueue, and implement it using the LLQueue class." The second version says, "Create an LLQueue object." The first version is the accepted pattern unless the client code needs to use methods specific to the actual implementation.

---

Stage 2

Create a test driver for the LLQueue class and add three different strings to the queue. You can give the strings whatever values you like: this is for practice. For testing purposes, if you would like to see the entire contents of the queue, you can use the toString method.

Then, remove an element from the queue. What should the queue look like now?. Remove the rest of the elements in the queue. You could just call the dequeue twice more, but what if you have been adding and subtracting elements and don't know how many elements are in the queue? The elementary pattern for removing all the elements from a queue is similar to the pattern for traversing a linear data structure using an iterator.

while ( ! theQueue.isEmpty() )
{
   SpecificType element = theQueue.dequeue();
   // possibly use element in some way before removing next one...
}

Look over the pattern and make sure that it makes sense to you and that you could use it in code of your own. Then use it to remove the elements from your queue. Add several new items to the queue. Verify that the queue contains what you think it does.

Submit your completed program through Kit, under Mini-Lab 3.

---

EVALUATION

Mini-lab #3 is worth 15 points. This project will be submitted individually. The following items describe the criteria we will use to evaluate your mini-lab:

• Correct implementation of all methods of the KQueue interface in the LLQueue class:
  • enqueue() method 2 pts.
  • dequeue() method 2 pts.
  • peekFront() method 2 pts.
  • isEmpty() method 1 pts.
• Correct implementation of a test driver for the LLQueue class. It can be a separate class (you can name it QueueTester) or it can be a main() method inside the LLQueue class. It needs to add, remove and peek elements from the queue. Make sure you have a while loop structure so you can dequeue all the elements until the queue is empty. 4 pts.
• Correct use of the queue: whether you used KQueue object = new LLQueue() or LLQueue object = new LLQueue() to create your queue, you will have to decide where to create the method size() 2 pts.
• Adding appropriate amount of comments to the code (your name and description of the class, method description, and so on) 1 pt.
• Proper organization of your code (indentation, clarity, cleverness) 1 pt.

Have fun! And if you have any questions remember my email, my office hours, and the collaboration center are here for you!