LinkedBlockingDeque 與 LinkedBlockingQueue 對(duì)比
LinkedBlockingDeque在結(jié)構(gòu)上有別于之前講解過的阻塞隊(duì)列，它不是Queue而是Deque隙赁，中文翻譯成雙端隊(duì)列垦藏，雙端隊(duì)列指可以從任意一端入隊(duì)或者出隊(duì)元素的隊(duì)列，實(shí)現(xiàn)了在隊(duì)列頭和隊(duì)列尾的高效插入和移除
LinkedBlockingDeque是鏈表實(shí)現(xiàn)的線程安全的無界的同時(shí)支持FIFO伞访、LIFO的雙端阻塞隊(duì)列掂骏，可以回顧下之前的LinkedBlockingQueue阻塞隊(duì)列特點(diǎn)，本質(zhì)上是類似的咐扭，但是又有些不同：
內(nèi)部是通過Node節(jié)點(diǎn)組成的鏈表來實(shí)現(xiàn)的芭挽，當(dāng)然為了支持雙端操作滑废，結(jié)點(diǎn)結(jié)構(gòu)不同
LinkedBlockingQueue通過兩個(gè)ReentrantLock鎖保護(hù)競爭資源蝗肪，實(shí)現(xiàn)了多線程對(duì)競爭資源的互斥訪問，入隊(duì)和出隊(duì)互不影響蠕趁，可同時(shí)操作薛闪，然而LinkedBlockingDeque只設(shè)置了一個(gè)全局ReentrantLock鎖，兩個(gè)條件對(duì)象實(shí)現(xiàn)互斥訪問俺陋，性能上要比LinkedBlockingQueue差一些 (為什么有兩把鎖 和一把鎖的區(qū)別豁延？）無界，默認(rèn)鏈表長度為Integer.MAX_VALUE腊状，本質(zhì)上還是有界
阻塞隊(duì)列诱咏，是指多線程訪問競爭資源時(shí)，當(dāng)競爭資源已被某線程獲取時(shí)缴挖，其它要獲取該資源的線程需要阻塞等待
Queue和Deque的關(guān)系有點(diǎn)類似于單鏈表和雙向鏈表袋狞，LinkedBlockingQueue和LinkedBlockingDeque的內(nèi)部結(jié)點(diǎn)實(shí)現(xiàn)就是單鏈表和雙向鏈表的區(qū)別，具體可參考源碼映屋。
在第二點(diǎn)中可能有些人有些疑問苟鸯，兩個(gè)互斥鎖和一個(gè)互斥鎖的區(qū)別在哪里？我們可以考慮以下場景：
A線程先進(jìn)行入隊(duì)操作棚点，B線程隨后進(jìn)行出隊(duì)操作早处，如果是LinkedBlockingQueue，A線程入隊(duì)過程還未結(jié)束（已獲得鎖還未釋放）瘫析，B線程出隊(duì)操作不會(huì)被阻塞等待（鎖不同）砌梆，如果是LinkedBlockingDeque則B線程會(huì)被阻塞等待（同一把鎖）A線程完成操作才繼續(xù)執(zhí)行
LinkedBlockingQueue一般的操作是獲取一把鎖就可以默责，但有些操作例如remove操作，則需要同時(shí)獲取兩把鎖咸包，之前的LinkedBlockingQueue講解曾經(jīng)說明過
LinkedBlockingQueue 由于是單鏈表結(jié)構(gòu)傻丝，只能一端操作，讀只能在頭诉儒，寫只能在尾葡缰，因此兩把鎖效率更高。LinkedBlockingDeque 由于是雙鏈表結(jié)構(gòu)忱反，兩端頭尾都能讀寫泛释，因此只能用一把鎖保證原子性。 當(dāng)然效率也就更低
ArrayBlockingQueue與LinkedBlockingQueue對(duì)比
ArrayBlockingQueue
- 一個(gè)對(duì)象數(shù)組+一把鎖+兩個(gè)條件
- 入隊(duì)與出隊(duì)都用同一把鎖
- 在只有入隊(duì)高并發(fā)或出隊(duì)高并發(fā)的情況下温算，因?yàn)椴僮鲾?shù)組怜校，且不需要擴(kuò)容，性能很高
- 采用了數(shù)組注竿，必須指定大小茄茁，即容量有限。從空間利用角度巩割，數(shù)組結(jié)構(gòu)的ArrayBlockingQueue要比LinkedBlockingQueue緊湊裙顽，因?yàn)槠洳恍枰獎(jiǎng)?chuàng)建所謂節(jié)點(diǎn)，但是其初始分配階段就需要一段連續(xù)的空間宣谈，所以初始內(nèi)存需求更大愈犹。
LinkedBlockingQueue
- 一個(gè)單向鏈表+兩把鎖+兩個(gè)條件
- 兩把鎖，一把用于入隊(duì)闻丑，一把用于出隊(duì)漩怎，有效的避免了入隊(duì)與出隊(duì)時(shí)使用一把鎖帶來的競爭。
- 在入隊(duì)與出隊(duì)都高并發(fā)的情況下嗦嗡，性能比ArrayBlockingQueue高很多
- 采用了鏈表勋锤，最大容量為整數(shù)最大值，可看做容量無限侥祭。ArrayBlockingQueue是有明確的容量限制的叁执，而LinkedBlockingQueue則取決于我們是否在創(chuàng)建時(shí)指定，
問題卑硫，為什么ArrayBlockingQueue 不能用兩把鎖
因?yàn)槿〕龊笸搅担珹rrayBlockingQueue 的元素需要向前移動(dòng)。
概述
LinkedBlockingQueue內(nèi)部由單鏈表實(shí)現(xiàn)欢伏，只能從head取元素入挣，從tail添加元素。添加元素和獲取元素都有獨(dú)立的鎖硝拧，也就是說LinkedBlockingQueue是讀寫分離的径筏，讀寫操作可以并行執(zhí)行葛假。LinkedBlockingQueue采用可重入鎖(ReentrantLock)來保證在并發(fā)情況下的線程安全。
構(gòu)造器
LinkedBlockingQueue一共有三個(gè)構(gòu)造器滋恬，分別是無參構(gòu)造器聊训、可以指定容量的構(gòu)造器、可以穿入一個(gè)容器的構(gòu)造器恢氯。如果在創(chuàng)建實(shí)例的時(shí)候調(diào)用的是無參構(gòu)造器带斑，LinkedBlockingQueue的默認(rèn)容量是Integer.MAX_VALUE，這樣做很可能會(huì)導(dǎo)致隊(duì)列還沒有滿勋拟，但是內(nèi)存卻已經(jīng)滿了的情況（內(nèi)存溢出）勋磕。
public LinkedBlockingQueue()； //設(shè)置容量為Integer.MAX
public LinkedBlockingQueue(int capacity)敢靡； //設(shè)置指定容量
public LinkedBlockingQueue(Collection<? extends E> c)挂滓； //穿入一個(gè)容器，如果調(diào)用該構(gòu)造器啸胧，容量默認(rèn)也是Integer.MAX_VALUE
LinkedBlockingQueue常用操作
取數(shù)據(jù)
take()：首選赶站。當(dāng)隊(duì)列為空時(shí)阻塞
poll()：彈出隊(duì)頂元素，隊(duì)列為空時(shí)纺念，返回空
peek()：和poll烈性贝椿，返回隊(duì)隊(duì)頂元素，但頂元素不彈出柠辞。隊(duì)列為空時(shí)返回null
remove(Object o)：移除某個(gè)元素团秽，隊(duì)列為空時(shí)拋出異常主胧。成功移除返回true
添加數(shù)據(jù)
put()：首選叭首。隊(duì)滿是阻塞
offer()：隊(duì)滿時(shí)返回false
判斷隊(duì)列是否為空
size()方法會(huì)遍歷整個(gè)隊(duì)列，時(shí)間復(fù)雜度為O(n),所以最好選用isEmtpy
put元素原理
基本過程：
1.判斷元素是否為null踪栋，為null拋出異常
2.加鎖(可中斷鎖)
3.判斷隊(duì)列長度是否到達(dá)容量焙格，如果到達(dá)一直等待
4.如果沒有隊(duì)滿，enqueue()在隊(duì)尾加入元素
5.隊(duì)列長度加1夷都，此時(shí)如果隊(duì)列還沒有滿眷唉，調(diào)用signal喚醒其他堵塞隊(duì)列
/**
* 在隊(duì)尾插一個(gè)元素
* 如果隊(duì)列滿了，一直阻塞囤官，直到隊(duì)列不滿了或者線程被中斷
*/
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
int c = -1;
final ReentrantLock putLock = this.putLock;//入隊(duì)鎖
final AtomicInteger count = this.count;//當(dāng)前隊(duì)列中的元素個(gè)數(shù)
putLock.lockInterruptibly();//加鎖
try {
while (count.get() == capacity) {//如果隊(duì)列滿了
/*
* 加入notFull等待隊(duì)列冬阳，直到隊(duì)列元素不滿了，
* 被其他線程使用notFull.signal()喚醒
*/
notFull.await();
}
enqueue(e);//入隊(duì)
c = count.getAndIncrement();//入隊(duì)數(shù)量+1
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}
take元素原理
基本過程：
1.加鎖(依舊是ReentrantLock)党饮，注意這里的鎖和寫入是不同的兩把鎖
2.判斷隊(duì)列是否為空肝陪，如果為空就一直等待
3.通過dequeue方法取得數(shù)據(jù)
3.取走元素后隊(duì)列是否為空，如果不為空喚醒其他等待中的隊(duì)列
/**
* 出隊(duì)：
* 如果隊(duì)列空了刑顺，一直阻塞氯窍，直到隊(duì)列不為空或者線程被中斷
*/
public E take() throws InterruptedException {
E x;
int c = -1;
final AtomicInteger count = this.count;//獲取隊(duì)列中的元素總量
final ReentrantLock takeLock = this.takeLock;
takeLock.lockInterruptibly();//獲取出隊(duì)鎖
try {
while (count.get() == 0) {//如果沒有元素饲常，一直阻塞
/*
* 加入等待隊(duì)列， 一直等待條件notEmpty（即被其他線程喚醒）
* （喚醒其實(shí)就是狼讨，有線程將一個(gè)元素入隊(duì)了贝淤，然后調(diào)用notEmpty.signal()喚醒其他等待這個(gè)條件的線程，同時(shí)隊(duì)列也不空了）
*/
notEmpty.await();
}
x = dequeue();//出隊(duì)
c = count.getAndDecrement();//元素?cái)?shù)量-1
if (c > 1)
notEmpty.signal();
} finally {
takeLock.unlock();
}
if (c == capacity)
signalNotFull();
return x;
}
/**
* 從隊(duì)列頭部移除一個(gè)節(jié)點(diǎn)
*/
private E dequeue() {
Node<E> h = head;//獲取頭節(jié)點(diǎn)：x==null
Node<E> first = h.next;//將頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)賦值給first
h.next = h; // 將當(dāng)前將要出隊(duì)的節(jié)點(diǎn)置null（為了使其做head節(jié)點(diǎn)做準(zhǔn)備）
head = first;//將當(dāng)前將要出隊(duì)的節(jié)點(diǎn)作為了頭節(jié)點(diǎn)
E x = first.item;//獲取出隊(duì)節(jié)點(diǎn)的值
first.item = null;//將出隊(duì)節(jié)點(diǎn)的值置空
return x;
}
private void signalNotFull() {
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
notFull.signal();
} finally {
putLock.unlock();
}
}
public boolean offer(E e)
原理：在隊(duì)尾插入一個(gè)元素政供， 如果隊(duì)列沒滿播聪，立即返回true； 如果隊(duì)列滿了布隔，立即返回false犬耻。
/**
* 在隊(duì)尾插入一個(gè)元素， 容量沒滿执泰，可以立即插入枕磁，返回true； 隊(duì)列滿了术吝，直接返回false
* 注：如果使用了限制了容量的隊(duì)列计济，這個(gè)方法比add()好，因?yàn)閍dd()插入失敗就會(huì)拋出異常
*/
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
final AtomicInteger count = this.count;// 獲取隊(duì)列中的元素個(gè)數(shù)
if (count.get() == capacity)// 隊(duì)列滿了
return false;
int c = -1;
final ReentrantLock putLock = this.putLock;
putLock.lock();// 獲取入隊(duì)鎖
try {
if (count.get() < capacity) {// 容量沒滿
enqueue(e);// 入隊(duì)
c = count.getAndIncrement();// 容量+1排苍，返回舊值（注意）
if (c + 1 < capacity)// 如果添加元素后的容量沦寂，還小于指定容量（說明在插入當(dāng)前元素后，至少還可以再插一個(gè)元素）
notFull.signal();// 喚醒等待notFull條件的其中一個(gè)線程
}
} finally {
putLock.unlock();// 釋放入隊(duì)鎖
}
if (c == 0)// 如果c==0淘衙，這是什么情況传藏？一開始如果是個(gè)空隊(duì)列，就會(huì)是這樣的值彤守，要注意的是毯侦，上邊的c返回的是舊值
signalNotEmpty();
return c >= 0;
}
/**
* 創(chuàng)建一個(gè)節(jié)點(diǎn)，并加入鏈表尾部
* @param x
*/
private void enqueue(E x) {
/*
* 封裝新節(jié)點(diǎn)具垫，并賦給當(dāng)前的最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)侈离，然后在將這個(gè)節(jié)點(diǎn)設(shè)為最后一個(gè)節(jié)點(diǎn)
*/
last = last.next = new Node<E>(x);
}
private void signalNotEmpty() {
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();//獲取出隊(duì)鎖
try {
notEmpty.signal();//喚醒等待notEmpty條件的線程中的一個(gè)
} finally {
takeLock.unlock();//釋放出隊(duì)鎖
}
}
public E poll()
原理：如果沒有元素，直接返回null筝蚕；如果有元素卦碾，出隊(duì)
/**
* 出隊(duì)：
* 1、如果沒有元素起宽，直接返回null
* 2洲胖、如果有元素，出隊(duì)
*/
public E poll() {
final AtomicInteger count = this.count;// 獲取元素?cái)?shù)量
if (count.get() == 0)// 沒有元素
return null;
E x = null;
int c = -1;
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();// 獲取出隊(duì)鎖
try {
if (count.get() > 0) {// 有元素
x = dequeue();// 出隊(duì)
// 元素個(gè)數(shù)-1（注意：該方法是一個(gè)無限循環(huán)坯沪，直到減1成功為止绿映，且返回舊值）
c = count.getAndDecrement();
if (c > 1)// 還有元素（如果舊值c==1的話，那么通過上邊的操作之后屏箍，隊(duì)列就空了）
notEmpty.signal();// 喚醒等待在notEmpty隊(duì)列中的其中一條線程
}
} finally {
takeLock.unlock();// 釋放出隊(duì)鎖
}
if (c == capacity)// c == capacity是怎么發(fā)生的绘梦？如果隊(duì)列是一個(gè)滿隊(duì)列橘忱，注意：上邊的c返回的是舊值
signalNotFull();
return x;
}
五、總結(jié)
1卸奉、具體入隊(duì)與出隊(duì)的原理圖：
圖中每一個(gè)節(jié)點(diǎn)前半部分表示封裝的數(shù)據(jù)x钝诚，后邊的表示指向的下一個(gè)引用。
1.1榄棵、初始化
初始化之后凝颇，初始化一個(gè)數(shù)據(jù)為null，且head和last節(jié)點(diǎn)都是這個(gè)節(jié)點(diǎn)疹鳄。
1.2拧略、入隊(duì)兩個(gè)元素過后
1.3、出隊(duì)一個(gè)元素后
表面上看瘪弓，只是將頭節(jié)點(diǎn)的next指針指向了要?jiǎng)h除的x1.next垫蛆，事實(shí)上這樣我覺的就完全可以，但是jdk實(shí)際上是將原來的head節(jié)點(diǎn)刪除了腺怯，而上邊看到的這個(gè)head節(jié)點(diǎn)袱饭，正是剛剛出隊(duì)的x1節(jié)點(diǎn)，只是其值被置空了呛占。
2虑乖、三種入隊(duì)對(duì)比：
- offer(E e)：如果隊(duì)列沒滿，立即返回true晾虑； 如果隊(duì)列滿了疹味，立即返回false-->不阻塞
- put(E e)：如果隊(duì)列滿了，一直阻塞帜篇，直到隊(duì)列不滿了或者線程被中斷-->阻塞
- offer(E e, long timeout, TimeUnit unit)：在隊(duì)尾插入一個(gè)元素,糙捺，如果隊(duì)列已滿，則進(jìn)入等待坠狡，直到出現(xiàn)以下三種情況：-->阻塞
- 被喚醒
- 等待時(shí)間超時(shí)
- 當(dāng)前線程被中斷
3继找、三種出隊(duì)對(duì)比：
- poll()：如果沒有元素，直接返回null逃沿；如果有元素，出隊(duì)
- take()：如果隊(duì)列空了幻锁，一直阻塞凯亮，直到隊(duì)列不為空或者線程被中斷-->阻塞
- poll(long timeout, TimeUnit unit)：如果隊(duì)列不空，出隊(duì)哄尔；如果隊(duì)列已空且已經(jīng)超時(shí)假消，返回null；如果隊(duì)列已空且時(shí)間未超時(shí)岭接，則進(jìn)入等待富拗，直到出現(xiàn)以下三種情況：
- 被喚醒
- 等待時(shí)間超時(shí)
- 當(dāng)前線程被中斷
