一敞恋、簡(jiǎn)述
LinkedBlockingDeque 是一個(gè)由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列其兴，即可以從隊(duì)列的兩端插入和移除元素猪瞬。雙向隊(duì)列因?yàn)槎嗔艘粋€(gè)操作隊(duì)列的入口链韭，在多線程同時(shí)入隊(duì)時(shí)，也就減少了一半的競(jìng)爭(zhēng)庭惜。相比于其他阻塞隊(duì)列距芬，LinkedBlockingDeque 多了 addFirst涝开、addLast、peekFirst框仔、peekLast 等方法舀武。以first結(jié)尾的方法，表示插入离斩、獲取或移除雙端隊(duì)列的第一個(gè)元素银舱。以 last 結(jié)尾的方法，表示插入跛梗、獲取或移除雙端隊(duì)列的最后一個(gè)元素纵朋。LinkedBlockingDeque 是可選容量的，在初始化時(shí)可以設(shè)置容量防止其過(guò)度膨脹茄袖。如果不設(shè)置，默認(rèn)容量大小為 Integer.MAX_VALUE嘁锯。LinkedBlockingDeque 類有三個(gè)構(gòu)造方法：
public LinkedBlockingDeque()
public LinkedBlockingDeque(int capacity)
public LinkedBlockingDeque(Collection<? extends E> c)
二宪祥、LinkedBlockingDeque源碼詳解
LinkedBlockingDeque 類定義為：
public class LinkedBlockingDeque<E>
extends AbstractQueue<E>
implements BlockingDeque<E>, java.io.Serializable
該類繼承自 AbstractQueue 抽象類，又實(shí)現(xiàn)了 BlockingDeque 接口家乘。BlockingDeque 接口定義如下：
public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E>
BlockingDeque 繼承自 BlockingQueue 和 Deque 接口蝗羊，BlockingDeque 接口定義了在雙端隊(duì)列中常用的方法。
LinkedBlockingDeque 類中的數(shù)據(jù)都被封裝成了 Node 對(duì)象：
static final class Node<E> {
E item;
Node<E> prev;
Node<E> next;
Node(E x) {
item = x;
}
}
LinkedBlockingDeque 類中的重要字段如下：
// 隊(duì)列雙向鏈表首節(jié)點(diǎn)
transient Node<E> first;
// 隊(duì)列雙向鏈表尾節(jié)點(diǎn)
transient Node<E> last;
// 雙向鏈表元素個(gè)數(shù)
private transient int count;
// 雙向鏈表最大容量
private final int capacity;
// 全局獨(dú)占鎖
final ReentrantLock lock = new ReentrantLock();
// 非空Condition對(duì)象
private final Condition notEmpty = lock.newCondition();
// 非滿Condition對(duì)象
private final Condition notFull = lock.newCondition();
LinkedBlockingDeque 類的底層實(shí)現(xiàn)和 LinkedBlockingQueue 類很相似仁锯，都有一個(gè)全局獨(dú)占鎖耀找，和兩個(gè) Condition 對(duì)象，用來(lái)阻塞和喚醒線程。
LinkedBlockingDeque 類對(duì)元素的操作方法比較多野芒。針對(duì)元素的入隊(duì)蓄愁、出隊(duì)操作以 putFirst、putLast狞悲、pollFirst撮抓、pollLast 方法來(lái)進(jìn)行分析。
三摇锋、入隊(duì)
1??putFirst(E e) 是將指定的元素插入雙端隊(duì)列的開頭丹拯，源碼如下：
public void putFirst(E e) throws InterruptedException {
// 若插入元素為null，則直接拋出NullPointerException異常
if (e == null) throw new NullPointerException();
// 將插入節(jié)點(diǎn)包裝為Node節(jié)點(diǎn)
Node<E> node = new Node<E>(e);
// 獲取全局獨(dú)占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
while (!linkFirst(node))
notFull.await();
} finally {
// 釋放全局獨(dú)占鎖
lock.unlock();
}
}
2??入隊(duì)操作是通過(guò) linkFirst(E e) 來(lái)完成的荸恕，如下所示：
private boolean linkFirst(Node<E> node) {
// assert lock.isHeldByCurrentThread();
// 元素個(gè)數(shù)超出容量乖酬。直接返回false
if (count >= capacity)
return false;
// 獲取雙向鏈表的首節(jié)點(diǎn)
Node<E> f = first;
// 將node設(shè)置為首節(jié)點(diǎn)
node.next = f;
first = node;
// 若last為null，設(shè)置尾節(jié)點(diǎn)為node節(jié)點(diǎn)
if (last == null)
last = node;
else
// 更新原首節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
f.prev = node;
++count;
// 喚醒阻塞在notEmpty上的線程
notEmpty.signal();
return true;
}
若入隊(duì)成功融求，則 linkFirst(E e) 返回 true咬像，否則返回 false。若該方法返回 false双肤，則當(dāng)前線程會(huì)阻塞在 notFull 條件上施掏。
3??putLast(E e) 是將指定的元素插入到雙端隊(duì)列的末尾，源碼如下：
public void putLast(E e) throws InterruptedException {
// 若插入元素為null茅糜，則直接拋出NullPointerException異常
if (e == null) throw new NullPointerException();
// 將插入節(jié)點(diǎn)包裝為Node節(jié)點(diǎn)
Node<E> node = new Node<E>(e);
// 獲取全局獨(dú)占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
while (!linkLast(node))
notFull.await();
} finally {
// 釋放全局獨(dú)占鎖
lock.unlock();
}
}
4??該方法和 putFirst(E e) 幾乎一樣七芭，不同點(diǎn)在于，putLast(E e) 通過(guò)調(diào)用 linkLast(E e) 來(lái)插入節(jié)點(diǎn)：
private boolean linkLast(Node<E> node) {
// assert lock.isHeldByCurrentThread();
// 元素個(gè)數(shù)超出容量蔑赘。直接返回false
if (count >= capacity)
return false;
// 獲取雙向鏈表的尾節(jié)點(diǎn)
Node<E> l = last;
// 將node設(shè)置為尾節(jié)點(diǎn)
node.prev = l;
last = node;
// 若first為null狸驳，設(shè)置首節(jié)點(diǎn)為node節(jié)點(diǎn)
if (first == null)
first = node;
else
// 更新原尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)
l.next = node;
++count;
// 喚醒阻塞在notEmpty上的線程
notEmpty.signal();
return true;
}
若入隊(duì)成功，則 linkLast(E e) 返回 true缩赛，否則返回 false耙箍。若該方法返回 false，則當(dāng)前線程會(huì)阻塞在 notFull 條件上酥馍。
四辩昆、出隊(duì)
1??pollFirst() 是獲取并移除此雙端隊(duì)列的首節(jié)點(diǎn)，若不存在旨袒，則返回 null汁针，源碼如下：
public E pollFirst() {
// 獲取全局獨(dú)占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
return unlinkFirst();
} finally {
// 釋放全局獨(dú)占鎖
lock.unlock();
}
}
2??移除首節(jié)點(diǎn)的操作是通過(guò) unlinkFirst() 來(lái)完成的：
private E unlinkFirst() {
// assert lock.isHeldByCurrentThread();
// 獲取首節(jié)點(diǎn)
Node<E> f = first;
// 首節(jié)點(diǎn)為null，則返回null
if (f == null)
return null;
// 獲取首節(jié)點(diǎn)的后繼節(jié)點(diǎn)
Node<E> n = f.next;
// 移除first砚尽，將首節(jié)點(diǎn)更新為n
E item = f.item;
f.item = null;
f.next = f; // help GC
first = n;
// 移除首節(jié)點(diǎn)后施无，為空隊(duì)列
if (n == null)
last = null;
else
// 將新的首節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)設(shè)置為null
n.prev = null;
--count;
// 喚醒阻塞在notFull上的線程
notFull.signal();
return item;
}
3??pollLast() 是獲取并移除此雙端隊(duì)列的尾節(jié)點(diǎn)，若不存在必孤，則返回 null猾骡，源碼如下：
public E pollLast() {
// 獲取全局獨(dú)占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
return unlinkLast();
} finally {
// 釋放全局獨(dú)占鎖
lock.unlock();
}
}
4??移除尾節(jié)點(diǎn)的操作是通過(guò) unlinkLast() 來(lái)完成的：
private E unlinkLast() {
// assert lock.isHeldByCurrentThread();
// 獲取尾節(jié)點(diǎn)
Node<E> l = last;
// 尾節(jié)點(diǎn)為null，則返回null
if (l == null)
return null;
// 獲取尾節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
Node<E> p = l.prev;
// 移除尾節(jié)點(diǎn)，將尾節(jié)點(diǎn)更新為p
E item = l.item;
l.item = null;
l.prev = l; // help GC
last = p;
// 移除尾節(jié)點(diǎn)后兴想，為空隊(duì)列
if (p == null)
first = null;
else
// 將新的尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)設(shè)置為null
p.next = null;
--count;
// 喚醒阻塞在notFull上的線程
notFull.signal();
return item;
}
其實(shí) LinkedBlockingDeque 類的入隊(duì)幢哨、出隊(duì)操作都是通過(guò) linkFirst、linkLast襟企、unlinkFirst嘱么、unlinkLast 這幾個(gè)方法來(lái)實(shí)現(xiàn)的，源碼讀起來(lái)也比較簡(jiǎn)單顽悼。
