Queues and Stacks

Imagine adding the numbers 5, 2, 8, and 1 to a collection, in that order, and then calling remove once. Which number comes back? The answer depends on the kind of collection you are using. This article looks at the priority queue, a collection in which elements leave in order of priority rather than in the order they arrived. Making a prediction before you read the trace is the fastest way to check whether the priority rule is clear to you.

A regular queue works like a line at a checkout. The first element added is the first element removed. A priority queue replaces that arrival-order rule with a priority rule. Each element you add competes with the others on priority, and the queue always hands back the one with the minimal priority among those still waiting.

This changes the question you ask while reading a priority queue program. You no longer ask only what came in first. At each step you ask two questions: what was just added, and which element now has the minimal priority. The answer to the second question is the one that will leave next.

A priority queue offers two methods that the course focuses on. The add method places an object into the queue. The object must be of the element type T that the queue was declared with. The remove method takes no arguments, removes the element of minimal priority, and returns it. The returned value is also of type T.

The source also mentions addAll, which adds every element of a collection named coll to the queue in one call. It is a convenience for loading many elements at once; the add and remove rules stay the same.

The easiest way to see the rule at work is to track what the queue holds after each call. Start with an empty queue and apply the four add calls from the prediction, then one remove. The diagram shows the set of stored elements after each step. Notice that the diagram lists the contents as a set; it does not claim anything about the order the queue keeps them internally.

The same four values can leave the queue in a completely different sequence from the one they arrived in. The comparison below lines up the order of additions against the order of removals. Each removal takes the smallest value still waiting, so the removal column is always sorted from smallest to largest, while the addition column follows the order of the add calls.

The source uses the phrase minimal priority, and it notes that for integers the smallest value is the one with minimal priority in this example. The rule that the removed element has minimal priority stays the same for any element type. Only the meaning of minimal depends on how the elements are compared. So if you change the element type, you must ask what minimal means for that type before predicting the output.

The source states that remove throws an exception if the queue is empty. That means you cannot call remove as many times as you like. If you call it when nothing is left, the program fails. The guard against this is the isEmpty check, which reports whether any elements remain. Each remove should happen only while isEmpty says there is at least one element left.

This is the standard pattern for draining a priority queue: keep calling remove until isEmpty reports that nothing is left. The source's own loop guards every call this way, so each removal happens only while there is at least one element.