Summary: We consider the essential features of queues, one of the forms of linear structures. We also consider a novel implementation of queues.
Prerequisites: Linear Structures, Arrays, Polymorphism, Inheritance, Generics, Stacks.
Contents:
Now that you understand about linear structures and stacks,
you will find that queues are also fairly simple. Queues
are linear structures
structures that implement a first in, first out
policy. That is, the value returned by get is
the value least recently added to the stack.
Why do we have queues in addition to stacks? Because for
many applications (such as to-do lists), stacks are inherently
unfair
. In particular, if you do a lot of put
and get operations, you will not get the first
element you put until after you've dealt with everything else.
(Yes, that's the intent of stacks, but it's not very fair if, for
example, you use a stack to deal with incoming mail messages or phone
calls.)
As you may recall, we often use object-oriented programs to
model real-world systems. There are many places in which
things end up in line
(or in the queue
, if you're
in Great Britain). For example, if you are modeling a retail
store, the lines at each cash register can be modeled by queues.
(It's a little bit harder to deal with people who cut in line,
but we won't worry about such issues right now.)
package username.linear;
/**
* A linear structure that follows the "first in, first out" policy.
*
* @author Samuel A. Rebelsky
* @version 1.1 of March 2006
*/
public interface Queue<T>
extends LinearStructure<T>
{
/**
* Add an element to the end of the queue.
*
* @param val
* The object that is to be added.
* @post
* The queue now contains an additional copy of val.
*/
public void put(T val);
/**
* Remove the least-recently-added element that is still in the
* queue.
*
* @return val
* An object in the queue.
* @pre
* The queue is not empty.
* @post
* The queue contains one fewer copy of val.
* @post
* Every value in the queue was added more recently than val.
*/
public T get();
/**
* Determine which object will next be returned by get.
*
* @return val
* An object in the queue.
* @pre
* The queue is not empty.
* @post
* Every other value in the queue was added more recently than val.
*/
public T peek();
/**
* Determine if the queue is empty.
*/
public boolean isEmpty();
} // interface Queue<T>
At first glance, it may seem as easy to implement queues with arrays as it was to implement stacks with them. Unfortunately, because queues behave differently than do stacks, we encounter some significant problems.
In particular, if we follow the stack policy of putting new values at the
end of the array, we'll need to implement get by removing
values from
the front. We can use the remove(int index) method
of the DynamicArray class to remove the initial value in the array, but
that is actually quite inefficient since it must shift every
remaining element left one space. (Note that this does not pose a problem
for stacks since we always remove the rightmost element from a stack.)
Another possibility would be to leave the array elements in place, but
somehow mark them as "removed" when they have been (conceptually)
removed from the stack. That would save time during the remove operation.
However,
we will soon find that we run off the end of the array, even if we have
empty space at the front. In stacks, we simply allow the
array to grow and grow, as needed. However, for queues, it seems
wasteful to grow allow it to grow when there is (conceptually) empty
space available
at the beginning. It is possible to wrap around
, and add
new elements to the empty spaces at the beginning of the array. An
implementation that does so is called a "circular array," but
it has many subtleties that novice programmers
(and even some expert programmers) tend to handle incorrectly, so we will
avoid it.
Is there an better way to implement queues? It turns out that we can implement queues as a form of linked structure. Linked structures are typically built by creating small objects, which we call nodes. Each node contains a value and links (connections) to other nodes. You can think of each node as a position in the queue.
As a first step in creating a queue, we create a
QueueNode class with two
fields: contents, which refers to the contents of the
node (the value at that position), and next, which
refers to (or "points to") the next node.
public class QueueNode<T>
{
/** The value stored in the node. */
T contents;
/** The next node, which provides the front of the rest of the queue. */
QueueNode<T> next;
...
} // class QueueNode<T>
It is often useful to think of node-based queues pictorially. For example, here is a queue containing values A, B, C.
+---+---+ +---+---+ +---+---+ | A | *------>| B | *------>| C | / | +---+---+ +---+---+ +---+---+
Note that we use a slash to represent the end of the sequence. If we add the value D to the queue, we get the following:
+---+---+ +---+---+ +---+---+ +---+---+ | A | *------>| B | *------>| C | *------>| D | / | +---+---+ +---+---+ +---+---+ +---+---+
If we get the A from the beginning of the list, we then
delete that node.
+---+---+ +---+---+ +---+---+
| B | *------>| C | *------>| D | / |
+---+---+ +---+---+ +---+---+
Note that although we tend to draw the nodes in node-based queues in a row from left to right, there is no guarantee that they will be represented sequentially in memory. For example, the three-element queue above might just as easily be stored as follows:
+------------------+
| | front
| +---+---+ | +---+---+
| +-->| C | *----+ | B | *----+
| | +---+---+ +---+---+ |
| | |
| +-----------------------------------------+
|
| +---+---+
+----->| D | / |
+---+---+
Since there is no advantage to drawing node-based queues this way, we will generally choose simpler layouts.
Let us now return to the implementation.
How do we add to the back and remove from the front? We will store two
reference variables, front and back, (which
are also frequently called head and tail).
public class LinkedQueue<T>
implements Queue<T>
{
QueueNode<T> front;
QueueNode<T> back;
...
} // LinkedQueue<T>
When the queue is empty, front and back are null.
Otherwise, front is a reference to the first node in the
structure and back is a reference to the last node. Note
that these may be the same node.
front back \ \ +---+---+ +---+---+ +---+---+ | A | *------>| B | *------>| C | / | +---+---+ +---+---+ +---+---+
As the pictures above suggest, adding to the queue involves generating
a new node, setting the next link of the current last node
to "point to" the new node, and then updating back
to reference the new node as well.
this.back.next = new QueueNode<T>(val);
this.back = this.back.next;
Getting the value at the front is equally easy. We extract it from
the node and then change front to reference the next
node. In Java,
we don't need to do anything to actually remove the first node from
memory; once we have removed the reference to it, it will be "cleaned
up" automatically.
T tmp = this.front.contents;
this.front = this.front.next;
return tmp;
There are, of course, some special situations we need to worry about. You'll learn about these special situations in the lab.
Unfortunately, some bright computer scientist designed the queue before
some other bright computer scientist designed the more general linear
structure. (Does that statement sound familiar? It should; we said the
same thing about stacks.) Hence, the terms that many folks use for the
basic queue operations are not put and get,
but rather enqueue and dequeue.
To make our code more usable, we will continue to use the more general linear structure terms.