可以搜索微信公眾號【Jet 與編程】查看更多精彩文章
原文發佈於自己的博客平臺【http://www.jetchen.cn/deque/】
堆棧（Stack）數據結構也是常用的數據結構之一，但是官方建議使用 Deque 這種雙邊隊列才替代之，所以，本文就對 Deque 這種數據結構進行詳細地剖析下。
簡介
這是數據結構系列的第二篇文章，上篇文章見： 【詳解 HashMap 數據結構】
Deque 是 java.util 包下的一個接口，源碼首行也講明瞭，它是 double ended queue 的縮寫，所以本文稱之為 雙邊隊列，顧名思義，它和隊列 Queue 是有千絲萬縷的聯繫的，看源碼也可知，它繼承自 java.util.Queue 接口。
<code>public
interface
Deque
<E
>extends
Queue
<E
> {} /<code>
另外，Deque 發音同 deck，不要讀錯了哦。
其實源碼的註釋很多都蠻有意思的，比如上面的發音，便是在源碼中寫到的
LIFO：Deque VS Stack
萬物存在皆有因，那 Deque 存在的意義是啥呢？我個人的理解是劍指 Stack。
因為我們都知道，在處理 LIFO (Last-In-First-Out) 數列的時候，即後進先出，首先想到的數據模型便是 Stack（棧數據結構），因為它有兩個最關鍵的方法：push(e) （壓棧） 和 pop()（彈棧），Java util 包下也是有相關類的：
<code>public
class
Stack
<E
>extends
Vector
<E
> {} /<code>
但是看源碼內的註釋，很明確地告訴我們，不建議使用 Stack 類，而使用 Deque stack = new ArrayDeque(); 來取代：
為什麼呢？首先參考 SO 上面的回答：stack overflow
下面來簡單說下：
1、首先，正如 SO 上面的回答，Stack 類繼承自 Vector，確實蠻奇怪的，有點混亂，畢竟雜家也是個很實在的數據結構啊，怎麼樣也得和 Map 一樣作為一個接口而存在吧，不然每個擴展類都要繼承 Stack 類，蠻奇怪的。
2、其次，Stack 最大的弊端就是同步，即線程安全，因為它在方法上面都使用了重量級的鎖命令 synchronized，這樣做造成的最大的問題就是性能會大打折扣，即效率低下，例如：public synchronized E pop()。
上文已經提到了，Deque 是雙邊隊列，雙邊的意思是即可以操作 頭數據 也可以操作 尾數據，所以自然而然， Deque 是可以實現 Stack 中的 push(e) 和 pop() 方法的，兩者的方法對應圖如下：
DequeStack說明addFirst(e)push(e)向棧頂插入數據，失敗則拋出異常offerFirst(e)無向棧頂插入數據，失敗則返回 falseremoveFirst()pop()獲取並刪除棧頂數據，失敗則拋出異常pollFirst()無獲取並刪除棧頂數據，失敗則返回 nullgetFirst()peek()查詢棧頂數據，失敗則拋出異常peekFirst()無查詢棧頂數據，失敗則返回 null
FIFO：Deque VS Queue
上文提到，Deque 繼承自 Queue 接口，所以他們倆肯定是有相關性的，下面我們就來看看這兩個接口是個啥情況。
首先，Queue 是隊列，數據結構是 FIFO（First-In-First-Out），即先進先出，意思是元素的添加，是發生在末尾的，而元素的刪除，則發生在首部。
類似上圖中的 add(e) 和 element() 方法，在 Deque 中都是有對應的方法的。
兩個接口中方法的對應圖如下：
DequeQueue說明addLast(e)add(e)尾部插入數據，失敗則拋出異常offerLast(e)offer(e)尾部插入數據，失敗則返回 falseremoveFirst()remove()獲取並刪除首部數據，失敗則拋出異常pollFirst()poll()獲取並刪除首部數據，失敗則返回 nullgetFirst()element()查詢首部數據，失敗則拋出異常peekFirst()peek()查詢首部數據，失敗則返回 null
使用場景
無論是 Stack，還是 Queue，它們都只能操作頭或尾，那如何同時支持操作頭和尾呢，這便體現出 Deque（雙邊隊列）的優勢了，即 Deque 既可以用於 LIFO，也可以用於 FIFO。
Deque 和 List 最大的區別是，它不支持索引訪問元素，但是 Deque 也提供了相應的方法來操作指定的元素：removeFirstOccurrence(Object o) 和 removeLastOccurrence(Object o)
Deque 是一個數據結構的標準接口，只定義標準方法，其下有若干實現了該接口的類，比如常用的 ArrayDeque、LinkedList、ConcurrentLinkedDeque。
由上面列舉的三個類是我們常用的實現，看它們的名字我們便可以知曉，ArrayDeque 是基於數組的，LinkedList和 ConcurrentLinkedDeque很顯然是基於鏈表的，並且後者是線程安全的。
這三個類的主要特性和應用場景見下表：
類特點 & 使用場景ArrayDeque①數組 ②大小可變，涉及自動擴容 ③無序 ④不可插入 null ⑤線程不安全LinkedList①鏈表 ②大小可變，不需要擴容 ③無序 ④可以插入 null ⑤線程不安全ConcurrentLinkedDeque①鏈表 ②大小可變，不需要擴容 ③無序 ④不可以插入 null ⑤線程安全
繼承關係見下圖：
ArrayDeque
下面我們從源碼層面來介紹下它最重要的幾個方法：添加 和 刪除，另外，ArrayDeque 底層是一個數組，所以自然而然會聯想到數組固有的方法：
擴容。數據結構
數據結構很簡單，沒啥好說的，我們應該也能猜出來，就是一個數組，然後因為要操作頭和尾，所以肯定有頭部索引和尾部索引。
<code>public
class
ArrayDeque
<E
>extends
AbstractCollection
<E
>implements
Deque
<E
>,Cloneable
,Serializable
{transient
Object[] elements;transient
int
head;transient
int
tail;private
static
final
int
MIN_INITIAL_CAPACITY =8
; } /<code>
構造函數
構造函數有三個，分別是：
- 無參構造（初始化一個容量為 16 的數組）
- 有參構造，參數是指定的容量
- 有參構造，參數是 Collection 集合
下面介紹下第二個有參構造，即初始化一個指定容量的數組，為什麼要單獨拎出來說呢，因為初始化的容量是有一定規則的。
<code>
elements = new
Object
[calculateSize(numElements)];
}
/<code>還記得在上文 【詳解 HashMap 數據結構】 中，談過了它在擴容的時候的騷操作，此處 ArrayDeque 也是如初一折，即擴容的時候，容量始終是 2 的冪次方。
和 HashMap 不一樣的是，HashMap 中有一個 -1 的動作，即計算而得的容量始終是大於等於參數的，例如參數是 8，則返回值也是 8。但是此處計算而得的容量始終是大於參數的，例如參數是 8，返回值則是 16。
<code>計算容量，容量始終是 2 的冪次方// 容量最小是 8// 返回值是 ＞ 傳入的參數的private static int calculateSize(int numElements) {
容量最小值
int
initialCapacity = MIN_INITIAL_CAPACITY;
if
(numElements >= initialCapacity) {
initialCapacity
=numElements;
initialCapacity
|= (initialCapacity >>> 1);
initialCapacity
|= (initialCapacity >>> 2);
initialCapacity
|= (initialCapacity >>> 4);
initialCapacity
|= (initialCapacity >>> 8);
initialCapacity
|= (initialCapacity >>> 16);
initialCapacity++;
if
(initialCapacity < 0)
initialCapacity
>>>= 1;
}
return
initialCapacity;
}
/<code>
上面的位運算很精妙，就不再詳細贅述了，詳細可以看之前的文章 【詳解 HashMap 數據結構】 ，然後精妙的計算邏輯，就貼一張前文中的圖吧：
大致原理就是保證低位上面，每一位都是 1，最後 +1，這樣就是實現了除了高位以外全是 0，也就是 2 的冪次方。
擴容
當容量不夠的時候肯定就要進行擴容了，擴容的具體時機暫不進行敘述，等到下文講 添加元素 方法的時候再詳細描述下，下面就著源碼講解下擴容的方法：
<code>
assert
head == tail;
int
p = head;
int
n = elements.length;
int
r = n - p;
int
newCapacity = n <1
;
if
(newCapacity 0
)
throw
new
IllegalStateException("Sorry, deque too big"
);
Object[] a = new
Object[newCapacity];
System.arraycopy(elements, p, a, 0
, r);
System.arraycopy(elements, 0
, a, r, p);
elements = a;
head = 0
;
tail = n;
}
/<code>注意，上面的擴容操作，涉及到元數據拷貝至新數組的操作，此處是通過兩次拷貝來進行的，為什麼這麼做呢，其實這就涉及到元素的添加了，下文接著講。
添加元素
元素的添加，我們介紹兩個典型的方法，其它的呢大同小異，分別是 首部添加 和 尾部添加，即 addFirst(E e) 和 addLast(E e)。
<code>
if
(e == null
)
throw
new
NullPointerException();
elements[head = (head - 1
) & (elements.length - 1
)] = e;
if
(head == tail)
doubleCapacity();
/<code><code>
if
(e == null
)
throw
new
NullPointerException();
elements[tail] = e;
if
( (tail = (tail + 1
) & (elements.length - 1
)) == head)
doubleCapacity();
}
/<code>從上面的源碼中我們可以看到幾個很有趣的點：
- 首部添加元素時，先將 head 索引前移，然後再添加元素，說明，head 索引處是有元素的
- 尾部添加元素時，直接在 tail 索引處添加元素，然後再將 tail 索引後移，說明，tail 索引處是沒有元素的
- 從中可以看出數組中肯定有一個索引處是空的，即 tail 索引處，所以可以先插入元素然後再進行擴容的判斷
- 擴容的判斷條件是判斷首尾索引是否一致，即 head == tail
首部添加元素的時候，如果 head 是 0，那麼在進行 elements[head = (head - 1) & (elements.length - 1)] = e; 操作的時候，head - 1 = -1，elements.length - 1 = 15，將兩者進行“與”運算的時候，因為“-1”的二進制其實是 “1111 1111... 1111”，即所有位上都是 1，所以與運算得出的結果自然也是 15。
下面畫圖來介紹下元素的插入過程：
移除元素
Deque 是不可以按照索引來刪除元素的，只能刪除首尾的元素（pollFirst()、pollLast()），或者刪除指定內容的元素（removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)）
<code>
int h = head;
E result = (E) elements[h];
if
(result == null
)
return
null
;
elements[h] = null
;
head = (h + 1
) & (elements.length - 1
);
return
result;
}
int t = (tail - 1
) & (elements.length - 1
);
E result = (E) elements[t];
if
(result == null
)
return
null
;
elements[t] = null
;
tail = t;
return
result;
}
/<code>刪除元素的代碼其實也很簡單，有趣的是刪除了元素之後的數組，可能出現數組的前部和後部有數據，也可能出現數組的中間部分有數據，也就是說 head 不一定總等於 0，tail 也不一定總是比 head 大。所以我們稱之為 環形數組。
LinkedList
LinkedList 相對 ArrayDeque 而言，底層數數據結構由數組變為了鏈表，所以 LinkedList 自然而然是不用進行擴容操作的。
LinkedList 是由一個個的 Node 組成的，每個 node 都會記錄當前的數據、前一個 node 和 後一個 node，所以就形成了一個 鏈表，數據模型如下：
具體的方法就不贅述了，比較簡單。
<code>public
class
LinkedList
<E
>extends
AbstractSequentialList
<E
>implements
List
<E
>,Deque
<E
>,Cloneable
,java
.io
.Serializable
{transient
int
size =0
;transient
Node first;transient
Node last;private
static
class
Node
<E
> { E item; Node next; Node prev; Node(Node prev, E element, Node next) {this
.item = element;this
.next = next;this
.prev = prev; } } } /<code>
ConcurrentLinkedDeque
上文提到的 ArrayDeque 和 LinkedList 都是 List 包下的工具類，而 ConcurrentLinkedDeque 就有意思了，它是 concurrent 併發包下面的類，其實看名字我們應該也能略知其中的一二了，它是線程安全的無邊雙向隊列。
它內部的變量等都是使用 volatile 來修飾的，所以它是線程安全的。因為 volatile 的作用就是阻止變量訪問前後的指令重排，從而保證指令的順序執行。
另外，其內部使用了 自旋+CAS 的非阻塞算法來保證線程併發訪問時的數據一致性，例如在首部添加元素 addFirst(E e) 方法：
<code>public
void
addFirst
(E e
) { linkFirst(e); }private
void
linkFirst
(E e
) { checkNotNull(e); final Node newNode =new
Node(e); restartFromHead:for
(;;)for
(Node h = head, p = h, q;;) {if
((q = p.prev) !=null
&& (q = (p = q).prev) !=null
) p = (h != (h = head)) ? h : q;else
if
(p.next == p)continue
restartFromHead;else
{ newNode.lazySetNext(p);if
(p.casPrev(null
, newNode)) {if
(p != h) casHead(h, newNode);return
; } } } } /<code>
執行流程大致為：
- 從 head 節點開始向前循環找到 first 節點 (p.prev==null&&p.next!=p)
- 然後通過 lazySetNext 設置新節點的 next 節點為 first
- CAS 修改 first 的 prev 為新節點。
注意這裡 CAS 指令成功後會判斷 first 節點是否已經跳了兩個節點，只有在跳了兩個節點才會 CAS 更新 head，這也是為了節省 CAS 指令執行開銷。
ConcurrentLinkedDeque 數據結構，本文就簡單提了一點，詳細的分析會放到後面介紹 java.util.concurrent 包（簡稱 JUC 包）的時候再詳細闡述，尤其是 ConcurrentLinkedDeque 中的節點刪除的操作，需要詳細分析下。
小結
Deque 雙邊隊列這種數據結構，為兩端數據的操作提供了便捷性，並且也是官方建議的替換 Stack 數據結構的方案，另外，其不僅有最常用的 ArrayDeque，也有線程安全的 ConcurrentLinkedDeque，數據結構也是比較豐富的。
