可以搜索微信公眾號【Jet 與編程】查看更多精彩文章

原文發(fā)布于自己的博客平臺【http://www.jetchen.cn/deque/】

堆棧（Stack）數(shù)據(jù)結(jié)構(gòu)也是常用的數(shù)據(jù)結(jié)構(gòu)之一，但是官方建議使用 Deque 這種雙邊隊列才替代之键袱，所以话瞧，本文就對 Deque 這種數(shù)據(jù)結(jié)構(gòu)進行詳細地剖析下疚鲤。

簡介

這是數(shù)據(jù)結(jié)構(gòu)系列的第二篇文章，上篇文章見： 【詳解 HashMap 數(shù)據(jù)結(jié)構(gòu)】

Deque 是 java.util 包下的一個接口镇防，源碼首行也講明了钦椭，它是 double ended queue 的縮寫盈简，所以本文稱之為 雙邊隊列，顧名思義携取，它和隊列 Queue 是有千絲萬縷的聯(lián)系的攒钳，看源碼也可知，它繼承自 java.util.Queue<E> 接口雷滋。

public interface Deque<E> extends Queue<E> {}

另外不撑，Deque 發(fā)音同 deck文兢，不要讀錯了哦。

其實源碼的注釋很多都蠻有意思的焕檬，比如上面的發(fā)音姆坚，便是在源碼中寫到的

LIFO：Deque VS Stack

萬物存在皆有因，那 Deque 存在的意義是啥呢实愚？我個人的理解是劍指 Stack兼呵。

Stack 模型

因為我們都知道，在處理 LIFO (Last-In-First-Out) 數(shù)列的時候腊敲，即后進先出击喂，首先想到的數(shù)據(jù)模型便是 Stack（棧數(shù)據(jù)結(jié)構(gòu)），因為它有兩個最關(guān)鍵的方法：push(e) （壓棧） 和 pop()（彈棧）碰辅，Java util 包下也是有相關(guān)類的：

/**
 * @since   JDK1.0
 */
public class Stack<E> extends Vector<E> {}

但是看源碼內(nèi)的注釋懂昂，很明確地告訴我們，不建議使用 Stack 類没宾，而使用 Deque<Integer> stack = new ArrayDeque<Integer>(); 來取代：

不建議使用 Stack

為什么呢凌彬？首先參考 SO 上面的回答：stack overflow

下面來簡單說下：

1、首先循衰，正如 SO 上面的回答饿序，Stack 類繼承自 Vector，確實蠻奇怪的羹蚣，有點混亂原探，畢竟雜家也是個很實在的數(shù)據(jù)結(jié)構(gòu)啊，怎么樣也得和 Map 一樣作為一個接口而存在吧顽素，不然每個擴展類都要繼承 Stack 類咽弦，蠻奇怪的。

2胁出、其次型型，Stack 最大的弊端就是同步，即線程安全全蝶，因為它在方法上面都使用了重量級的鎖命令 synchronized闹蒜，這樣做造成的最大的問題就是性能會大打折扣，即效率低下抑淫，例如：public synchronized E pop()绷落。

上文已經(jīng)提到了，Deque 是雙邊隊列始苇，雙邊的意思是即可以操作 頭數(shù)據(jù) 也可以操作 尾數(shù)據(jù)砌烁，所以自然而然， Deque 是可以實現(xiàn) Stack 中的 push(e) 和 pop() 方法的，兩者的方法對應圖如下：

FIFO：Deque VS Queue

上文提到捐下，Deque 繼承自 Queue 接口顿天，所以他們倆肯定是有相關(guān)性的，下面我們就來看看這兩個接口是個啥情況蔑担。

首先牌废，Queue 是隊列，數(shù)據(jù)結(jié)構(gòu)是 FIFO（First-In-First-Out）啤握，即先進先出鸟缕，意思是元素的添加，是發(fā)生在末尾的排抬，而元素的刪除懂从，則發(fā)生在首部。

Queue 模型

類似上圖中的 add(e) 和 element() 方法蹲蒲，在 Deque 中都是有對應的方法的番甩。

兩個接口中方法的對應圖如下：

使用場景

無論是 Stack，還是 Queue表锻，它們都只能操作頭或尾恕齐，那如何同時支持操作頭和尾呢，這便體現(xiàn)出 Deque（雙邊隊列）的優(yōu)勢了瞬逊，即 Deque 既可以用于 LIFO显歧，也可以用于 FIFO。

