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

- Queue Basics
- A Queue Interface
- A Vector-Based Implemention of Queues
- A Linked Implementation of Queues
- Terminology

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 that *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.)

packageusername.linear;/** * A linear structure that follows the "first in, first out" policy. * * @author Samuel A. Rebelsky * @version 1.1 of March 2006 */publicinterfaceQueue<T>extendsLinearStructure<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. */publicvoidput(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. */publicT 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 less recently than val. */publicT peek();/** * Determine if the queue is empty. */publicbooleanisEmpty(); } // interface Queue<T>

At first glance, it may seem as easy to implement queues with vectors as it was to implement stacks with vectors. 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 vector , we'll need to implement get by removing values from
the front of the vector. That, in itself, is not a problem. However,
we'll soon find that we run off the end of the vector , even if we have
empty space at the front of the vector. In stacks, we simply allow the
vector to grow and grow and grow. However, it seems wasteful to grow
the vector when there's empty space available for new elements at the
beginning of the vector. It is possible to wrap around

, and add
new elements to the empty spaces at the beginning of the array. However,
such an implementation has many subtleties that novice programmers
(and even some expert programmers) tend to handle incorrectly.

You can also use the `remove(`

method of the
vecdtor class to remove the initial value in the vector. However,
that method is amazingly inefficient - it must __int__ index)*shift* every
remaining element left one space.

Is there an easier 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, which contain 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 the next node.

publicclassQueueNode<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 the queue A, B, C.

+---+---+ +---+---+ +---+---+ | * | *------>| * | *------>| * | / | +-|-+---+ +-|-+---+ +-|-+---+ | | | v v v 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:

+---+---+ +---+---+ +---+---+ +---+---+ | * | *------>| * | *------>| * | *------>| * | / | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | | | | v v v v A B C D

If we get the A from the beginning of the list, we then delete that node.

+---+---+ +---+---+ +---+---+ | * | *------>| * | *------>| * | / | +-|-+---+ +-|-+---+ +-|-+---+ | | | v v v B C D

Note that although we tend to draw then 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, a three-element queue above might just as easily be stored as follows

+------------------+ | | front | +---+---+ | +---+---+ | +-->| | *----+ | | *----+ | | +---+---+ +---+---+ | | | | | +-----------------------------------------+ | | +---+---+ +----->| | / | +---+---+

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 use two
variables, `front`

and `back`

.

publicclassLinkedQueue<T>implementsQueue<T> { QueueNode<T> front; QueueNode<T> back; ... } // LinkedQueue<T>

As the pictures above suggest, adding to the queue simply involves setting the next link of the current back and then moving the back.

this.back.next =newQueueNode<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 the front to use the next node.

T tmp =this.front.contents;this.front =this.front.next;returntmp;

When the queue is empty, front is

.
__null__

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.

Monday, 7 March 2005 [Samuel A. Rebelsky]

- Created.

Tuesday, 7 March 2006 [Samuel A. Rebelsky]

- Updated for generics.
- Updated to use vectors rather than arrays for the first strategy.
- Added the code for the
`QueueNode`

class and the fields of`LinkedQueue`

. - Other, more minor, edits.

This page was generated by
Siteweaver on Tue Mar 7 09:50:13 2006.

The source to the page was last modified on Tue Mar 7 09:50:12 2006.

This page may be found at `http://www.cs.grinnell.edu/~rebelsky/TAO/Readings/queues.html`

.

You may wish to validate this page's HTML ; ; Check with Bobby

rebelsky@grinnell.edu