|
|
|
|
|
|
|
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: arrays, lists, or vectors. 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 is defined by the following operations:
To demonstrate a queue implementation, I will take advantage of the LinkedList class from Chapter 14. 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.
public class Queue {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.
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.
public Object removeFirst () {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.
The performance of addLast is very different.
public void addLast (Object obj) {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.
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.
Here's what a linked Queue implementation looks like:
public class Queue {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.
public void insert (Object obj) {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.
public Object remove () {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.
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 15.12. 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).
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:
public class Queue {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 more more sense.
public void insert (Object item) {insert looks very much like push in Section 15.12; 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.
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:
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:
next++;A fancy alternative is to use the modulus operator:
next = (next + 1) % array.length;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."
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?
if ((next + 1) % array.length == first)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.
The Priority Queue ADT has the same interface as the Queue ADT, but different semantics. The interface is:
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.
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.
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.
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:
public class PriorityQueue {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.
public PriorityQueue () {insert is similar to push:
public void insert (Comparable item) {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:
public Comparable remove () {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.
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:
Comparable comp = new Comparable (); // ERRORYou'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.
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.
PriorityQueue pq = new PriorityQueue ();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:
Rectangle rect = new Rectangle ();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.
To get items out of the queue, we have to reverse the process:
while (!pq.empty ()) {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.
Finally, let's looks 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:
public class Golfer implements Comparable {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:
public int compareTo (Object obj) {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:
Golfer tiger = new Golfer ("Tiger Woods", 61);And put them in the queue:
pq.insert (tiger);When we pull them out:
while (!pq.empty ()) {They appear in descending order (for golfers):
Tiger Woods 61When 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.
|
|
|
|
|
|
|