The Way of the Java/Queues

Queues and Priority Queues

This chapter presents two ADTs: Queues and Priority Queues. In real life a queue is a line of customers waiting for service of some kind. In most cases, the first customer in line is the next customer to be served. There are exceptions, though. For example, at airports customers whose flight is leaving imminently are sometimes taken from the middle of the queue. Also, at supermarkets a polite customer might let someone with only a few items go first.

The rule that determines who goes next is called a queueing discipline. The simplest queueing discipline is called FIFO, for ``first-in-first-out. The most general queueing discipline is priority queueing, in which each customer is assigned a priority, and the customer with the highest priority goes first, regardless of the order of arrival. The reason I say this is the most general discipline is that the priority can be based on anything: what time a flight leaves, how many groceries the customer has, or how important the customer is. Of course, not all queueing disciplines are ``fair, but fairness is in the eye of the beholder.

The Queue ADT and the Priority Queue ADT have the same set of operations and their interfaces are the same. The difference is in the semantics of the operations: a Queue uses the FIFO policy, and a Priority Queue (as the name suggests) uses the priority queueing policy.

As with most ADTs, there are a number of ways to implement queues. Since a queue is a collection of items, we can use any of the basic mechanisms for storing collections, including arrays and lists. Our choice among them will be based in part on their performance--- how long it takes to perform the operations we want to perform--- and partly on ease of implementation.

The queue ADT

ADT!Queue
Queue ADT
implementation!Queue
queue!List implementation

The queue ADT is defined by the following operations:

description

[constructor:] Create a new, empty queue.

[insert:] Add a new item to the queue.

[remove:] Remove and return an item from the queue. The item that is returned is the first one that was added.

[empty:] Check whether the queue is empty.

description

To demonstrate a queue implementation, I will take advantage of the LinkedList class from Chapter list. Also, I will assume that we have a class named Customer that defines all the information about each customer, and the operations we can perform on customers.

As far as our implementation goes, it does not matter what kind of object is in the Queue, so we can make it generic. Here is what the implementation looks like.

verbatim public class Queue

   public LinkedList list;

   public Queue () 
       list = new List ();
   

   public boolean empty () 
       return list.empty ();
   

   public void insert (Object obj) 
       list.addLast (obj);
   

   public Object remove () 
       return list.removeFirst ();
   

verbatim

A queue object contains a single instance variable, which is the list that implements it. For each of the other methods, all we have to do is invoke one of the methods from the LinkedList class.

Veneer

veneer
performance hazard
performance analysis

An implementation like this is called a veneer. In real life, veneer is a thin coating of good quality wood used in furniture-making to hide lower quality wood underneath. Computer scientists use this metaphor to describe a small piece of code that hides the details of an implementation and provides a simpler, or more standard, interface.

This example demonstrates one of the nice things about a veneer, which is that it is easy to implement, and one of the dangers of using a veneer, which is the performance hazard!

Normally when we invoke a method we are not concerned with the details of its implementation. But there is one ``detail we might want to know---the performance characteristics of the method. How long does it take, as a function of the number of items in the list?

First let's look at removeFirst.

verbatim

   public Object removeFirst () 
       Object result = head;
       if (head != null) 
           head = head.next;
       
       return result;
   

verbatim

There are no loops or function calls here, so that suggests that the run time of this method is the same every time. Such a method is called a constant time operation. In reality, the method might be slightly faster when the list is empty, since it skips the body of the conditional, but that difference is not significant.

constant time

The performance of addLast is very different.

verbatim

   public void addLast (Object obj) 
       // special case: empty list
       if (head == null) 
           head = new Node (obj, null);
           return;
       
       Node last;
       for (last = head; last.next != null; last = last.next) 
           // traverse the list to find the last node
       
       last.next = new Node (obj, null);
   

verbatim

The first conditional handles the special case of adding a new node to an empty list. In this case, again, the run time does not depend on the length of the list. In the general case, though, we have to traverse the list to find the last element so we can make it refer to the new node.

