Priority Queue

I have to write an ADT specification for a priority queue. The methods that I am thinking that should be included are:

-getHighPriority() - returns the highest priority item in the list.
-size() returns the size of the priority queue.
-isEmpty() boolean to tell if the queue is empty or not.
-add(item E, priority p) - will add the item to the list, and assign a priority to it
-add(item E) will add the item to the queue, and assign it a priority that is 1 behind the item with the lowest priority contained in the queue.


Am I overlooking important methods? Also, I looked at the java PriorityQueue class, and I do not see any methods that seem to allow you to assign a priority to an item that you add, or is that option not available? Adding an item to the queue automatically assigns the priority?

The priority is based on properties of the objects themselves, either by having the class of the objects held implement Comparable or by using a Comparator. The tutorials will tell you how this is done.

One way of seeing what should go into a priority queue ADT is to look at particular implementations. Java has one in the form of a PriorityQueue.

Where you have getHighPriority() the collections framework has peek() and poll() - the difference is whether the object is removed from the collection: it is returned in either case. And so on for the other methdos you describe.

Some of the PriorityQueue methods make sense because they are part of a more general collection framework. (I am thinking of methods like addAll() which PriorityQueue shares with other types of queue.)

One method you have - add(item E, priority p) - goes "against the grain" of how Java's PriorityQueue works. "The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used." This is the point Fubarable was making. The priority is somehow implicit in the objects themselves.

-----

ADT's are, in the nature of things, abstract. How you implement (or in detail how you *define* them) will depend on the use you intend to make of them: the framework of which they are part, the specific situations in which they will used (as actual code), whether they will be objects about which you intend to derive formal results.

Ah, I missed the ADT/Abstract Data Type bit at the beginning of the OP's post. Please ignore my response and go with pbrockways.

I think I understand your explanations. So in developing the ADT specification, would it be the same as writing an interface for a PriorityQueue?

PriorityQueue is actually a class (ie it has an implementation). But, yes, an interface is just a way - using Java syntax - of writing a specification.