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.
Analysis Question:
- Consider the following data structures. Which ones could be used as
the internal data representation for a
KQueue
implementation with the performance characteristics described above?- a Java array?
- an
ArrayList
object? - a
LinkedList
object?
- Which do you think would be easiest to implement?
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
is declared to be a KQueue
(interface), but constructed as an instance of LLQueue
(implementation). The statement could be written:
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.
Analysis Question:
- What happens when you ask for the queue's size? Should there be a
size
method for a queue? If so, where would you put it? - Yes! You guess it! Add a method
size()
to your queue.
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 itQueueTester
) or it can be amain()
method inside theLLQueue
class. It needs to add, remove and peek elements from the queue. Make sure you have awhile
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()
orLLQueue object = new LLQueue()
to create your queue, you will have to decide where to create the methodsize()
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!
← back to the schedule