This traversal takes time proportional to the length of the list. Since the run time is a linear function of the length, we would say that this method is linear time. Compared to constant time, that's very bad.

linear time

Linked Queue

queue!linked implementation
linked queue

We would like an implementation of the Queue ADT that can perform all operations in constant time. One way to accomplish that is to implement a linked queue, which is similar to a linked list in the sense that it is made up of zero or more linked Node objects. The difference is that the queue maintains a reference to both the first and the last node, as shown in the figure.

figure=figs/queue1.eps,width=4in

Here's what a linked Queue implementation looks like:

verbatim public class Queue

   public Node first, last;

   public Queue () 
       first = null;
       last = null;
   

   public boolean empty () 
       return first == null;
   

verbatim

So far it is straightforward. In an empty queue, both first and last are null. To check whether a list is empty, we only have to check one of them.

insert is a little more complicated because we have to deal with several special cases.

verbatim

   public void insert (Object obj) 
       Node node = new Node (obj, null);
       if (last != null) 
           last.next = node;
       
       last = node;
       if (first == null) 
           first = last;
       
   

verbatim

The first condition checks to make sure that last refers to a node; if it does then we have to make it refer to the new node.

The second condition deals with the special case where the list was initially empty. In this case both first and last refer to the new node.

remove also deals with several special cases.

verbatim

   public Object remove () 
       Node result = first;
       if (first != null) 
           first = first.next;
       
       if (first == null) 
           last = null;
       
       return result;
   

verbatim

The first condition checks whether there were any nodes in the queue. If so, we have to copy the next node into first. The second condition deals with the special case that the list is now empty, in which case we have to make last null.

As an exercise, draw diagrams showing both operations in both the normal case and in the special cases, and convince yourself that they are correct.

Clearly, this implementation is more complicated than the veneer implementation, and it is more difficult to demonstrate that it is correct. The advantage is that we have achieved the goal: both insert and remove are constant time.

Circular buffer

queue!circular buffer implementation
circular buffer
buffer!circular

Another common implementation of a queue is a circular buffer. ``Buffer is a general name for a temporary storage location, although it often refers to an array, as it does in this case. What it means to say a buffer is ``circular should become clear in a minute.

The implementation of a circular buffer is similar to the array implementation of a stack, as in Section arraystack. The queue items are stored in an array, and we use indices to keep track of where we are in the array. In the stack implementation, there was a single index that pointed to the next available space. In the queue implementation, there are two indices: first points to the space in the array that contains the first customer in line and next points to the next available space.

The following figure shows a queue with two items (represented by dots).

figure=figs/queue2.eps,width=4in

There are two ways to think of the variables first and last. Literally, they are integers, and their values are shown in boxes on the right. Abstractly, though, they are indices of the array, and so they are often drawn as arrows pointing to locations in the array. The arrow representation is convenient, but you should remember that the indices are not references; they are just integers.

Here is an incomplete array implementation of a queue:

verbatim public class Queue

   public Object[] array;
   public int first, next;

   public Queue () 
       array = new Object[128];
       first = 0;
       next = 0;
   

   public boolean empty () 
       return first == next;
   

verbatim

The instance variables and the constructor are straightforward, although again we have the problem that we have to choose an arbitrary size for the array. Later we will solve that problem, as we did with the stack, by resizing the array if it gets full.

The implementation of empty is a little surprising. You might have thought that first == 0 would indicate an empty queue, but that neglects the fact that the head of the queue is not necessarily at the beginning of the array. Instead, we know that the queue is empty if head equals next, in which case there are no items left. Once we see the implementation of insert and remove, that situation will make more sense.

verbatim

   public void insert (Object item) 
       array[next] = item;
       next++;
   

   public Object remove () 
       Object result = array[first];
       first++;
       return result;
   

verbatim

