ADTpriority_queue and the STL priority_queue Container Adaptor
A priority_queue, rather than being a standard FIFO structure, is a collection of entries, each of which has a "key", which is called the "priority" of the entry, and which determines the order in which the entries are removed from the priority_queue (though they may enter the priority_queue in any order).
In the context of programming, for example, a large number of tasks may be waiting for the CPU, and since some of these tasks have a higher priority than others, the set of tasks waiting for time on the CPU forms a "priority_queue".
The STL priority_queue is not a "first class" container in its own right, like the vector, deque and list, but is instead based on a tightly controlled interface to an underlying vector container class (by default). This is why it is called a container "adaptor".
| priority_queue Operations | |
|---|---|
| Generic (ADT) | Specific (STL) |
| Construct a priority_queue |
priority_queue<T> pq;
priority_queue<T> pq(binPred); priority_queue<T> pq(inIter1, inIter2); priority_queue<T> pq(inIter1, inIter2, binPred); There are also a couple of other constructors which we do not discuss. |
| Test for emptiness | empty() |
| Add a value | push(val) |
| Remove value with highest priority | pop() |
| Get value with highest priority, without removing it | top() |
| Get current size | size() |
The above interface for a priority queue contains the usual operations you would find if you looked up "priority queue" in most any textbook on data structures, and these are in fact the operations provided by the STL.
The priority_queue container adaptor does not support any iterators.
The priority_queue container adaptor should be used in any situation where components may be entered into the container in any order but need to come out of the container in some "order of priority".