队列
分类
- 普通队列。
- 优先队列。
- 以广义队列的角度来看，栈也可以理解为一个队列。
优先队列
普通队列是FIFO的。优先队列的出队顺序与入队顺序无关，和优先级相关。
为什么要用
动态选择优先级最高的任务执行。
概述
与普通队列的最大区别是出队的操作。
实现
接口：
- 入队与其他队列无区别。
- 出队需要找出优先级最高的元素。
底层数据结构
- 普通线性结构。入队O(1)出队O(N)。
- 顺序线性结构。使用排序好的线性结构，入队O(lg n)出队O(1)。
- 堆。入队O(lg n)出队O(lg n)。
适用性
在N个元素选出前M个元素。在1000000个元素选出前100名。
Java
Java当中的优先队列：PriorityQueue<E>。