java队列Queue、双端队列Deque

以你之姓@ 2022-07-16 08:15 247阅读 0赞

注意：这都只是**接口**而已

**1、Queue**

**[API][]**

在java5中新增加了[Java][].util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。

1.  **public** **interface** Queue<E> 
2.  **extends** Collection<E>

除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。

每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）**。**

![0a3af09c-84c1-3192-a396-788778793770.jpg][]

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。

**在 FIFO 队列中，所有的新元素都插入队列的末尾，移除元素从队列头部移除。**

Queue使用时要**尽量避免Collection的add()和remove()方法**，**而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常**。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

![6c5cd3f1-9cb8-3af5-8be6-558e880fb143.jpg][]

offer 方法可插入一个元素，否则返回 false。这与 Collection.add 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。

remove() 和 poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove() 和 poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。

element() 和 peek() 返回，但不移除，队列的头。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

**2、Deque**

[API][API 1]

Java代码 ![收藏代码][icon_star.png]

1.  **public** **interface** Deque<E> 
2.  **extends** Queue<E>

**一个线性 collection，支持在两端插入和移除元素。**

名称 deque 是“**double ended queue（双端队列）**”的缩写，通常读为“deck”。

大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

![b1956624-3f28-312c-808a-301e67059ce8.jpg][]

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。因为此接口**继承了队列接口Queue**，所以其每种方法也存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

**a、****在将双端队列用作队列时，将得到 FIFO（先进先出）行为**。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

![f769ea83-1a83-3bec-84df-52342cbe00b8.jpg][]

**b、****用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类**。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

![610121eb-2298-36a9-918a-73cdaa085df9.jpg][]

[API]: http://dlc.sun.com.edgesuite.net/jdk/jdk-api-localizations/jdk-api-zh-cn/publish/1.6.0/html/zh_CN/api/java/util/Queue.html#peek%28%29
[Java]: http://lib.csdn.net/base/javaee
[0a3af09c-84c1-3192-a396-788778793770.jpg]: /images/20220716/59b54044d79644df8b051b83fcb6d3c2.png
[6c5cd3f1-9cb8-3af5-8be6-558e880fb143.jpg]: /images/20220716/eed9b59190da47ceba4a8f54fb0667db.png
[API 1]: http://dlc.sun.com.edgesuite.net/jdk/jdk-api-localizations/jdk-api-zh-cn/publish/1.6.0/html/zh_CN/api/java/util/Deque.html
[icon_star.png]: /images/20220716/070bc24e2f0f46ecae548f533422d219.png
[b1956624-3f28-312c-808a-301e67059ce8.jpg]: /images/20220716/0d5242b5c050499eb23f9283052f4c09.png
[f769ea83-1a83-3bec-84df-52342cbe00b8.jpg]: /images/20220716/496f9f790dff4919976ca284ac1e276d.png
[610121eb-2298-36a9-918a-73cdaa085df9.jpg]: /images/20220716/492f16bf735d4147abf5bf77538695fc.png