Deque 和 List 最大的區(qū)別是，它不支持索引訪問元素，但是 Deque 也提供了相應的方法來操作指定的元素：
removeFirstOccurrence(Object o) 和 removeLastOccurrence(Object o)

Deque 是一個數(shù)據(jù)結(jié)構(gòu)的標準接口辩越，只定義標準方法，其下有若干實現(xiàn)了該接口的類敦间，比如常用的 ArrayDeque、LinkedList束铭、ConcurrentLinkedDeque廓块。

由上面列舉的三個類是我們常用的實現(xiàn)，看它們的名字我們便可以知曉契沫，ArrayDeque 是基于數(shù)組的带猴，LinkedList和 ConcurrentLinkedDeque很顯然是基于鏈表的，并且后者是線程安全的懈万。

這三個類的主要特性和應用場景見下表：

繼承關(guān)系見下圖：

繼承圖

ArrayDeque

下面我們從源碼層面來介紹下它最重要的幾個方法：添加 和 刪除口予，另外，ArrayDeque 底層是一個數(shù)組涕侈，所以自然而然會聯(lián)想到數(shù)組固有的方法：擴容沪停。

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)很簡單，沒啥好說的裳涛，我們應該也能猜出來木张，就是一個數(shù)組，然后因為要操作頭和尾端三，所以肯定有頭部索引和尾部索引舷礼。

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
    // 底層的數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組
    transient Object[] elements; 

    // 頭部索引
    transient int head;

    // 尾部索引
    transient int tail;
    
    // 最小容量是 8
    private static final int MIN_INITIAL_CAPACITY = 8;
}

構(gòu)造函數(shù)

構(gòu)造函數(shù)有三個，分別是：

1. 無參構(gòu)造（初始化一個容量為 16 的數(shù)組）
2. 有參構(gòu)造郊闯，參數(shù)是指定的容量
3. 有參構(gòu)造妻献，參數(shù)是 Collection 集合

下面介紹下第二個有參構(gòu)造，即初始化一個指定容量的數(shù)組团赁，為什么要單獨拎出來說呢旋奢，因為初始化的容量是有一定規(guī)則的。

// 初始化一個指定容量的 Deque
private void allocateElements(int numElements) {
    // 初始化出來的數(shù)組容量然痊，始終是 2 的冪次方
    elements = new Object[calculateSize(numElements)];
}

還記得在上文 【詳解 HashMap 數(shù)據(jù)結(jié)構(gòu)】 中至朗，談過了它在擴容的時候的騷操作，此處 ArrayDeque 也是如初一折剧浸，即擴容的時候锹引，容量始終是 2 的冪次方。

和 HashMap 不一樣的是唆香，HashMap 中有一個 -1 的動作嫌变，即計算而得的容量始終是大于等于參數(shù)的，例如參數(shù)是 8躬它，則返回值也是 8腾啥。但是此處計算而得的容量始終是大于參數(shù)的，例如參數(shù)是 8，返回值則是 16倘待。

// 計算容量疮跑，容量始終是 2 的冪次方
// 容量最小是 8
// 返回值是 ＞ 傳入的參數(shù)的
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;
}

上面的位運算很精妙，就不再詳細贅述了凸舵，詳細可以看之前的文章 【詳解 HashMap 數(shù)據(jù)結(jié)構(gòu)】 祖娘，然后精妙的計算邏輯，就貼一張前文中的圖吧：

大致原理就是保證低位上面啊奄，每一位都是 1渐苏，最后 +1，這樣就是實現(xiàn)了除了高位以外全是 0菇夸，也就是 2 的冪次方琼富。

擴容原理圖

擴容

當容量不夠的時候肯定就要進行擴容了，擴容的具體時機暫不進行敘述庄新，等到下文講 添加元素 方法的時候再詳細描述下鞠眉，下面就著源碼講解下擴容的方法：

