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.