Contents |

Abstractly, a priority queue is an ordered list of elements. Inserting
into a priority queue entails placing the new element in its proper
position to maintain the ordering. Thus, the point of the insertion
can be anywhere in the list: front, interior, or back.
Removing from a priority queue means removing an extreme element, either
the `smallest' or the `largest'. An auxiliary value, called a *rank*,
is used to decide which element is the smallest or largest.

A priority queue is neither a stack nor a queue, but is similar to both. Both a stack and a queue order their elements by the insertion time, whereas a priority queue orders its elements by their ranks. Here is an example:

pq = new PriorityQueue(); pq.enqueue("alpha",3); //element first, rank second pq.enqueue("beta",2); pq.enqueue("gamma",4); pq.enqueue("delta",1);

At this point, the ordered list of elements would be:

("delta","beta","alpha","gamma")

Typically, but not always, the smallest rank is the highest priority,
so a removal (dequeuing) would remove the element `"delta"`

.

Generally, the structure of a priority queue resembles that of a queue or a stack.

The terms used in describing a priority queue are:

- enqueue
- The name of the operation that adds an element, with a given rank, to a priority queue.
- dequeue
- The name of the operation that removes the element
with the smallest (largest) rank.
Usually, the element removed is returned by the
*dequeue*operation, with the rank being thrown away. - peek
- Like
*dequeue*, but the element is not removed from the queue. Consecutive peeks, with no intervening enqueues or dequeues, always return the same element. - rank
- The value used to order the elements in a priority queue.
Each element is associated with a
*rank*. - priority
- Another name for
*rank*. - first-come-first-served
- A strategy for dealing with the insertion
of an element with the same rank as a previously enqueued, but not
yet dequeued, element. Under this strategy, the newly inserted element
should be dequeued
*after*the previously enqueued element.

Priority queues are used in some important graph algorithms as well as in discrete-event simulations.

A priority queue, where the rank of an insertion is forced to be greater than the rank of the previous insertion implements a stack. In such a case, the last element inserted has the highest rank and thus is the next element to come off the priority queue. Conversely, forcing the rank of an insertion to be less than that of the previous insertion implements a queue.

Priority queues are often built from singly-linked lists or heaps. If the priority queue is based upon a linked-list, a tail pointer is not needed (although if present, it can provide a significant optimization if enqueues generally end up at the back of the list).

The operations of a priority queue have the same name as the operations
of a
queue,
namely *enqueue*, *dequeue*, *peek*, and *isEmpty*.
Of course, the *enqueue* operation takes a rank as well as the element
to be enqueued.

The enqueuing operation can take anywhere from constant to linear time, depending on the underlying data structure used to implement the priority queue. The dequeuing operation can take anywhere from constant to logarithmic time, again depending on the underlying structure. The choice of the underlying structure depends on whether one wishes for faster enqueues (at the cost of slower dequeues) or vice versa.

Priority queues are generally not traversed.

- This is a question.
- This is one possible answer
- This is another possible answer

Contents |