// 擴容，擴容至 2 倍大小
private void doubleCapacity() {
    // 斷言摄咆，true 則繼續(xù)凡蚜，false 則拋 AssertionError 異常
    assert head == tail;
    int p = head;
    // 當前容量
    int n = elements.length;
    // p 右側(cè)的元素數(shù)量
    int r = n - p; 
    // 新容量擴大兩倍
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    // 新數(shù)組
    Object[] a = new Object[newCapacity];
    // 拷貝 head 右側(cè)的數(shù)據(jù)，拷至目標數(shù)組0索引處
    // 說下5個參數(shù)分別是：元數(shù)據(jù)吭从、元數(shù)據(jù)中需要拷貝的元素的起始位置朝蜘、目標數(shù)據(jù)、目標數(shù)據(jù)中需要粘貼的元素的起始位置涩金、數(shù)據(jù)長度
    System.arraycopy(elements, p, a, 0, r);
    // 拷貝 head 左側(cè)的數(shù)據(jù)谱醇，拷至目標數(shù)組 r 索引處
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    // 首部索引
    head = 0;
    // 尾部索引
    tail = n;
}

注意，上面的擴容操作步做，涉及到元數(shù)據(jù)拷貝至新數(shù)組的操作副渴，此處是通過兩次拷貝來進行的，為什么這么做呢全度，其實這就涉及到元素的添加了煮剧，下文接著講。

添加元素

元素的添加将鸵，我們介紹兩個典型的方法勉盅，其它的呢大同小異，分別是 首部添加 和 尾部添加顶掉，即 addFirst(E e) 和 addLast(E e)草娜。

// 首部添加元素
public void addFirst(E e) {    
    // 插入的元素不能為空，否則拋出空指針異常
    if (e == null)       
        throw new NullPointerException();    
    // 首部索引減一痒筒，并將該索引處的元素設置為 e
    elements[head = (head - 1) & (elements.length - 1)] = e;    
    // 判斷是否需要擴容
    if (head == tail)        
        doubleCapacity();

// 尾部添加元素
public void addLast(E e) {
    // 插入的元素不能為空宰闰，否則拋出空指針異常
    if (e == null)
        throw new NullPointerException();
    // 尾部索引處的元素設置為 e
    elements[tail] = e;
    // 尾部索引后移一位茬贵，并且判斷是否需要擴容
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

從上面的源碼中我們可以看到幾個很有趣的點：

1. 首部添加元素時，先將 head 索引前移移袍，然后再添加元素解藻，說明，head 索引處是有元素的
2. 尾部添加元素時咐容，直接在 tail 索引處添加元素舆逃，然后再將 tail 索引后移蚂维，說明戳粒，tail 索引處是沒有元素的
3. 從中可以看出數(shù)組中肯定有一個索引處是空的，即 tail 索引處虫啥，所以可以先插入元素然后再進行擴容的判斷
4. 擴容的判斷條件是判斷首尾索引是否一致蔚约，即 head == tail

首部添加元素的時候，如果 head 是 0涂籽，那么在進行 elements[head = (head - 1) & (elements.length - 1)] = e; 操作的時候苹祟，head - 1 = -1，elements.length - 1 = 15评雌，將兩者進行“與”運算的時候树枫，因為“-1”的二進制其實是 “1111 1111... 1111”，即所有位上都是 1景东，所以與運算得出的結(jié)果自然也是 15砂轻。

下面畫圖來介紹下元素的插入過程：

插入元素

移除元素

Deque 是不可以按照索引來刪除元素的，只能刪除首尾的元素（pollFirst()斤吐、pollLast()）搔涝，或者刪除指定內(nèi)容的元素（removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)）

// 刪除首部元素
public E pollFirst() {
    // 首部索引
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    // 首部索引處元素置為 null
    elements[h] = null;     // Must null out slot
    // 調(diào)整首部索引
    head = (h + 1) & (elements.length - 1);
    return result;
}

// 刪除尾部元素
public E pollLast() {
    // 尾部索引前的一個索引和措，因為尾部索引指向的索引處是沒有元素的
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    // 置為 null
    elements[t] = null;
    tail = t;
    return result;
}

刪除元素的代碼其實也很簡單庄呈，有趣的是刪除了元素之后的數(shù)組，可能出現(xiàn)數(shù)組的前部和后部有數(shù)據(jù)派阱，也可能出現(xiàn)數(shù)組的中間部分有數(shù)據(jù)诬留，也就是說 head 不一定總等于 0，tail 也不一定總是比 head 大贫母。所以我們稱之為 環(huán)形數(shù)組文兑。

刪除元素

LinkedList

LinkedList 相對 ArrayDeque 而言，底層數(shù)數(shù)據(jù)結(jié)構(gòu)由數(shù)組變?yōu)榱随湵戆涠溃?LinkedList 自然而然是不用進行擴容操作的彩届。

