摘要：接口截止目前為止，我們介紹的阻塞隊(duì)列都是實(shí)現(xiàn)了接口。該類在構(gòu)造時(shí)一般需要指定容量，如果不指定，則最大容量為。另外，由于內(nèi)部通過來保證線程安全，所以的整體實(shí)現(xiàn)時(shí)比較簡(jiǎn)單的。另外，雙端隊(duì)列相比普通隊(duì)列，主要是多了隊(duì)尾出隊(duì)元素隊(duì)首入隊(duì)元素的功能。

本文首發(fā)于一世流云專欄：https://segmentfault.com/blog...

LinkedBlockingDeque和ConcurrentLinkedDeque類似，都是一種雙端隊(duì)列的結(jié)構(gòu)，只不過LinkedBlockingDeque同時(shí)也是一種阻塞隊(duì)列，它是在JDK1.5時(shí)隨著J.U.C包引入的，實(shí)現(xiàn)了BlockingDueue接口，底層基于雙鏈表實(shí)現(xiàn)：

注意：LinkedBlockingDeque底層利用ReentrantLock實(shí)現(xiàn)同步，并不像ConcurrentLinkedDeque那樣采用無鎖算法。

另外，LinkedBlockingDeque是一種近似有界阻塞隊(duì)列，為什么說近似？因?yàn)長(zhǎng)inkedBlockingDeque既可以在初始構(gòu)造時(shí)就指定隊(duì)列的容量，也可以不指定，如果不指定，那么它的容量大小默認(rèn)為Integer.MAX_VALUE。

截止目前為止，我們介紹的阻塞隊(duì)列都是實(shí)現(xiàn)了BlockingQueue接口。和普通雙端隊(duì)列接口——Deque一樣，J.U.C中也有一種阻塞的雙端隊(duì)列接口——BlockingDeque。BlockingDeque是JDK1.6時(shí)，J.U.C包新增的一個(gè)接口：

BlockingDeque的類繼承關(guān)系圖：

我們知道，BlockingQueue中阻塞方法一共有4個(gè)：put(e)、take()；offer(e, time, unit)、poll(time, unit)，忽略限時(shí)等待的阻塞方法，一共就兩個(gè)：
隊(duì)尾入隊(duì)：put(e)
隊(duì)首出隊(duì)：take()

BlockingDeque相對(duì)于BlockingQueue，最大的特點(diǎn)就是增加了在隊(duì)首入隊(duì)/隊(duì)尾出隊(duì)的阻塞方法。下面是兩個(gè)接口的比較：

LinkedBlockingDeque一共三種構(gòu)造器，不指定容量時(shí)，默認(rèn)為Integer.MAX_VALUE：

/**
 * 默認(rèn)構(gòu)造器.
 */
public LinkedBlockingDeque() {
    this(Integer.MAX_VALUE);
}

/**
 * 指定容量的構(gòu)造器.
 */
public LinkedBlockingDeque(int capacity) {
    if (capacity <= 0) throw new IllegalArgumentException();
    this.capacity = capacity;
}

/**
 * 從已有集合構(gòu)造隊(duì)列.
 */
public LinkedBlockingDeque(Collection c) {
    this(Integer.MAX_VALUE);
    final ReentrantLock lock = this.lock;
    lock.lock(); // Never contended, but necessary for visibility
    try {
        for (E e : c) {
            if (e == null)
                throw new NullPointerException();
            if (!linkLast(new Node(e)))
                throw new IllegalStateException("Deque full");
        }
    } finally {
        lock.unlock();
    }
}

LinkedBlockingDeque內(nèi)部是雙鏈表的結(jié)構(gòu)，結(jié)點(diǎn)Node的定義如下：

/**
 * 雙鏈表結(jié)點(diǎn)定義
 */
static final class Node {
    /**
     * 結(jié)點(diǎn)值, null表示該結(jié)點(diǎn)已被移除.
     */
    E item;

    /**
     * 前驅(qū)結(jié)點(diǎn)指針.
     */
    Node prev;

    /**
     * 后驅(qū)結(jié)點(diǎn)指針.
     */
    Node next;

    Node(E x) {
        item = x;
    }
}