insert looks very much like push in Section arraystack; it puts the new item in the next available space and then increments the index.

remove is similar. It takes the first item from the queue and then increments first so it refers to the new head of the queue. The following figure shows what the queue looks like after both items have been removed.

figure=figs/queue3.eps,width=4in

It is always true that next points to an available space. If first catches up with next and points to the same space, then first is referring to an ``empty location, and the queue is empty. I put ``empty in quotation marks because it is possible that the location that first points to actually contains a value (we do nothing to ensure that empty locations contain null); on the other hand, since we know the queue is empty, we will never read this location, so we can think of it, abstractly, as empty.

As an exercise, fix remove so that it returns null if the queue is empty.

The next problem with this implementation is that eventually it will run out of space. When we add an item we increment next and when we remove an item we increment first, but we never decrement either. What happens when we get to the end of the array?

The following figure shows the queue after we add four more items:

figure=figs/queue4.eps,width=4in

The array is now full. There is no ``next available space, so there is nowhere for next to point. One possibility is that we could resize the array, as we did with the stack implementation. But in that case the array would keep getting bigger regardless of how many items were actually in queue. A better solution is to wrap around to the beginning of the array and reuse the spaces there. This ``wrap around is the reason this implementation is called a circular buffer.

One way to wrap the index around is to add a special case whenever we increment an index:

verbatim

       next++;
       if (next == array.length) next = 0; 

verbatim

A fancy alternative is to use the modulus operator:

verbatim

       next = (next + 1) 

verbatim

Either way, we have one last problem to solve. How do we know if the queue is really full, meaning that we cannot insert another item? The following figure shows what the queue looks like when it is ``full.

figure=figs/queue5.eps,width=4in

There is still one empty space in the array, but the queue is full because if we insert another item, then we have to increment next such that next == first, and in that case it would appear that the queue was empty!

To avoid that, we sacrifice one space in the array. So how can we tell if the queue is full?