LinkedList 是由一個個的 Node<V> 組成的，每個 node 都會記錄當前的數(shù)據(jù)誓酒、前一個 node 和 后一個 node贮聂，所以就形成了一個 鏈表，數(shù)據(jù)模型如下：

具體的方法就不贅述了寨辩，比較簡單吓懈。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable,  java.io.Serializable {
    
    // 鏈表長度
    transient int size = 0;

    // 第一個 元素
    transient Node<E> first;

    // 最后一個元素
    transient Node<E> last;
    
    // 每個節(jié)點的數(shù)據(jù)結(jié)構(gòu)
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
}

LinkedList 模型

ConcurrentLinkedDeque

上文提到的 ArrayDeque 和 LinkedList 都是 List 包下的工具類，而 ConcurrentLinkedDeque 就有意思了靡狞，它是 concurrent 并發(fā)包下面的類耻警，其實看名字我們應該也能略知其中的一二了，它是線程安全的無邊雙向隊列甸怕。

它內(nèi)部的變量等都是使用 volatile 來修飾的甘穿，所以它是線程安全的。因為 volatile 的作用就是阻止變量訪問前后的指令重排梢杭，從而保證指令的順序執(zhí)行温兼。

另外，其內(nèi)部使用了 自旋+CAS 的非阻塞算法來保證線程并發(fā)訪問時的數(shù)據(jù)一致性武契，例如在首部添加元素 addFirst(E e) 方法：

public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    // 檢查待插入的元素是否為空
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);

    // 錨點設計募判，作用是便于在多層 for 循環(huán)的內(nèi)部 for 循環(huán)中，可以直接 continue 到該錨點
    restartFromHead:
    for (;;)
        // 從head節(jié)點往前尋找first節(jié)點
        for (Node<E> h = head, p = h, q;;) {
            if ((q = p.prev) != null && (q = (p = q).prev) != null)
                // Check for head updates every other hop.
                // If p == q, we are sure to follow head instead.
                // 如果head被修改咒唆，返回head重新查找
                p = (h != (h = head)) ? h : q;
            else if (p.next == p) // PREV_TERMINATOR
                continue restartFromHead;
            else {
                // p is first node
                newNode.lazySetNext(p); // CAS piggyback
                if (p.casPrev(null, newNode)) {
                    // Successful CAS is the linearization point
                    // for e to become an element of this deque,
                    // and for newNode to become "live".
                    if (p != h) // hop two nodes at a time
                        casHead(h, newNode);  // Failure is OK.
                    return;
                }
                // Lost CAS race to another thread; re-read prev
            }
        }
}

執(zhí)行流程大致為：

1. 從 head 節(jié)點開始向前循環(huán)找到 first 節(jié)點 (p.prev==null&&p.next!=p)
2. 然后通過 lazySetNext 設置新節(jié)點的 next 節(jié)點為 first
3. CAS 修改 first 的 prev 為新節(jié)點届垫。

注意這里 CAS 指令成功后會判斷 first 節(jié)點是否已經(jīng)跳了兩個節(jié)點，只有在跳了兩個節(jié)點才會 CAS 更新 head全释，這也是為了節(jié)省 CAS 指令執(zhí)行開銷装处。

ConcurrentLinkedDeque 數(shù)據(jù)結(jié)構(gòu)，本文就簡單提了一點恨溜，詳細的分析會放到后面介紹 java.util.concurrent 包（簡稱 JUC 包）的時候再詳細闡述符衔，尤其是 ConcurrentLinkedDeque 中的節(jié)點刪除的操作，需要詳細分析下糟袁。

小結(jié)

Deque 雙邊隊列這種數(shù)據(jù)結(jié)構(gòu)判族，為兩端數(shù)據(jù)的操作提供了便捷性，并且也是官方建議的替換 Stack 數(shù)據(jù)結(jié)構(gòu)的方案项戴，另外形帮，其不僅有最常用的 ArrayDeque，也有線程安全的 ConcurrentLinkedDeque周叮，數(shù)據(jù)結(jié)構(gòu)也是比較豐富的辩撑。

image