字段first指向隊(duì)首結(jié)點(diǎn)，字段last指向隊(duì)尾結(jié)點(diǎn)。另外LinkedBlockingDeque利用ReentrantLock來保證線程安全，所有對(duì)隊(duì)列的修改操作都需要先獲取這把全局鎖：

public class LinkedBlockingDeque extends AbstractQueue
    implements BlockingDeque, java.io.Serializable {

    /**
     * 隊(duì)首結(jié)點(diǎn)指針.
     */
    transient Node first;

    /**
     * 隊(duì)尾結(jié)點(diǎn)指針.
     */
    transient Node last;

    /**
     * 隊(duì)列元素個(gè)數(shù).
     */
    private transient int count;

    /**
     * 隊(duì)列容量.
     */
    private final int capacity;

    /**
     * 全局鎖
     */
    final ReentrantLock lock = new ReentrantLock();

    /**
     * 出隊(duì)線程條件隊(duì)列（隊(duì)列為空時(shí)，出隊(duì)線程在此等待）
     */
    private final Condition notEmpty = lock.newCondition();

    /**
     * 入隊(duì)線程條件隊(duì)列（隊(duì)列為滿時(shí)，入隊(duì)線程在此等待）
     */
    private final Condition notFull = lock.newCondition();

    //...
}

先來看下，LinkedBlockingDeque是如何實(shí)現(xiàn)正常的從隊(duì)尾入隊(duì)的：

/**
 * 在隊(duì)尾入隊(duì)元素e.
 * 如果隊(duì)列已滿, 則阻塞線程.
 */
public void put(E e) throws InterruptedException {
    putLast(e);
}

public void putLast(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();    // 隊(duì)列不能包含null元素
    Node node = new Node(e);                      // 創(chuàng)建入隊(duì)結(jié)點(diǎn)
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        while (!linkLast(node))                         // 隊(duì)列已滿, 則阻塞線程
            notFull.await();
    } finally {
        lock.unlock();
    }
}

put方法內(nèi)部調(diào)用了putLast方法，這是Deque接口獨(dú)有的方法。上述入隊(duì)操作的關(guān)鍵是linkLast方法：

/**
 * 將結(jié)點(diǎn)node鏈接到隊(duì)尾, 如果失敗, 則返回false.
 */
private boolean linkLast(Node node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity)  // 隊(duì)列已滿, 直接返回
        return false;

    // 以下是雙鏈表的"尾插"操作
    Node l = last;
    node.prev = l;
    last = node;
    if (first == null)
        first = node;
    else
        l.next = node;

    ++count;            // 隊(duì)列元素加1
    notEmpty.signal();  // 喚醒一個(gè)等待的出隊(duì)線程
    return true;
}

linkLast方法在隊(duì)尾插入一個(gè)結(jié)點(diǎn)，插入失敗（隊(duì)列已滿的情況）則返回false。插入成功，則喚醒一個(gè)正在等待的出隊(duì)線程：

初始：

隊(duì)尾插入結(jié)點(diǎn)node：

隊(duì)首入隊(duì)就是雙鏈表的“頭插法”插入一個(gè)結(jié)點(diǎn)，如果隊(duì)列已滿，則阻塞調(diào)用線程：

/**
 * 在隊(duì)首入隊(duì)元素e.
 * 如果隊(duì)列已滿, 則阻塞線程.
 */
public void putFirst(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    Node node = new Node(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        while (!linkFirst(node))        // 隊(duì)列已滿, 則阻塞線程
            notFull.await();
    } finally {
        lock.unlock();
    }
}

/**
 * 在隊(duì)首插入一個(gè)結(jié)點(diǎn), 插入失敗則返回null.
 */
private boolean linkFirst(Node node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity)      // 隊(duì)列已滿
        return false;

    // 以下是雙鏈表的“頭插”操作
    Node f = first;
    node.next = f;
    first = node;
    if (last == null)
        last = node;
    else
        f.prev = node;

    ++count;                    // 隊(duì)列元素?cái)?shù)量加1
    notEmpty.signal();          // 喚醒一個(gè)等待的出隊(duì)線程
    return true;
}

初始：

隊(duì)首插入結(jié)點(diǎn)node：

隊(duì)首出隊(duì)的邏輯很簡(jiǎn)單，如果隊(duì)列為空，則阻塞調(diào)用線程：

/**
 * 從隊(duì)首出隊(duì)一個(gè)元素, 如果隊(duì)列為空, 則阻塞線程.
 */
