A priority queue is a generalization of both the stack and queue. The difference is in the method of selecting which item to next pop off the data structure. A priority queue usually assigns a number to each item (the priority) and the item with the highest number (priority) is the next to come off. A priority queue that acts like a stack assigns the highest priority to new elements and the queue does exactly the opposite.

The priority queue is used extensively in process scheduling by the operating system; In this setting the priority may be determined by a combination of factors including how much time has elapsed since the process last ran.

Due to the nature of the priority queue it is most often implemented as a binary heap which gives the following complexities (see Big O notation):

Operation | Complexity | Description |
---|---|---|

push | $O(\log n)$ | puts an element into the queue |

pop | $O(\log n)$ | takes the highest priority item out of the queue |