Queues


Mini Lab 1

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:

Exercise:

 


Mini Lab 2

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: 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.

Exercise


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