TAO of Java: Queues

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.

Queue Basics

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

A Queue Interface

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 less recently than val.
   */
  public T peek();

  /**
   * Determine if the queue is empty.
   */
  public boolean isEmpty();

} // interface Queue<T>

A Vector-Based Implemention of Queues

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(int index) method of the vecdtor class to remove the initial value in the vector. However, that method is amazingly inefficient - it must shift every remaining element left one space.

A Linked Implementation of Queues

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.

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>

Picturing Node-Based Queues

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

              +---+---+     +---+---+     +---+---+
              | * | *------>| * | *------>| * | / |
              +-|-+---+     +-|-+---+     +-|-+---+
                |             |             |
                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.

Implementing Queue Methods with Nodes

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.

public class LinkedQueue<T>
  implements Queue<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 = 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 the front to use the next node.

     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.

Terminology

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.

History

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

Samuel A. Rebelsky
rebelsky@grinnell.edu