队列Queue

我就是我 2022-02-24 17:29 299阅读 0赞

队列是一种数据结构，它只允许在队列尾部（rear）加人一个元素，和从队列头部（front）移除一个元素。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。

### Queue的实现 ###

**1、非阻塞队列**

*  LinkedList是双向链表结构，在添加和删除元素时具有比ArrayList更好的性能。但在 Get 与 Set 方面弱于ArrayList。当然，这些对比都是指数据量很大或者操作很频繁的情况下的对比。
 *  PriorityQueue：实质上维护了一个有序列表，加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。
 *  ConcurrentLinkedQueue：是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以不需要知道队列的大小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。

**2、阻塞队列**  
BlockingQueue 是一个先进先出的队列（Queue），为什么说是阻塞（Blocking）的呢？是因为 BlockingQueue 支持当获取队列元素但是队列为空时，会阻塞等待队列中有元素再返回；也支持添加元素时，如果队列已满，那么等到队列可以放入新元素时再放入。

*  ArrayBlockingQueue：一个内部由数组支持的有界队列。初始化时必须指定队列的容量，还可以设置内部的ReentrantLock是否使用公平锁。但是公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列，此队列按 FIFO（先进先出）原则对元素进行排序。它的思想就是如果BlockQueue是空的，那么从BlockingQueue取东西的操作将会被阻断进入等待状态，直到BlockingQueue进了东西才会被唤醒。同样，如果BlockingQueue是满的，任何试图往里存东西的操作也会被阻断进入等待状态，直到BlockingQueue里有空间才会被唤醒继续操作。
 *  LinkedBlockingQueue：一个内部由链接节点支持的可选有界队列。初始化时不需要指定队列的容量，默认是Integer.MAX\_VALUE，也可以看成容量无限大。此队列按 FIFO（先进先出）排序元素 。
 *  PriorityBlockingQueue：一个内部由优先级堆支持的无界优先级队列。PriorityBlockingQueue是对 PriorityQueue的再次包装，队列中的元素按优先级顺序被移除。
 *  DelayQueue：一个内部由优先级堆支持的、基于时间的调度队列。队列中存放Delayed元素，只有在延迟期满后才能从队列中提取元素。当一个元素的getDelay()方法返回值小于等于0时才能从队列中poll中元素，否则poll()方法会返回null。
 *  SynchronousQueue：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

下表显示了jdk1.5中的阻塞队列的操作：

*  **add**      添加一个元索                            如果队列已满，则抛出一个IIIegaISlabEepeplian异常
 *  **remove**   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
 *  **element**  返回队列头部的元素               如果队列为空，则抛出一个NoSuchElementException异常
 *  **offer**     添加一个元素并返回true           如果队列已满，则返回false
 *  **poll**         移除并返问队列头部的元素    如果队列为空，则返回null
 *  **peek**       返回队列头部的元素               如果队列为空，则返回null
 *  **put**       添加一个元素                            如果队列满，则阻塞
 *  **take**        移除并返回队列头部的元素    如果队列为空，则阻塞

BlockingQueue 对插入操作、移除操作、获取元素操作提供了四种不同的方法用于不同的场景中使用：1、抛出异常；2、返回特殊值（null 或 true/false，取决于具体的操作）；3、阻塞等待此操作，直到这个操作成功；4、阻塞等待此操作，直到成功或者超时指定时间。总结如下：

![20190408155805434.png][]

Queue使用时要尽量避免add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要得到而不移出队头元素，使用  
element()或者peek()方法。对于 BlockingQueue，我们的关注点应该在 put(e) 和 take() 这两个方法，因为这两个方法是带阻塞的。

BlockingQueue 不接受 null 值的插入，相应的方法在碰到 null 的插入时会抛出 NullPointerException 异常。null 值在这里通常用于作为特殊值返回（表格中的第三列），代表 poll 失败。所以，如果允许插入 null 值的话，那获取的时候，就不能很好地用 null 来判断到底是代表失败，还是获取的值就是 null 值。

一个 BlockingQueue 可能是有界的，如果在插入的时候，发现队列满了，那么 put 操作将会阻塞。通常，在这里我们说的无界队列也不是说真正的无界，而是它的容量是 Integer.MAX\_VALUE（21亿多）。

BlockingQueue 是设计用来实现生产者-消费者队列的，当然，你也可以将它当做普通的 Collection 来用，前面说了，它实现了 java.util.Collection 接口。例如，我们可以用 remove(x) 来删除任意一个元素，但是，这类操作通常并不高效，所以尽量只在少数的场合使用，比如一条消息已经入队，但是需要做取消操作的时候。

BlockingQueue 的实现都是线程安全的，但是批量的集合操作如 `addAll`, `containsAll`, `retainAll` 和 `removeAll` 不一定是原子操作。如 addAll(c) 有可能在添加了一些元素后中途抛出异常，此时 BlockingQueue 中已经添加了部分元素，这个是允许的，取决于具体的实现。

BlockingQueue 不支持 close 或 shutdown 等关闭操作，因为开发者可能希望不会有新的元素添加进去，此特性取决于具体的实现，不做强制约束。

最后，BlockingQueue 在生产者-消费者的场景中，是支持多消费者和多生产者的，说的其实就是线程安全问题。

参考：

[https://www.cnblogs.com/yuansc/p/9087044.html][https_www.cnblogs.com_yuansc_p_9087044.html]

[http://www.importnew.com/28053.html][http_www.importnew.com_28053.html]

[20190408155805434.png]: /images/20220224/2e4e0a95cfad4c33acf56feb7de8408c.png
[https_www.cnblogs.com_yuansc_p_9087044.html]: https://www.cnblogs.com/yuansc/p/9087044.html
[http_www.importnew.com_28053.html]: http://www.importnew.com/28053.html