public E take() throws InterruptedException {
    return takeFirst();
}

public E takeFirst() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E x;
        while ((x = unlinkFirst()) == null)     // 隊(duì)列為空, 則阻塞線程
            notEmpty.await();
        return x;
    } finally {
        lock.unlock();
    }
}

實(shí)際的出隊(duì)由unlinkFirst方法執(zhí)行：

/**
 * 從隊(duì)首刪除一個(gè)元素, 失敗則返回null.
 */
private E unlinkFirst() {
    // assert lock.isHeldByCurrentThread();
    Node f = first;
    if (f == null)          // 隊(duì)列為空
        return null;

    // 以下是雙鏈表的頭部刪除過程
    Node n = f.next;
    E item = f.item;
    f.item = null;
    f.next = f;             // help GC
    first = n;
    if (n == null)
        last = null;
    else
        n.prev = null;

    --count;                // 隊(duì)列元素個(gè)數(shù)減1
    notFull.signal();       // 喚醒一個(gè)等待的入隊(duì)線程
    return item;
}

初始：

刪除隊(duì)首結(jié)點(diǎn)：

隊(duì)尾出隊(duì)的邏輯很簡(jiǎn)單，如果隊(duì)列為空，則阻塞調(diào)用線程：

/**
 * 從隊(duì)尾出隊(duì)一個(gè)元素, 如果隊(duì)列為空, 則阻塞線程.
 */
public E takeLast() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E x;
        while ((x = unlinkLast()) == null)  // 隊(duì)列為空, 阻塞線程
            notEmpty.await();
        return x;
    } finally {
        lock.unlock();
    }
}

實(shí)際的出隊(duì)由unlinkLast方法執(zhí)行：

/**
 * 刪除隊(duì)尾元素, 如果失敗, 則返回null.
 */
private E unlinkLast() {
    // assert lock.isHeldByCurrentThread();
    Node l = last;
    if (l == null)          // 隊(duì)列為空
        return null;

    // 以下為雙鏈表的尾部刪除過程
    Node p = l.prev;
    E item = l.item;
    l.item = null;
    l.prev = l;             // help GC
    last = p;
    if (p == null)
        first = null;
    else
        p.next = null;

    --count;                // 隊(duì)列元素個(gè)數(shù)減1
    notFull.signal();       // 喚醒一個(gè)等待的入隊(duì)線程
    return item;
}

初始：

刪除隊(duì)尾結(jié)點(diǎn)：

LinkedBlockingDeque作為一種阻塞雙端隊(duì)列，提供了隊(duì)尾刪除元素和隊(duì)首插入元素的阻塞方法。該類在構(gòu)造時(shí)一般需要指定容量，如果不指定，則最大容量為Integer.MAX_VALUE。另外，由于內(nèi)部通過ReentrantLock來保證線程安全，所以LinkedBlockingDeque的整體實(shí)現(xiàn)時(shí)比較簡(jiǎn)單的。

另外，雙端隊(duì)列相比普通隊(duì)列，主要是多了【隊(duì)尾出隊(duì)元素】/【隊(duì)首入隊(duì)元素】的功能。
阻塞隊(duì)列我們知道一般用于“生產(chǎn)者-消費(fèi)者”模式，而雙端阻塞隊(duì)列在“生產(chǎn)者-消費(fèi)者”就可以利用“雙端”的特性，從隊(duì)尾出隊(duì)元素。

考慮下面這樣一種場(chǎng)景：有多個(gè)消費(fèi)者，每個(gè)消費(fèi)者有自己的一個(gè)消息隊(duì)列，生產(chǎn)者不斷的生產(chǎn)數(shù)據(jù)扔到隊(duì)列中，消費(fèi)者消費(fèi)數(shù)據(jù)有快又慢。為了提升效率，速度快的消費(fèi)者可以從其它消費(fèi)者隊(duì)列的隊(duì)尾出隊(duì)元素放到自己的消息隊(duì)列中，由于是從其它隊(duì)列的隊(duì)尾出隊(duì)，這樣可以減少并發(fā)沖突（其它消費(fèi)者從隊(duì)首出隊(duì)元素），又能提升整個(gè)系統(tǒng)的吞吐量。這其實(shí)是一種“工作竊取算法”的思路。