首页 > 集合 > 实现

队列实现

Queue实现分为通用和并发两种实现。

通用队列实现

如前一节所述，LinkedList实现了Queue接口，提供了先进先出（FIFO）队列操作，如add、poll等。

PriorityQueue类是基于堆数据结构的优先级队列。该队列根据构造时指定的顺序对元素进行排序，可以是元素的自然顺序或显式Comparator指定的顺序。

队列的检索操作——poll、remove、peek和element——访问队列头部的元素。队列的头部是根据指定的顺序最小的元素。如果多个元素的值最小相等，则头部是这些元素之一；如果存在多个最小值相等的元素，则随机选择一个。

PriorityQueue及其迭代器实现了Collection和Iterator接口的所有可选方法。在方法iterator中提供的迭代器不能保证以任何特定顺序遍历PriorityQueue的元素。要进行有序遍历，考虑使用Arrays.sort(pq.toArray())。

并发队列实现

java.util.concurrent包含一组同步的Queue接口和类。BlockingQueue通过在检索元素时等待队列变为非空以及在存储元素时等待队列中有可用空间来扩展Queue。此接口由以下类实现：

• LinkedBlockingQueue — 一个可选有界FIFO阻塞队列，由链表节点支持
• ArrayBlockingQueue — 一个有界FIFO阻塞队列，由数组支持
• PriorityBlockingQueue — 一个无界阻塞优先级队列，由堆支持
• DelayQueue — 一个基于时间的调度队列，由堆支持
• SynchronousQueue — 使用BlockingQueue接口的简单会合机制

在JDK 7中，TransferQueue 是一种特殊的BlockingQueue，它允许将元素添加到队列中的代码有选择地等待（阻塞），直到另一个线程中的代码取出元素为止。 TransferQueue只有一个实现：

• LinkedTransferQueue — 基于链式节点的无界TransferQueue