Queues


Mini Lab 1

A Queue interface, and an implementation

Java does not (yet?) provide a standard Queue interface, but consider the following one.

/** The Queue interface specifies the methods for a queue data structure.
 *    - The enqueue method adds an element to the "back" of the data structure.
 *    - The dequeue method acts as follows:
 *        - If the queue is empty, an exception is thrown.
 *        - If the queue contains one element, dequeue returns that element,
 *          leaving the queue empty.
 *        - If the queue contains multiple elements, dequeue returns the
 *          element at the "front" of the queue, the one that has been there longest.
 **/
public interface Queue
{
    /** Returns true if this queue is empty; false otherwise. */
    boolean isEmpty();
 
    /** Adds a specified object to the "back" of this queue.
     *    @param x the object to add to the queue
     */
    void enqueue(Object x);
 
    /** Removes the element at the "front" of this queue.
     *    @returns the returned element
     *    @throws an exception if the queue is empty
     **/
    Object dequeue();
 
    /** Returns the element at the "front" of this queue, without
     *  modifying the queue.
     *    @throws an exception if the queue is empty
     **/
    Object peekFront();

}

Read through the Queue interface and become familiar with the methods and their specifications.

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

Analysis Question:

Exercise:

 


Mini Lab 2

Testing and Using Queue 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

    Queue colorQueue = new LLQueue();
colorQueue is declared to be a Queue (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 Queue 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


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