Deque（队列）

素颜马尾好姑娘i 2022-04-24 22:10 188阅读 0赞

### 文章目录 ###

*  Deque
 *   *   *  概述
         *  特点
         *  常用方法
         *  双向队列操作
         *   *   *  插入元素
                 *  移除元素
                 *  获取元素
                 *  栈操作
                 *  引用场景
         *  ArrayDeque
         *   *   *  概述
                 *  特点

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

# Deque #

### 概述 ###

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

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

### 特点 ###

1.  `Deque`是一个Queue的子接口，是一个双端队列，支持在两端插入和移除元素
2.  `deque`支持索引值直接存取。
3.  `Deque`头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。
4.  插入、删除、获取操作支持两种形式：快速失败和返回*null*或*true/false*
5.  不推荐插入*null*元素，*null*作为特定返回值表示队列为空

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

### 常用方法 ###

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th><strong>第一个元素（头部）</strong></th> 
   <th></th> 
   <th>最后一个元素（尾部）</th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><em>抛出异常</em></td> 
   <td><em>特殊值</em></td> 
   <td><em>抛出异常</em></td> 
   <td><em>特殊值</em></td> 
  </tr> 
  <tr> 
   <td><strong>插入</strong></td> 
   <td><a rel="nofollow"><code>addFirst(e)</code></a></td> 
   <td><a rel="nofollow"><code>offerFirst(e)</code></a></td> 
   <td><a rel="nofollow"><code>addLast(e)</code></a></td> 
   <td><a rel="nofollow"><code>offerLast(e)</code></a></td> 
  </tr> 
  <tr> 
   <td><strong>移除</strong></td> 
   <td><a rel="nofollow"><code>removeFirst()</code></a></td> 
   <td><a rel="nofollow"><code>pollFirst()</code></a></td> 
   <td><a rel="nofollow"><code>removeLast()</code></a></td> 
   <td><a rel="nofollow"><code>pollLast()</code></a></td> 
  </tr> 
  <tr> 
   <td><strong>检查</strong></td> 
   <td><a rel="nofollow"><code>getFirst()</code></a></td> 
   <td><a rel="nofollow"><code>peekFirst()</code></a></td> 
   <td><a rel="nofollow"><code>getLast()</code></a></td> 
   <td><a rel="nofollow"><code>peekLast()</code></a></td> 
  </tr> 
 </tbody> 
</table>

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

### 双向队列操作 ###

##### 插入元素 #####

*  **addFirst():** 向队头插入元素，如果元素为*null*，则发生空指针异常
 *  **addLast():** 向队尾插入元素，如果为空，则发生空指针异常
 *  **offerFirst():** 向队头插入元素，如果插入成功返回*true*，否则返回*false*
 *  **offerLast():** 向队尾插入元素，如果插入成功返回*true*，否则返回*false*

##### 移除元素 #####

*  **removeFirst():** 返回并移除队头元素，如果该元素是*null*，则发生*NoSuchElementException*
 *  **removeLast():** 返回并移除队尾元素，如果该元素是*null*，则发生*NoSuchElementException*
 *  **pollFirst():** 返回并移除队头元素，如果队列无元素，则返回*null*
 *  **pollLast():** 返回并移除队尾元素，如果队列无元素，则返回*null*

##### 获取元素 #####

*  **getFirst():** 获取队头元素但不移除，如果队列无元素，则发生*NoSuchElementException*
 *  **getLast():** 获取队尾元素但不移除，如果队列无元素，则发生*NoSuchElementException*
 *  **peekFirst():** 获取队头元素但不移除，如果队列无元素，则返回*null*
 *  **peekLast():** 获取队尾元素但不移除，如果队列无元素，则返回*null*

##### 栈操作 #####

**pop():** 弹出栈中元素，也就是返回并移除队头元素，等价于`removeFirst()`，如果队列无元素，则发生*NoSuchElementException*

**push():** 向栈中压入元素，也就是向队头增加元素，等价于`addFirst()`，如果元素为*null*，则发生*NoSuchElementException*，如果栈空间受到限制，则发生*IllegalStateException*

##### 引用场景 #####

1.  满足FIFO场景时
2.  满足LIFO场景时，曾经在解析XML按标签时使用过栈这种数据结构，但是却选择`Stack`类，如果在进行栈选型时，更推荐使用`Deque`类，应为`Stack`是线程同步

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

### ArrayDeque ###

##### 概述 #####

> `Deque` 接口的大小可变数组的实现。数组双端队列没有容量限制；它们可根据需要增加以支持使用。它们不是线程安全的；在没有外部同步时，它们不支持多个线程的并发访问。禁止 null 元素。此类很可能在用作堆栈时快于 `Stack`，在用作队列时快于 `LinkedList`。

##### 特点 #####

1.  初始容量为16，每次扩容都会翻倍，并且容量一定是2^n。

public ArrayDeque() { 
            elements = new Object[16];
        }

public ArrayDeque(int numElements) { 
            allocateElements(numElements);
        }

private void allocateElements(int numElements) { 
            int initialCapacity = MIN_INITIAL_CAPACITY;
            // Find the best power of two to hold elements.
            // Tests "<=" because arrays aren't kept full.
            if (numElements >= initialCapacity) { 
                initialCapacity = numElements;
                initialCapacity |= (initialCapacity >>>  1);
                initialCapacity |= (initialCapacity >>>  2);
                initialCapacity |= (initialCapacity >>>  4);
                initialCapacity |= (initialCapacity >>>  8);
                initialCapacity |= (initialCapacity >>> 16);
                initialCapacity++;
    
                if (initialCapacity < 0)   // Too many elements, must back off
                    initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
            }
            elements = new Object[initialCapacity];
        }

`>>>`是无符号右移操作，`|`是位或操作，经过五次右移和位或操作可以保证得到大小为2^n -1 的数。最后在自增一，就是 2^n。

1.  增加或删除（head）

public void addFirst(E e) { 
            if (e == null)
                throw new NullPointerException();
            elements[head = (head - 1) & (elements.length - 1)] = e;//注意点
            if (head == tail)
                doubleCapacity();
        }

elements[head = (head - 1) & (elements.length - 1)] = e;

*  当head为0时，实际上是11111111&00001111，结果是00001111，也就是物理数组的尾部15；
 *  当head增长如head+1超过物理数组长度如16时，实际上是00010000&00001111，结果00000000，也就是0，这样就回到了物理数组的头部。
 *  相当于head初始值0时，第一次就将head指针定位到数组末尾了，然后指针从后向前移动。
 *  而addLast就与之相反，控制tail指针，从前向后移动。当tail和head相遇了就说明空间已经满了。（就像一个圆环结构）

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

以上

@Fzxey