【Java】Java双端队列Deque使用详解

矫情吗；* 2021-09-27 10:54 334阅读 0赞

Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。

> 关于Queue的介绍可以看上一篇文章：[Java队列Queue使用详解][Java_Queue]

#### Deque有三种用途： ####

*  普通队列(一端进另一端出):  
    `Queue queue = new LinkedList()`或`Deque deque = new LinkedList()`  
    
 *  双端队列(两端都可进出)  
    `Deque deque = new LinkedList()`  
    
 *  堆栈  
    `Deque deque = new LinkedList()`

> 注意：Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法：push()、pop()、peek()。

Deque是一个线性collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

下表总结了上述 12 种方法：

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td align="CENTER" colspan="2"> <b>第一个元素 (头部)</b></td> 
   <td align="CENTER" colspan="2"> <b>最后一个元素 (尾部)</b></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td align="CENTER"><em>抛出异常</em></td> 
   <td align="CENTER"><em>特殊值</em></td> 
   <td align="CENTER"><em>抛出异常</em></td> 
   <td align="CENTER"><em>特殊值</em></td> 
  </tr> 
  <tr> 
   <td><b>插入</b></td> 
   <td>addFirst(e)</td> 
   <td>offerFirst(e)</td> 
   <td>addLast(e)</td> 
   <td>offerLast(e)</td> 
  </tr> 
  <tr> 
   <td><b>删除</b></td> 
   <td>removeFirst()</td> 
   <td>pollFirst()</td> 
   <td>removeLast()</td> 
   <td>pollLast()</td> 
  </tr> 
  <tr> 
   <td><b>检查</b></td> 
   <td>getFirst()</td> 
   <td>peekFirst()</td> 
   <td>getLast()</td> 
   <td>peekLast()</td> 
  </tr> 
 </tbody> 
</table>

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

<table> 
 <tbody> 
  <tr> 
   <td align="CENTER"> <b>Queue方法</b></td> 
   <td align="CENTER"> <b>等效Deque方法</b></td> 
  </tr> 
  <tr> 
   <td>add(e)</td> 
   <td>addLast(e)</td> 
  </tr> 
  <tr> 
   <td>offer(e)</td> 
   <td>offerLast(e)</td> 
  </tr> 
  <tr> 
   <td>remove()</td> 
   <td>removeFirst()</td> 
  </tr> 
  <tr> 
   <td> poll()</td> 
   <td>pollFirst()</td> 
  </tr> 
  <tr> 
   <td>element()</td> 
   <td>getFirst()</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>peekFirst()</td> 
  </tr> 
 </tbody> 
</table>

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

<table> 
 <tbody> 
  <tr> 
   <td align="CENTER"> <b>堆栈方法</b></td> 
   <td align="CENTER"> <b>等效Deque方法</b></td> 
  </tr> 
  <tr> 
   <td>push(e)</td> 
   <td>addFirst(e)</td> 
  </tr> 
  <tr> 
   <td>pop()</td> 
   <td>removeFirst()</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>peekFirst()</td> 
  </tr> 
 </tbody> 
</table>

[Java_Queue]: https://blog.csdn.net/devnn/article/details/82591349