The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Priority Queue

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

Create a new, empty queue.
Add a new item to the queue.
Remove and return an item from the queue. The item that is returned is the one with the highest priority.
Check whether the queue is empty.

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.

Last Update: 2011-01-24