Priority Queue

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

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.

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 Node, but that does not solve this problem, because there is no way to compare Node unless we know what type the cargo is. So basically, to implement a priority queue, we will have to create compare functions that will compare the cargo of the nodes.