A priority queue is like a regular stack or queue data structure, but in addition, each element has a priority associated with it. Elements in the queue are served according to their priorities listed. Higher priority elements are served before the lower priority ones. When there are elements with the same priority, they are served according to their order in the queue.
Minimum operations performed by priority queue:
- add element to the queue with associated priority.
- remove element from queue according to highest priority.
Priority queues can be implemented in different ways:
- insert elements as they come and when an element has to be removed from , do linear search in array to find out the highest priority element and then remove it from the queue.
- insert elements to the priority queue in the descending order of priorities so that when an element has to be dequeued, it just needs to removed from the starting.
- The best way to implement priority queue is using heaps. Here, elements can be inserted into the heap, heap sort can be performed and then while removing, the element deleted will be the element at the top of the heap, ie, the highest priority element.
We can also infer from here that,
Minimum number of queues needed to implement the priority queue:
Two. One queue is used for actual storing of data and another for storing the priorities.
Priority queue has many applications in real life. For eg, it can be used in bandwidth management, where the prioritized traffic has to be forwarded with the least delay possible.