Priority queue
A priority queue is an abstract data type supporting the following two operations:
- add an element to the queue with an associated priority
- remove the element from the queue that has the highest priority, and return it
This makes removing an element O(n) in the number of elements in the queue, which is somewhat inefficient if the queue gets large; a heap is a more efficient way to implement a priority queue for a large number of elements.
The Standard Template Library (STL), part of the C++ programming language 1998 standard, specifies "priority_queue" as one of the STL container adaptor class templatess. Unlike actual STL containers, it does not allow iteration of its elements.
Priority queuing can be used to manage limited resources such as bandwidth on a transmission line from a network router. In the event of outgoing traffic queuing due to insufficient bandwidth, all other queues can be halted to send the traffic from the highest priority queue upon arrival. This ensures that the prioritized traffic (such as real-time traffic, e.g. a RTP stream of a voip connection) is forwarded with the least delay and the least likelihood of being rejected due to a queue reaching its maximum capacity. All other traffic can be handled when the highest priority queue is empty. Another approach used is to send disproportionately more traffic from higher priority queues.
Usually a limitation (policer) is set to limit the bandwidth that traffic from the highest priority queue can take, in order to prevent high priority packets from choking off all other traffic. This limit is usually never reached due to higher lever control instances such as the Cisco Callmanager, which can be programmed to inhibit calls which would exceed the programmed bandwidth limit.
See also: scheduling, queuing theoryApplications