verbatim

       if ((next + 1) 

verbatim

And what should we do if the array is full? In that case resizing the array is probably the only option.

As an exercise, put together all the code from this section and write an implementation of a queue using a circular buffer that resizes itself when necessary.

Priority queue

priority queue!ADT
ADT!Priority Queue

The Priority Queue ADT has the same interface as the Queue ADT, but different semantics. The interface is:

description

[constructor:] Create a new, empty queue.

[insert:] Add a new item to the queue.

[remove:] Remove and return an item from the queue. The item that is returned is the one with the highest priority.

[empty:] Check whether the queue is empty.

description

The semantic difference is that the item that is removed from the queue is not necessarily the first one that was added. Rather, it is whatever item in the queue has the highest priority. What the priorities are, and how they compare to each other, are not specified by the Priority Queue implementation. It depends on what the items are that are in the queue.

For example, if the items in the queue have names, we might choose them in alphabetical order. If they are bowling scores, we might choose from highest to lowest, but if they are golf scores, we would go from lowest to highest.

generic
data structure!generic

So we face a new problem. We would like an implementation of Priority Queue that is generic---it should work with any kind of object---but at the same time the code that implements Priority Queue needs to have the ability to compare the objects it contains.

We have seen a way to implement generic data structures using Objects, but that does not solve this problem, because there is no way to compare Objects unless we know what type they are.

The answer lies in a new Java feature called an abstract class.

Abstract class

abstract class
class!abstract
Comparable
abstract class!Comparable

An abstract class is a set of classes. The abstract class definition specifies the requirements a class must satisfy to be a member.

Often abstract classes have names that end in ``able to indicate the fundamental capability the abstract class requires. For example, any class that provides a method named draw can be a member of the abstract class named Drawable. Any class that contains a method named start can be a member of the abstract class Runnable.

As of Java 2, Java provides a built-in abstract class that we can use in an implementation of a Priority Queue. It is called Comparable, and it means what it says. Any class that belongs to the Comparable abstract class has to provide a method named compareTo that compares two objects and returns a value indicating whether one is larger or smaller than the other, or whether they are the same.

Many of the built-in Java classes are members of the Comparable abstract class, including numeric wrapper classes like Integer and Double.

In the next section I will show how to write an ADT that manipulates an abstract class. Then we will see how to write a new (concrete) class that belongs to an existing abstract class. Then we will see how to write a new abstract class.

Array implementation of Priority Queue

implementation!Priority Queue
priority queue!array implementation

In the implementation of the Priority Queue, every time we specify the type of the items in the queue, we specify the abstract class Comparable. For example, the instance variables are an array of Comparables and an integer:

verbatim public class PriorityQueue

   private Comparable[] array;
   private int index;

verbatim

As usual, index is the index of the next available location in the array. The instance variables are declared private so that other classes cannot have direct access to them.

The constructor and empty are similar to what we have seen before. I chose the initial size for the array arbitrarily.

verbatim

   public PriorityQueue () 
       array = new Comparable [16];
       index = 0;
   

   public boolean empty () 
       return index == 0;
   

verbatim

insert is similar to push:

verbatim

   public void insert (Comparable item) 
       if (index == array.length) 
           resize ();
       
       array[index] = item;
       index++;
   

verbatim

I omitted the implementation of resize. The only substantial method in the class is remove, which has to traverse the array to find and remove the largest item:

verbatim

   public Comparable remove () 
       if (index == 0) return null;

       int maxIndex = 0;

       // find the index of the item with the highest priority
       for (int i=1; i<index; i++) 
           if (array[i].compareTo (array[maxIndex]) > 0) 
               maxIndex = i;
           
       
       Comparable result = array[maxIndex];

       // move the last item into the empty slot
       index--;
       array[maxIndex] = array[index];
       return result;
  

verbatim

As we traverse the array, maxIndex keeps track of the index of the largest element we have seen so far. What it means to be the ``largest is determined by compareTo. In this case the compareTo method is provided by the Integer class, and it does what we expect---larger (more positive) numbers win.

A Priority Queue client

client
abstract class
class!abstract

The implementation of Priority Queue is written entirely in terms of Comparable objects, but there is no such thing as a Comparable object! Go ahead, try to create one:

verbatim

   Comparable comp = new Comparable ();       // ERROR

verbatim

You'll get a compile-time message that says something like ``java.lang.Comparable is an interface. It can't be instantiated. In Java, abstract classes are called interfaces. I have avoided this word so far because it also means several other things, but now you have to know.

interface

Why can't abstract classes be instantiated? Because an abstract class only specifies requirements (you must have a compareTo method); it does not provide an implementation.

To create a Comparable object, you have to create one of the objects that belongs to the Comparable set, like Integer. Then you can use that object anywhere a Comparable is called for.

verbatim

       PriorityQueue pq = new PriorityQueue ();
       Integer item = new Integer (17);
       pq.insert (item);

verbatim

This code creates a new, empty Priority Queue and a new Integer object. Then it inserts the Integer into the queue. insert is expecting a Comparable as a parameter, so it is perfectly happy to take an Integer. If we try to pass a Rectangle, which does not belong to Comparable, we get a compile-time message like, ``Incompatible type for method. Explicit cast needed to convert java.awt.Rectangle to java.lang.Comparable.

That's the compiler telling us that if we want to make that conversion, we have to do it explicitly. We might try to do what it says:

verbatim Rectangle rect = new Rectangle (); pq.insert ((Comparable) rect); verbatim

But in that case we get a run-time error, a ClassCastException. When the Rectangle tries to pass as a Comparable, the run-time system checks whether it satisfies the requirements, and rejects it. So that's what we get for following the compiler's advise.

ClassCastException
exception!ClassCastException

To get items out of the queue, we have to reverse the process:

verbatim

   while (!pq.empty ()) 
       item = (Integer) pq.remove ();
       System.out.println (item);
   

verbatim

This loop removes all the items from the queue and prints them. It assumes that the items in the queue are Integers. If they were not, we would get a ClassCastException.

The Golfer class

Golfer
class!Golfer
abstract class!implementing
Comparable

Finally, let's look at how we can make a new class that belongs to Comparable. As an example of something with an unusual definition of ``highest priority, we'll use golfers:

verbatim public class Golfer implements Comparable

   String name;
   int score;

   public Golfer (String name, int score) 
       this.name = name;
       this.score = score;
   

verbatim

The class definition and the constructor are pretty much the same as always; the difference is that we have to declare that Golfer implements Comparable. In this case the keyword implements means that Golfer implements the interface specified by Comparable.

If we try to compile Golfer.java at this point, we get something like ``class Golfer must be declared abstract. It does not define int compareTo(java.lang.Object) from interface java.lang.Comparable. In other words, to be a Comparable, Golfer has to provide a method named compareTo. So let's write one:

verbatim

   public int compareTo (Object obj) 
       Golfer that = (Golfer) obj;

       int a = this.score;
       int b = that.score;

       // for golfers, low is good!
       if (a < b) return 1;
       if (a > b) return -1;
       return 0;
   

verbatim

Two things here are a little surprising. First, the parameter is an Object. That's because in general the caller doesn't know what type the objects are that are being compared. For example, in PriorityQueue.java when we invoke compareTo, we pass a Comparable as a parameter. We don't have to know whether it is an Integer or a Golfer or whatever.

Inside compareTo we have to convert the parameter from an Object to a Golfer. As usual, there is a risk when we do this kind of cast: if we cast to the wrong type we get an exception.

Finally, we can create some golfers:

verbatim

       Golfer tiger = new Golfer ("Tiger Woods", 61);
       Golfer phil = new Golfer ("Phil Mickelson", 72);
       Golfer hal = new Golfer ("Hal Sutton", 69);

verbatim

And put them in the queue:

verbatim

       pq.insert (tiger);
       pq.insert (phil);
       pq.insert (hal);

verbatim

When we pull them out:

verbatim

       while (!pq.empty ()) 
           golfer = (Golfer) pq.remove ();
           System.out.println (golfer);
       

verbatim

They appear in descending order (for golfers):

verbatim

       Tiger Woods     61
       Hal Sutton      69
       Phil Mickelson  72

verbatim

When we switched from Integers to Golfers, we didn't have to make any changes in PriorityQueue.java at all. So we succeeded in maintaining a barrier between PriorityQueue and the classes that use it, allowing us to reuse the code without modification. Furthermore, we were able to give the client code control over the definition of compareTo, making this implementation of PriorityQueue more versatile.

Glossary

queue
queueing discipline
FIFO
priority queue
veneer
constant time
linear time
performance hazard
linked queue
circular buffer
abstract class
interface

description

[queue:] An ordered set of objects waiting for a service of some kind.

[queueing discipline:] The rules that determine which member of a queue is removed next.

[FIFO:] ``first in, first out, a queueing discipline in which the first member to arrive is the first to be removed.

[priority queue:] A queueing discipline in which each member has a priority determined by external factors. The member with the highest priority is the first to be removed.

[Priority Queue:] An ADT that defines the operations one might perform on a priority queue.

[veneer:] A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client.

[performance hazard:] A danger associated with a veneer that some of the methods might be implemented inefficiently in a way that is not apparent to the client.

[constant time:] An operation whose run time does not depend on the size of the data structure.

[linear time:] An operation whose run time is a linear function of the size of the data structure.

[linked queue:] An implementation of a queue using a linked list and references to the first and last nodes.

[circular buffer:] An implementation of a queue using an array and indices of the first element and the next available space.

[abstract class:] A set of classes. The abstract class specification lists the requirements a class must satisfy to be included in the set.

[interface:] The Java word for an abstract class. Not to be confused with the more broad meaning of the word interface.