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 four methods: isEmpty, 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 four methods.
Analysis Question:
- 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
test driver
K_SimpleQueueTester.java.
(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.) Then create a class, K_LLQueue, that implements
the K_Queue interface using a
K_SimpleLL linked list internally.
Remember that the K_LLQueue class extends Object as
well as implementing K_Queue, 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.
⇓
(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)
Stage 3 - Adding a size Method
Analysis Question:
- Should there be a
size method for a queue? If so,
where would you put it?
- Yes! You guessed it! Add a
size() method to the
K_Queue interface and to your K_LLQueue
class. Test the new method in your test driver.
⇓
(Continue to Implementation Stage 3)
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!