A Guide to Deque

你的名字 2024-03-30 16:47 55阅读 0赞

**Deque 是 “***`double ended queue`***（双端队列）” 的缩写，通常读为 “***`deck`***”，是一个线性集合，支持在两端插入和移除元素。**

--------------------

## 三种用途 ##

### 双端队列 (两端都可进出) ###

Deque<Integer> deque  = new LinkedList<>();

<table> 
 <thead> 
  <tr> 
   <th align="left">操作</th> 
   <th align="left">Special value</th> 
   <th align="left">Throws exception</th> 
   <th align="left">Special value</th> 
   <th align="left">Throws exception</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><code>Insert</code></td> 
   <td align="left"><strong><code>offerFirst(e)</code></strong></td> 
   <td align="left"><code>addFirst(e)</code></td> 
   <td align="left"><strong><code>offerLast(e)</code></strong></td> 
   <td align="left"><code>addLast(e)</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Remove</code></td> 
   <td align="left"><strong><code>pollFirst()</code></strong></td> 
   <td align="left"><code>removeFirst()</code></td> 
   <td align="left"><strong><code>pollLast()</code></strong></td> 
   <td align="left"><code>removeLast()</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Examine</code></td> 
   <td align="left"><strong><code>peekFirst()</code></strong></td> 
   <td align="left"><code>getFirst()</code></td> 
   <td align="left"><strong><code>peekLast()</code></strong></td> 
   <td align="left"><code>getLast()</code></td> 
  </tr> 
 </tbody> 
</table>

# Insert
    offerFirst(e)   offerLast(e)
    addFirst(e)     addLast(e)
    
    # Remove
    pollFirst()     pollLast()     null
    removeFirst()   removeLast()   NoSuchElementException
    
    # Examine
    peekFirst()     peekLast()     null
    getFirst()      getLast()      NoSuchElementException

### 普通队列 (一端进另一端出) ###

Queue<Integer> queue = new LinkedList();
    Deque<Integer> deque  =new LinkedList();

<table> 
 <thead> 
  <tr> 
   <th align="left">操作</th> 
   <th align="left"><strong>Queue方法 Special value</strong></th> 
   <th align="left"><strong>等效Deque方法 Special value</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><code>Insert</code></td> 
   <td align="left"><strong><code>offer(e)</code></strong></td> 
   <td align="left"><strong><code>offerLast(e)</code></strong></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Remove</code></td> 
   <td align="left"><strong><code>poll()</code></strong></td> 
   <td align="left"><strong><code>pollFirst()</code></strong></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Examine</code></td> 
   <td align="left"><strong><code>peek()</code></strong></td> 
   <td align="left"><strong><code>peekFirst()</code></strong></td> 
  </tr> 
  <tr> 
   <td align="left"></td> 
   <td align="left"><strong>Queue方法 Throws exception</strong></td> 
   <td align="left"><strong>等效Deque方法 Throws exception</strong></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Insert</code></td> 
   <td align="left"><code>add(e)</code></td> 
   <td align="left"><code>addLast(e)</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Remove</code></td> 
   <td align="left"><code>remove()</code></td> 
   <td align="left"><code>removeFirst()</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Examine</code></td> 
   <td align="left"><code>element()</code></td> 
   <td align="left"><code>getFirst()</code></td> 
  </tr> 
 </tbody> 
</table>

### 堆栈 ###

Deque<Integer> deque = new LinkedList<>();
     Stack<Integer> stack = new Stack<>();

<table> 
 <thead> 
  <tr> 
   <th align="left">操作</th> 
   <th align="left">Stack Throws exception</th> 
   <th align="left">等效Deque方法 Throws exception</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><code>Insert</code></td> 
   <td align="left"><code>push(e)</code></td> 
   <td align="left"><code>addFirst(e)</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Remove</code></td> 
   <td align="left"><code>pop()</code></td> 
   <td align="left"><code>removeFirst()</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>Examine</code></td> 
   <td align="left"><code>peek()</code></td> 
   <td align="left"><code>getFirst()</code></td> 
  </tr> 
 </tbody> 
</table>

## 参考 ##

[https://blog.csdn.net/qq\_42398447/article/details/125957910][https_blog.csdn.net_qq_42398447_article_details_125957910]  
[https://blog.csdn.net/devnn/article/details/82716447][https_blog.csdn.net_devnn_article_details_82716447]  
[https://www.likecs.com/show-203674798.html][https_www.likecs.com_show-203674798.html]

[https_blog.csdn.net_qq_42398447_article_details_125957910]: https://blog.csdn.net/qq_42398447/article/details/125957910
[https_blog.csdn.net_devnn_article_details_82716447]: https://blog.csdn.net/devnn/article/details/82716447
[https_www.likecs.com_show-203674798.html]: https://www.likecs.com/show-203674798.html#%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97