Queues
MINI-LAB
By Autumn C. Spaulding with Alyce Brady
A Queue Interface, and an Implementation
Read through the K_Queue interface, a
simplified version of the standard Java Queue interface that
specifies five methods: isEmpty, size,
enqueue, dequeue, and peekNext.
Become familiar with the descriptions of these methods.
Now think about implementing a class that implements the
K_Queue interface with O(1) performance for all five methods.
Stop and Think:
- Consider the following data structures. Which ones could be used as
the internal data representation for a
K_Queue 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 -
Implementing the K_Queue Interface
Create a project for this mini-lab and download the
K_Queue interface and the skeleton
K_LLQueue class and
K_SimpleQueueTester.java
test driver.*
The K_LLQueue class was created by:
- copying the interface and changing the name,
- slightly modifying some of the early comments,
- replacing the method descriptions with
{@inheritDoc}
so that they always display the same information as the
interface description and adding @Override to tell the
compiler to check that the signatures are correct,
- adding "public" to the front of all the method signatures,
- giving the methods minimal "stub" bodies that return an arbitrary
value of the correct type.*
It does not yet have any instance variables, a constructor, or meaningful
method bodies. Implement the class using a K_SimpleLL
linked list internally as a private instance variable. Add a constructor.
Implement the methods. Since the
K_SimpleQueueTester.java test driver
does not contain any calls to the size method, you
can leave that as a stub function for now.
Remember that, like all classes, the K_LLQueue class also
extends Object, so it inherits methods such as
toString and equals (and hashCode)
unless it redefines them. Provide an overriding implementation of the
toString method that returns a string showing the current
state of the queue.
* Stubs and Drivers: Stubs and Drivers are key
components when developing and testing software. A test
driver is a small program whose sole purpose is to run a
series of isolated tests, without the full context or complexity of a
true application. A stub is a temporary place-holder method
providing simplified functionality, often doing nothing or just
returning an arbitrary value of the right type so that the method will
compile, even if it doesn't do anything useful.
⇓
(Continue to Implementation Stage 1)
Stage 2 -
Testing and Using K_Queue and K_LLQueue
Adding Elements to a Queue
Modify the test driver to construct an instance of the K_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.
Declare Variables Using Interface or Specific Class Type?
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:
K_Queue colorQueue = new K_LLQueue();
colorQueue is declared to be a K_Queue
(interface), but constructed as an instance of K_LLQueue
(implementation). The statement could be written:
K_LLQueue colorQueue = new K_LLQueue();
but this is less flexible. The first version says, "Create a
K_Queue object called colorQueue, and implement it
using the K_LLQueue class." The second version says, "Create an
K_LLQueue object." The first version is the accepted pattern
unless the client code needs to use methods specific to the actual
implementation.
Removing Elements from a Queue
Now test removing 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 uses
a while loop.
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.
⇓
(Continue to Implementation Stage 2)
⇓
(Continue to Implementation Stage 3)
Submission
Submit your completed program through
Kit, under Queue Mini-Lab.
Have fun! And if you have any questions remember I am available through
email, Teams, and my office hours. And don't forget the Collaboration
Center, which is a great place to work and ask questions too!