Priority Queue ADT Specification

The interface tells us the methods and their types, but it leaves some questions open: what should peek and remove do when the queue is empty, may add be called with null, and what happens to duplicates? The Javadoc below answers them.

/**
 * A PriorityQueue is a collection of elements served in priority order: the
 * element with the highest priority is always the next one removed. Priority is
 * given by the natural ordering of the elements, where a smaller element has the
 * higher priority. Duplicate elements are allowed.
 * @param <T> the type of elements in this priority queue
 */
public interface PriorityQueue<T extends Comparable<T>> {
  /**
   * Adds an item to this priority queue.
   * @param item the item to be added to this priority queue
   * @throws IllegalArgumentException if the item is null
   */
  void add(T item);

  /**
   * Returns, without removing, the highest-priority item in this priority queue.
   * @return the highest-priority item
   * @throws NoSuchElementException if this priority queue is empty
   */
  T peek();

  /**
   * Removes the highest-priority item from this priority queue. To inspect that
   * item, call peek before removing it.
   * @throws NoSuchElementException if this priority queue is empty
   */
  void remove();

  /**
   * Returns the number of items in this priority queue.
   * @return the number of items in this priority queue
   */
  int size();
}

When the queue is empty there is no highest-priority element, so peek and remove throw a NoSuchElementException. This is the same choice we made for the stack and the queue: asking for an element that is not there is an error. A caller who is not sure whether the queue is empty can check size first.

add throws an IllegalArgumentException when the argument is null. A null has no natural ordering, so there is no way to compare it against the other elements, and no way to know where it belongs or when it should come out.

Notice also that add returns nothing. A priority queue holds duplicates, so every add of a non-null item succeeds and there is nothing to report. When two elements are equal, or tie for the highest priority, both stay in the queue. The contract does not promise which of the tied elements remove will take out first. If a problem needs ties broken a particular way, say oldest first, that ordering has to be built into how the elements compare. The queue will not do it for you.

A priority queue that serves the smallest element first, as ours does by default, is called a min priority queue. An implementation may also offer a second constructor that takes a Comparator<T>, the external ordering from the generics chapter. Supplying one that reverses the order gives a max priority queue, which serves the largest first. The interface cannot state this itself, since interfaces declare no constructors, so each implementation documents the option on its own class.

The next chapter implements this interface, and its code comes with a suite of tests for it in the PriorityQueueTest class.