一口氣說出 18種隊(duì)列（Queue），面試穩(wěn)了！

一、Queue自我介紹

1.1 Queue自我介紹

hi，大家好，我的英文名叫Queue，中文名叫隊(duì)列，無論現(xiàn)實(shí)生活中還是計算機(jī)的世界中，我都是一個很重要的角色哦~

我是一種數(shù)據(jù)結(jié)構(gòu)，大家可以把我想象成一個數(shù)組，元素從我的一頭進(jìn)入、從另外一頭出去，稱為FIFO原則（先進(jìn)先出原則）。

我還有兩個親兄弟：List（列表）、Set（集），他們都是Collection的兒子，我還有一個遠(yuǎn)房親戚：Map（映射）。他們都是java.util包這個大家庭的成員哦~

1.2 現(xiàn)實(shí)生活中的場景

• 海底撈排號等位（先排號的優(yōu)先進(jìn)餐廳）
• 郵政員寄送信件（信箱是隊(duì)列）

1.3 計算機(jī)世界中的場景

• 消息隊(duì)列 RabbitMQ
• UDP協(xié)議（接收端將消息存放在隊(duì)列中，從隊(duì)列中讀取數(shù)據(jù)）

二、高屋建瓴，縱覽全局

18種隊(duì)列分為三大類： 接口、抽象類、普通類。

弄清楚下面的繼承實(shí)現(xiàn)關(guān)系對后面理解18種隊(duì)列有很大幫助。

• Queue接口繼承 Collection接口，Collection接口繼承 ?Iterable接口
• BlockingQueue接口、Deque接口 繼承 Queue接口
• AbstractQueue抽象類實(shí)現(xiàn) Queue接口
• BlockingDeque接口、TransferQueue接口繼承 BlockingQueue接口
• BlockingDeque接口繼承Deque接口
• LinkedBlockingDeque類實(shí)現(xiàn) BlockingDeque接口
• LinkedTransferQueue類接口實(shí)現(xiàn) TransferQueue接口
• LinkedList類、ArrayDeque類、ConcurrentLinkedDeque類實(shí)現(xiàn) 了Deque接口
• ArrayBlockingQueue類、LinkendBlockingQueue類、LinkedBlockingDeque類、LinkedTransferQueue類、SynchronousQueue類、PriorityBlockQueue類、DelayQueue類繼承 了AbstractQueue抽象類和實(shí)現(xiàn)了BlockingQueue接口
• PriorityQueue類和ConcurrentLinkedQueue類繼承 了AbstractQueue抽象類

注意：

• Deque：全稱Double-Ended queue，表示雙端隊(duì)列。
• 類實(shí)現(xiàn)接口，用implements
• 接口繼承接口，用 extends
• 類繼承類，用extends

三、萬物歸宗Queue接口

2.1 深入理解Queue接口的本質(zhì)

• Queue接口是一種Collection，被設(shè)計用于處理之前臨時保存在某處的元素。

• 除了基本的Collection操作之外，隊(duì)列還提供了額外的插入、提取和檢查操作。每一種操作都有兩種形式：如果操作失敗，則拋出一個異常；如果操作失敗，則返回一個特殊值（null或false，取決于是什么操作）。

• 隊(duì)列通常是以FIFO（先進(jìn)先出）的方式排序元素，但是這不是必須的。

• 只有優(yōu)先級隊(duì)列可以根據(jù)提供的比較器對元素進(jìn)行排序或者是采用正常的排序。無論怎么排序，隊(duì)列的頭將通過調(diào)用remove()或poll()方法進(jìn)行移除。在FIFO隊(duì)列種，所有新的元素被插入到隊(duì)尾。其他種類的隊(duì)列可能使用不同的布局來存放元素。

• 每個Queue必須指定排序?qū)傩浴?/p>

2.2 Queue接口的核心方法

總共有3組方法，每一組方法對應(yīng)兩個方法。如下圖所示：

• （1）比如添加（Insert）元素的動作，會有兩種方式：add(e)和offer(e)。如果調(diào)用add(e)方法時，添加失敗，則會拋異常，而如果調(diào)用的是offer(e)方法失敗時，則會返回false。offer方法用于異常是正常的情況下使用，比如在有界隊(duì)列中，優(yōu)先使用offer方法。假如隊(duì)列滿了，不能添加元素，offer方法返回false，這樣我們就知道是隊(duì)列滿了，而不是去handle運(yùn)行時拋出的異常。

• （2）同理，移除（Remove）元素的動作，隊(duì)列為空時，remove方法拋異常，而poll返回null。如果移除頭部的元素成功，則返回移除的元素。

• （3）同理，檢測（Examine）元素的動作，返回頭部元素（最開始加入的元素），但不刪除元素， 如果隊(duì)列為空，則element()方法拋異常，而peek()返回false。

• （4）Queue接口沒有定義阻塞隊(duì)列的方法，這些方法在BlockQueue接口中定義了。

• （5）Queue實(shí)現(xiàn)類通常不允許插入null元素，盡管一些實(shí)現(xiàn)類比如LinkedList不禁止插入null，但是還是不建議插入null，因?yàn)閚ull也被用在poll方法的特殊返回值，以說明隊(duì)列不包含元素。

四、雙端可用Deque接口

4.1 深入理解Deque接口的原理

（1）Deque概念： 支持兩端元素插入和移除的線性集合。名稱deque是雙端隊(duì)列的縮寫，通常發(fā)音為deck。大多數(shù)實(shí)現(xiàn)Deque的類，對它們包含的元素的數(shù)量沒有固定的限制的，支持有界和無界。

（2）Deque方法說明：

說明：

• 該列表包含包含訪問deque兩端元素的方法，提供了插入，移除和檢查元素的方法。

• 這些方法種的每一種都存在兩種形式：如果操作失敗，則會拋出異常，另一種方法返回一個特殊值（null或false，取決于具體操作）。

• 插入操作的后一種形式專門設(shè)計用于容量限制的Deque實(shí)現(xiàn)，大多數(shù)實(shí)現(xiàn)中，插入操作不能失敗，所以可以用插入操作的后一種形式。

• Deque接口擴(kuò)展了Queue接口，當(dāng)使用deque作為隊(duì)列時，作為FIFO。元素將添加到deque的末尾，并從頭開始刪除。

• 作為FIFO時等價于Queue的方法如下表所示：

比如Queue的add方法和Deque的addLast方法等價。

• Deque也可以用作LIFO（后進(jìn)先出）棧，這個接口優(yōu)于傳統(tǒng)的Stack類。當(dāng)作為棧使用時，元素被push到deque隊(duì)列的頭，而pop也是從隊(duì)列的頭pop出來。

• Stack（棧）的方法正好等同于Deque的如下方法：

  

注意：peek方法不論是作為棧還是隊(duì)列，都是從隊(duì)列的檢測隊(duì)列的頭，返回最先加入的元素。比如第一次put 100，第二次put 200，則peek返回的是100。如下圖所示：

4.1 哪些類實(shí)現(xiàn)了Deque接口

• LinkedList類
• ArrayDeque類
• ConcurrentLinkedDeque類
• LinkedBlockingDeque類

4.2 哪些類繼承了Deque接口

• BlockingDeque接口

五、隊(duì)列骨架AbstractQueue抽象類

5.1 ?深入理解AbstractQueue抽象類

AbstractQueue是一個抽象類，繼承了Queue接口，提供了一些Queue操作的骨架實(shí)現(xiàn)。

方法add、remove、element方法基于offer、poll和peek。也就是說如果不能正常操作，則拋出異常。我們來看下AbstactQueue是怎么做到的。

• AbstractQueue的add方法

public?boolean?add(E?e)?{
????if?(offer(e))
????????return?true;
????else
????????throw?new?IllegalStateException("Queue?full");
}

• AbstractQueue的remove方法

public?E?remove()?{
????E?x?=?poll();
????if?(x?!=?null)
????????return?x;
????else
????????throw?new?NoSuchElementException();
}

• AbstractQueue的element方法

public?E?element()?{
????E?x?=?peek();
????if?(x?!=?null)
????????return?x;
????else
????????throw?new?NoSuchElementException();
}

注意：

• 如果繼承AbstractQueue抽象類則必須保證offer方法不允許null值插入。

5.2 哪些類繼承了AbstractQueue抽象類

• ArrayBlockingQueue類、LinkendBlockingQueue類、LinkedBlockingDeque類、LinkedTransferQueue類、SynchronousQueue類、PriorityBlockQueue類、DelayQueue類繼承 了AbstractQueue抽象類
• PriorityQueue類和ConcurrentLinkedQueue類繼承 了AbstractQueue抽象類

六、阻塞緩沖BlockingQueue接口

6.1 宏觀來看BlockingQueue（阻塞隊(duì)列）

• BlockQueue滿了，PUT操作被阻塞

• BlockQueue為空，Take操作被阻塞

（1）BlockingQueue（阻塞隊(duì)列）也是一種隊(duì)列，支持阻塞的插入和移除方法。

（3）阻塞的插入：當(dāng)隊(duì)列滿時，隊(duì)列會阻塞插入元素的線程，直到隊(duì)列不滿。

（4）阻塞的移除：當(dāng)隊(duì)列為空，獲取元素的線程會等待隊(duì)列變?yōu)榉强铡?/p>

（5）應(yīng)用場景：生產(chǎn)者和消費(fèi)者，生產(chǎn)者線程向隊(duì)列里添加元素，消費(fèi)者線程從隊(duì)列里移除元素，阻塞隊(duì)列時獲取和存放元素的容器。

（6）為什么要用阻塞隊(duì)列：生產(chǎn)者生產(chǎn)和消費(fèi)者消費(fèi)的速率不一樣，需要用隊(duì)列來解決速率差問題，當(dāng)隊(duì)列滿了或空的時候，則需要阻塞生產(chǎn)或消費(fèi)動作來解決隊(duì)列滿或空的問題。

6.2 案例解析

線程A往阻塞隊(duì)列（Blocking Queue）中添加元素，而線程B從阻塞隊(duì)列中移除元素。

• 當(dāng)阻塞隊(duì)列為空的時候 （一個元素都沒有），則從隊(duì)列中獲取元素的操作將會被阻塞。
• 生活中的案例：去海底撈吃火鍋的時候，早上8點(diǎn)沒人來吃火鍋，所以需要等客人過來。
• 翻譯成線程：現(xiàn)在沒有元素需要添加，而且阻塞隊(duì)列為空，所以線程B不需要從隊(duì)列中拿元素出來，所以線程B獲取元素的操作被阻塞了。
• 當(dāng)阻塞隊(duì)列滿了的時候 （所有位置都放有元素），則從隊(duì)列中添加元素的操作將會被阻塞。
• 生活中的案例：去海底撈吃火鍋的時候，人太多了，需要排號，等其他桌空出來了才能進(jìn)去。
• 翻譯成線程：線程A往阻塞隊(duì)列中添加元素，將隊(duì)列填滿了，線程B現(xiàn)在正在忙，無法拿出隊(duì)列中的元素，所以阻塞隊(duì)列沒有地方再放元素了，這個時候線程A添加元素的操作就被阻塞了

6.3 操刀BlockingQueue接口

BlockingQueue接口的10個核心方法：

10個核心方法總結(jié)如下：

有三大類操作：插入、移除、檢查。

• 插入有四種方法： add、offer、put、offer超時版。
• IllegalStateException - 隊(duì)列滿了
• ClassCastException - 添加的元素類型不匹配
• NullPointerException - 添加的元素為null
• IllegalArgumentException - 添加的元素某些屬性不匹配
• add方法特別之處用于添加失敗時拋出異常，共有四種異常：
• offer方法特別之處用于添加失敗時只返回false
• put方法特別之處用于當(dāng)阻塞隊(duì)列滿時，生產(chǎn)者如果往隊(duì)列里put元素，則隊(duì)列會一直阻塞生產(chǎn)者線程，直到隊(duì)列可用或者響應(yīng)中斷退出
• offer超時方法特別之處用于當(dāng)阻塞隊(duì)列滿時，生產(chǎn)者如果往隊(duì)列里面插入元素，隊(duì)列會阻塞生產(chǎn)者線程一段時間，如果超過了指定時間，生產(chǎn)者線程會退出，并返回false。
• 移除有四種方法： remove、poll、take、poll超時版
• NoSuchElementException - 如果這個隊(duì)列是空的
• remove方法特別之處用于移除失敗時拋出異常
• poll方法特別之處用于移除失敗時返回null
• take方法特別之處用于當(dāng)阻塞隊(duì)列為空時，消費(fèi)者線程如果從隊(duì)列里面移除元素，則隊(duì)列會一直阻塞消費(fèi)者線程，直到隊(duì)列不為空
• poll超時方法特別之處用于當(dāng)阻塞隊(duì)列空時，消費(fèi)者如果從隊(duì)列里面刪除元素，則隊(duì)列會一直阻塞消費(fèi)者線程，如果超過了指定時間，消費(fèi)者線程會退出，并返回null
• 檢查有兩種方法： element、peek
• element方法用于檢測頭部元素的存在性，如果隊(duì)列為空，則拋出異常，否則返回頭部元素。
• peek方法用于檢測頭部元素的存在性，如果隊(duì)列為空，返回特殊值null，否則返回頭部的元素。

6.4 BlockingQueue通過什么來阻塞插入和移除的？

• 當(dāng)往隊(duì)列里插入一個元素時，如果隊(duì)列不可用，那么阻塞生產(chǎn)者主要通過LockSupport. park（this）來實(shí)現(xiàn)。
• park這個方法會阻塞當(dāng)前線程，只有以下4種情況中的一種發(fā)生時，該方法才會返回。
• 與park對應(yīng)的unpark執(zhí)行或已經(jīng)執(zhí)行時。“已經(jīng)執(zhí)行”是指unpark先執(zhí)行，然后再執(zhí)行park的情況。
• 線程被中斷時。
• 等待完time參數(shù)指定的毫秒數(shù)時。
• 異常現(xiàn)象發(fā)生時，這個異?，F(xiàn)象沒有任何原因。

6.5 哪些類繼承了BlockingQueue接口？

• BlockingDeque接口 - 雙端阻塞隊(duì)列
• TransferQueue接口 - 傳輸隊(duì)列

6.6 哪些類實(shí)現(xiàn)了BlockingQueue接口？

• ArrayBlockingQueue類 - 由數(shù)組構(gòu)成的有界阻塞隊(duì)列
• LinkedBlockingQueue類 - 由鏈表構(gòu)成的有界阻塞隊(duì)列，界限默認(rèn)大小為Integer.MAX_Value（2^31-1），值非常大，相當(dāng)于無界。
• LinkedBlockingDeque類 - 由鏈表構(gòu)成的雙向阻塞隊(duì)列
• LinkedTransferQueue類 - 由鏈表構(gòu)成的無界阻塞隊(duì)列
• SynchronousQueue類 - 不存儲元素的阻塞隊(duì)列，只有一個元素進(jìn)行數(shù)據(jù)傳遞。
• LinkedTransferQueue類 - 由鏈表構(gòu)成的無界阻塞TransferQueue隊(duì)列
• DelayQueue類 - 使用優(yōu)先級隊(duì)列實(shí)現(xiàn)的延遲無界阻塞隊(duì)列

6.6 BlockingQueue接口繼承了哪些接口

• BlockingQueue接口繼承了Queue接口，可作為隊(duì)列使用

七、雙端阻塞BlockingDeque接口

7.1 從原理圖上理解BlockDeque

• BlockQueue滿了，兩端的Take操作被阻塞

• BlockQueue為空，兩端的Take操作被阻塞

7.2 BlockingDeque接口方法

是阻塞隊(duì)列BlockingQueue和雙向隊(duì)列Deque接口的結(jié)合。有如下方法：

示例：

嘗試執(zhí)行以下方法：

LinkedBlockingDeque?queue?=?new?LinkedBlockingDeque();
queue.addFirst("test1");
queue.addFirst(300);
queue.addLast("400");

最后隊(duì)列中的元素順序如下：

300, test1, 400。

先添加了test1放到隊(duì)列的頭部，然后在頭部的前面放入300，所以300在最前面，成為頭部，然后將400放入隊(duì)列的尾部，所以最后的結(jié)果是300, test1, 400。

7.3 BlockDeque和BlockQueue的對等方法

7.4 BlockingDeque的特點(diǎn)

• 線程安全。
• 不允許使用null元素。
• 無界和有界都可以。

7.5 BlockingDeque接口繼承了哪些接口？

• Queue接口，具有隊(duì)列的功能
• Deque接口，具有雙端隊(duì)列的功能
• BlockingQueue接口，可作為阻塞隊(duì)列使用

7.6 哪些類實(shí)現(xiàn)了BlockDeque接口？

• LinkedBlockingDeque

八、使命必達(dá)TransferQueue接口

8.1 Transfer怎么理解？

如果有消費(fèi)者正在獲取元素，則將隊(duì)列中的元素傳遞給消費(fèi)者。如果沒有消費(fèi)者，則等待消費(fèi)者消費(fèi)。我把它稱作使命必達(dá)隊(duì)列，必須將任務(wù)完成才能返回。

8.2 生活中的案例

• 針對TransferQueue的transfer方法
• 圓通快遞員要將小明的2個快遞送貨到門，韻達(dá)快遞員也想將小明的2個快遞送貨到門。小明一次只能拿一個，快遞員必須等小明拿了一個后，才能繼續(xù)給第二個。
• 針對TransferQueue的tryTransfer方法
• 圓通快遞員要將小明的2個快遞送貨到門，韻達(dá)快遞員也想將小明的2個快遞送貨到門。發(fā)現(xiàn)小明不在家，就把快遞直接放到菜鳥驛站了。
• 針對TransferQueue的tryTransfer超時方法
• 圓通快遞員要將小明的2個快遞送貨到門，韻達(dá)快遞員也想將小明的2個快遞送貨到門。發(fā)現(xiàn)小明不在家，于是先等了5分鐘，發(fā)現(xiàn)小明還沒有回來，就把快遞直接放到菜鳥驛站了。

8.3 TransferQueue的原理解析

• transfer(E e)

  原理如下圖所示：

  

• 原理圖解釋：生產(chǎn)者線程Producer Thread嘗試將元素B傳給消費(fèi)者線程，如果沒有消費(fèi)者線程，則將元素B放到尾節(jié)點(diǎn)。并且生產(chǎn)者線程等待元素B被消費(fèi)。當(dāng)元素B被消費(fèi)后，生產(chǎn)者線程返回。
• 如果當(dāng)前有消費(fèi)者正在等待接收元素（消費(fèi)者通過take方法或超時限制的poll方法時），transfer方法可以把生產(chǎn)者傳入的元素立刻transfer（傳輸）給消費(fèi)者。
• 如果沒有消費(fèi)者等待接收元素，transfer方法會將元素放在隊(duì)列的tail（尾）節(jié)點(diǎn)，并等到該元素被消費(fèi)者消費(fèi)了才返回。

• tryTransfer(E e)

• 試探生產(chǎn)者傳入的元素是否能直接傳給消費(fèi)者。
• 如果沒有消費(fèi)者等待接收元素，則返回false。
• 和transfer方法的區(qū)別是，無論消費(fèi)者是否接收，方法立即返回。

• tryTransfer(E e, long timeout, TimeUnit unit)

• 帶有時間限制的tryTransfer方法。
• 試圖把生產(chǎn)者傳入的元素直接傳給消費(fèi)者。
• 如果沒有消費(fèi)者消費(fèi)該元素則等待指定的時間再返回。
• 如果超時了還沒有消費(fèi)元素，則返回false。
• 如果在超時時間內(nèi)消費(fèi)了元素，則返回true。

• getWaitingConsumerCount()

• 獲取通過BlockingQueue.take()方法或超時限制poll方法等待接受元素的消費(fèi)者數(shù)量。近似值。
• 返回等待接收元素的消費(fèi)者數(shù)量。

• hasWaitingConsumer()

• 獲取是否有通過BlockingQueue.tabke()方法或超時限制poll方法等待接受元素的消費(fèi)者。
• 返回true則表示至少有一個等待消費(fèi)者。

8.3 TransferQueue接口繼承了哪些接口？

• BlockingQueue接口，可作為阻塞隊(duì)列使用
• Queue接口，可作為隊(duì)列使用

8.4 哪些類實(shí)現(xiàn)了TransferQueue接口？

• LinkedTranferQueue接口

九、優(yōu)先由你PriorityQueue類

9.1 理解PriorityQueue類

• 本應(yīng)該按照升序排序

• 按照倒敘排序

• PriorityQueue是一個支持優(yōu)先級的無界阻塞隊(duì)列。

• 默認(rèn)自然順序升序排序。

• 可以通過構(gòu)造參數(shù)Comparator來對元素進(jìn)行排序。

public?PriorityQueue(Comparatorsuper?E>?comparator)?{
?????this(DEFAULT_INITIAL_CAPACITY,?comparator);
}

• 自定義實(shí)現(xiàn)comapreTo()方法來指定元素排序規(guī)則。

public?Comparatorsuper?E>?comparator()?{
????return?comparator;
}

• 不允許插入null元素。
• 實(shí)現(xiàn)PriorityQueue接口的類，不保證線程安全，除非是PriorityBlockingQueue。
• PriorityQueue的迭代器不能保證以任何特定順序遍歷元素，如果需要有序遍歷，請考慮使用Arrays.sort(pq.toArray)。
• 進(jìn)列(offer、add)和出列（ poll、remove()）的時間復(fù)雜度O(log(n))。
• remove(Object) 和 contains(Object)的算法時間復(fù)雜度O(n)。
• peek、element、size的算法時間復(fù)雜度為O(1)。

9.2 PriorityQueue類繼承了哪些類？

• AbstractQueue抽象類，具有隊(duì)列的功能

9.2 PriorityQueue類實(shí)現(xiàn)了哪些接口？

• Queue接口，可作為隊(duì)列使用。

十、雙向鏈表LinkedList類

10.1 LinkedList的結(jié)構(gòu)

• LinkedList實(shí)現(xiàn)了List和Deque接口，所以是一種雙鏈表結(jié)構(gòu)，可以當(dāng)作堆棧、隊(duì)列、雙向隊(duì)列使用。
• 一個雙向列表的每一個元素都有三個整數(shù)值：元素、向后的節(jié)點(diǎn)鏈接、向前的節(jié)點(diǎn)鏈接

我們來看下節(jié)點(diǎn)類Node

private?static?class?Node<E>?{
????E?item;?//元素
????Node?next;?//向后的節(jié)點(diǎn)鏈接
????Node?prev;?//向前的節(jié)點(diǎn)鏈接

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

10.2 與ArrayList的區(qū)別

• 1.LinkedList的增加和刪除效率相對較高，而查找和修改的效率相對較低。

• 2.以下情況建議使用ArrayList

• 頻繁訪問列表中的一個元素。
• 只在列表的首尾添加元素。

• 3.以下情況建議使用LinkedList

• 頻繁地在列表開頭、中間、末尾添加和刪除元素。
• 需要通過循環(huán)迭代來訪問列表中的元素。

10.3 LinkedList不是線程安全的

LinkedList不是線程安全的，所以可以使用如下方式保證線程安全。

List?list?=?Collections.synchronizedList(new?LinkedList<>());

10.4 LinkedList的家庭成員關(guān)系

• LinkedList 繼承了 AbstractSequentialList 類。

• LinkedList 實(shí)現(xiàn)了 Queue 接口，可作為隊(duì)列使用。

• LinkedList 繼承了 AbstractQueue抽象類，具有隊(duì)列的功能。

• LinkedList 實(shí)現(xiàn)了 List 接口，可進(jìn)行列表的相關(guān)操作。

• LinkedList 實(shí)現(xiàn)了 Deque 接口，可作為雙向隊(duì)列使用。

• LinkedList 實(shí)現(xiàn)了 Cloneable 接口，可實(shí)現(xiàn)克隆。

• LinkedList 實(shí)現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十一、并發(fā)安全ConcurrentLinkedQueue類

11.1 理解ConcurrentLinkedQueue

• ConcurrentLinked是由鏈表結(jié)構(gòu)組成的線程安全的先進(jìn)先出無界隊(duì)列。
• 當(dāng)多線程要共享訪問集合時，ConcurrentLinkedQueue是一個比較好的選擇。
• 不允許插入null元素
• 支持非阻塞地訪問并發(fā)安全的隊(duì)列，不會拋出ConcurrentModifiationException異常。
• size方法不是準(zhǔn)確的，因?yàn)樵诮y(tǒng)計集合的時候，隊(duì)列可能正在添加元素，導(dǎo)致統(tǒng)計不準(zhǔn)。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保證原子性（操作不可分割）
• 添加元素happen-before其他線程移除元素。
• 用法如下：

ConcurrentLinkedQueue?queue?=?new?ConcurrentLinkedQueue();
BuildingBlockWithName?buildingBlock?=?new?BuildingBlockWithName("三角形",?"A");
concurrentLinkedQueue.add(buildingBlock);

11.2 ConcurrentLinkedQueue類繼承了哪些類？

• AbstractQueue抽象類，具有隊(duì)列的功能

11.3 ConcurrentLinkedQueue類實(shí)現(xiàn)了哪些接口？

• Queue接口，可作為隊(duì)列使用

十二、雙向數(shù)組ArrayDeque類

12.1 理解ArrayDeque

• 由數(shù)組組成的雙端隊(duì)列。
• 沒有容量限制，根據(jù)需要擴(kuò)容。
• 不是線程安全的。
• 禁止插入null元素。
• 當(dāng)用作棧時，比棧速度快，當(dāng)用作隊(duì)列時，速度比LinkList快。
• 大部分方法的算法時間復(fù)雜度為O(1)。
• remove、removeFirstOccurrence、removeLastOccurrence、contains、remove 和批量操作的算法時間復(fù)雜度O(n)

12.2 使用方法

創(chuàng)建一個ArrayDeque，往arrayDeque隊(duì)尾添加元素。

ArrayDeque?arrayDeque?=?new?ArrayDeque();
for?(int?i?=?0;?i?50;?i++)?{
????arrayDeque.add(buildingBlock);?//?add方法等價于addLast方法
}

12.3 ArrayDeque實(shí)現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊(duì)列

十三、雙向并發(fā)ConcurrentLinkedDeque類

13.1 理解ConcurrentLinkedDeque類

• 由鏈表結(jié)構(gòu)組成的雙向無界阻塞隊(duì)列
• 插入、刪除和訪問操作可以并發(fā)進(jìn)行，線程安全的類
• 不允許插入null元素
• 在并發(fā)場景下，計算隊(duì)列的大小是不準(zhǔn)確的，因?yàn)橛嬎銜r，可能有元素加入隊(duì)列。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保證原子性（操作不可分割）

13.2 ConcurrentLinkedDeque使用示例

創(chuàng)建兩個積木：三角形、四邊形，然后添加到隊(duì)列：

BuildingBlockWithName?buildingBlock1?=?new?BuildingBlockWithName("三角形",?"A");
BuildingBlockWithName?buildingBlock2?=?new?BuildingBlockWithName("四邊形",?"B");
ConcurrentLinkedDeque?concurrentLinkedDeque?=?new?ConcurrentLinkedDeque();
concurrentLinkedDeque.addFirst(buildingBlock1);
concurrentLinkedDeque.addLast(buildingBlock2);
//結(jié)果：順序：三角形、四邊形

13.3 ConcurrentLinkedDeque實(shí)現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊(duì)列

十四、數(shù)組阻塞ArrayBlockingQueue類

14.1 理解ArrayBlockingQueue

• ArrayBlockingQueue是一個用數(shù)組實(shí)現(xiàn)的有界阻塞隊(duì)列。
• 隊(duì)列慢時插入操作被阻塞，隊(duì)列空時，移除操作被阻塞。
• 按照先進(jìn)先出（FIFO）原則對元素進(jìn)行排序。
• 默認(rèn)不保證線程公平的訪問隊(duì)列。
• 公平訪問隊(duì)列：按照阻塞的先后順序訪問隊(duì)列，即先阻塞的線程先訪問隊(duì)列。
• 非公平性是對先等待的線程是非公平的，當(dāng)隊(duì)列可用時，阻塞的線程都可以爭奪訪問隊(duì)列的資格。有可能先阻塞的線程最后才訪問訪問隊(duì)列。
• 公平性會降低吞吐量。

14.2 ArrayBlockingQueue使用示例

創(chuàng)建兩個積木：三角形、四邊形，然后添加到隊(duì)列：

BuildingBlockWithName?buildingBlock1?=?new?BuildingBlockWithName("三角形",?"A");
BuildingBlockWithName?buildingBlock2?=?new?BuildingBlockWithName("四邊形",?"B");
ArrayBlockingQueue?arrayBlockingQueue?=?new?ArrayBlockingQueue(100,?true);
arrayBlockingQueue.add(buildingBlock1);
arrayBlockingQueue.add(buildingBlock2);

14.3 ArrayBlockQueue實(shí)現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊(duì)列

十五、鏈表阻塞LinkedBlockingQueue類

15.1 理解LinkedBlockingQueue

• LinkedBlockingQueue具有單鏈表和有界阻塞隊(duì)列的功能。
• 隊(duì)列慢時插入操作被阻塞，隊(duì)列空時，移除操作被阻塞。
• 默認(rèn)和最大長度為Integer.MAX_VALUE，相當(dāng)于無界(值非常大：2^31-1)。

15.2 LinkedBlockingQueue使用示例

LinkedList?linkedList1?=?new?LinkedList();
linkedList1.add("A");
linkedList1.add("B");
linkedList1.add("C");

15.3 LinkedBlockingQueue的應(yīng)用場景

• 吞吐量通常要高于ArrayBlockingQueue。創(chuàng)建線程池時，參數(shù)runnableTaskQueue（任務(wù)隊(duì)列），用于保存等待執(zhí)行的任務(wù)的阻塞隊(duì)列可以選擇LinkedBlockingQueue。靜態(tài)工廠方法Executors.newFixedThreadPool()使用了這個隊(duì)列。

15.4 LinkedBlockingQueue實(shí)現(xiàn)了哪些接口

• LinkedBlockingQueue繼承了 BlockingQueue類，可作為阻塞隊(duì)列使用
• LinkedBlockingQueue繼承了 AbstractQueue抽象類，具有隊(duì)列的功能。
• LinkedBlockingQueue實(shí)現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十六、雙向阻塞LinkedBlockingDeque類

16.1 理解LinkedBlockingDeque類

• 由鏈LinkedBlockingDeque = 阻塞隊(duì)列+鏈表+雙端訪問
• 線程安全。
• 多線程同時入隊(duì)時，因多了一端訪問入口，所以減少了一半的競爭。
• 默認(rèn)容量大小為Integer.MAX_VALUE?？芍付ㄈ萘看笮?。

16.2 LinkedBlockingDeque的應(yīng)用場景

LinkedBlockingDeque可以用在“工作竊取“模式中。

工作竊取算法：某個線程比較空閑，從其他線程的工作隊(duì)列中的隊(duì)尾竊取任務(wù)來幫忙執(zhí)行。

16.3 LinkedBlockingDeque實(shí)現(xiàn)了哪些接口

• LinkedBlockingDeque繼承了 BlockingDeque類，可作為阻塞隊(duì)列使用
• LinkedBlockingDeque繼承了 AbstractQueue抽象類，具有隊(duì)列的功能。
• LinkedBlockingDeque實(shí)現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十七、鏈表阻塞LinkedTransferQueue類

17.1 理解LinkedTransferQueue類

LinkedTransferQueue = 阻塞隊(duì)列+鏈表結(jié)構(gòu)+TransferQueue

之前我們講“使命必達(dá)TransferQueue接口時已經(jīng)介紹過了TransferQueue接口 ，所以LinkedTransferQueue接口跟它相似，只是加入了阻塞插入和移除的功能，以及結(jié)構(gòu)是鏈表結(jié)構(gòu)。

之前的TransferQueue也講到了3個案例來說明TransferQueue的原理，大家可以回看TransferQueue。

17.2 LinkedTransferQueue接口比其他阻塞隊(duì)列多了5個方法

• transfer(E e)
• tryTransfer(E e)
• tryTransfer(E e, long timeout, TimeUnit unit)
• getWaitingConsumerCount()
• hasWaitingConsumer()

17.3 LinkedTransferQueue代碼示例

• 創(chuàng)建一個LinkedTransferQueue，生產(chǎn)者1 依次往隊(duì)列中添加 A、B、C

• 生產(chǎn)者2 依次往隊(duì)列中添加 D、E、F

• 消費(fèi)者依次從隊(duì)列首部開始消費(fèi)元素，每次消費(fèi)前，先sleep 2s，來演示transfer方法是否進(jìn)行了等待。

• 運(yùn)行結(jié)果

生產(chǎn)者1?????transfer?A?
生產(chǎn)者2?????transfer?D?

2s后...
??
消費(fèi)者??????take?A
生產(chǎn)者1?????put?B?
?
2s后...
?????
消費(fèi)者??????take?D
生產(chǎn)者2?????transfer?E?
????
2s后...
??
消費(fèi)者??????take?B
生產(chǎn)者1?????transfer?C?

• 代碼執(zhí)行結(jié)果分析

（1）首先生產(chǎn)者線程1和2 調(diào)用transfer方法來傳輸A和D，發(fā)現(xiàn)沒有消費(fèi)者線程接收，所以被阻塞。

（2）消費(fèi)者線程過了2s后將A拿走了，然后生產(chǎn)者1 被釋放繼續(xù)執(zhí)行，傳輸元素B，發(fā)現(xiàn)又沒有消費(fèi)者消費(fèi)，所以進(jìn)行了等待。

（3）消費(fèi)者線程過了2s后，將排在隊(duì)列首部的D元素拿走，生產(chǎn)者2繼續(xù)往下執(zhí)行，傳輸元素E，發(fā)現(xiàn)沒有消費(fèi)者，所以進(jìn)行了等待。

（4）消費(fèi)者線程過了2s后，將排在隊(duì)列首部的B元素拿走，生產(chǎn)者1傳輸C元素，等待消費(fèi)者拿走。

（5）消費(fèi)者不再消費(fèi)了，所以生產(chǎn)者1和生產(chǎn)者2都被阻塞了，元素C和，元素E都沒有被拿走，而且生產(chǎn)者2的F元素還沒有開始傳輸，因?yàn)樵诘却谼被拿走。

（6）看下隊(duì)列里面確實(shí)有C和E元素，而且E排在隊(duì)列的首部。

17.4 LinkedTransferQueue實(shí)現(xiàn)了哪些接口

• LinkedBlockingDeque繼承了 BlockingQeque類，可作為阻塞隊(duì)列使用
• LinkedBlockingDeque繼承了 AbstractQueue抽象類，具有隊(duì)列的功能。

十八、傳球好手SynchronousQueue類

18.1 理解SynchronousQueue類

• 我稱SynchronousQueue為”傳球好手“。想象一下這個場景：小明抱著一個籃球想傳給小花，如果小花沒有將球拿走，則小明是不能再拿其他球的。

• SynchronousQueue負(fù)責(zé)把生產(chǎn)者產(chǎn)生的數(shù)據(jù)傳遞給消費(fèi)者線程。

• SynchronousQueue本身不存儲數(shù)據(jù)，調(diào)用了put方法后，隊(duì)列里面也是空的。

• 每一個put操作必須等待一個take操作完成，否則不能添加元素。

• 適合傳遞性場景。

• 性能高于ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

我們創(chuàng)建了兩個線程，一個線程用于生產(chǎn)，一個線程用于消費(fèi)

• 生產(chǎn)的線程依次put A、B、C三個值

• 消費(fèi)線程使用take來消費(fèi)阻塞隊(duì)列中的內(nèi)容，每次消費(fèi)前，等待5秒

• 運(yùn)行結(jié)果

t1?????put?A?
t2?????take?A?

5秒后...

t1?????put?B?
t2?????take?B?

5秒后...

t1?????put?C?
t2?????take?C?

小結(jié)：說明生產(chǎn)線程執(zhí)行put第一個元素"A" 操作后，需要等待消費(fèi)者線程take完“A”后，才能繼續(xù)往下執(zhí)行代碼。

18.1 SynchronousQueue應(yīng)用場景

• 吞吐量通常要高于LinkedBlockingQueue。創(chuàng)建線程池時，參數(shù)runnableTaskQueue（任務(wù)隊(duì)列），用于保存等待執(zhí)行的任務(wù)的阻塞隊(duì)列可以選擇SynchronousQueue。靜態(tài)工廠方法Executors.newCachedThreadPool()使用了這個隊(duì)列

18.2 SynchronousQueue和LinkedTransferQueue的區(qū)別

• SynchronousQueue 不存儲元素，而LinkedTransferQueue存儲元素。
• SynchronousQueue 隊(duì)列里面沒有元素，而LinkedTransferQueue可以有多個存儲在隊(duì)列等待傳輸。
• LinkedTransferQueue還支持若傳輸不了，則丟到隊(duì)列里面去。
• LinkedTransferQueue還支持若超過一定時間傳輸不了，則丟到隊(duì)列里面去。

十九、優(yōu)先級阻塞PriorityBlockingQueue類

19.1 理解PriorityBlockQueue類

• PriorityBlockQueue = PriorityQueue + BlockingQueue
• 之前我們也講到了PriorityQueue的原理，支持對元素排序。
• 元素默認(rèn)自然排序。
• 可以自定義CompareTo()方法來指定元素排序規(guī)則。
• 可以通過構(gòu)造函數(shù)構(gòu)造參數(shù)Comparator來對元素進(jìn)行排序。

19.2 PriorityBlockQueue實(shí)現(xiàn)了哪些接口

• LinkedBlockingQueue繼承了 BlockingQueue接口，可作為阻塞隊(duì)列使用
• LinkedBlockingQueue繼承了 AbstractQueue抽象類，具有隊(duì)列的功能。
• LinkedBlockingQueue實(shí)現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

二十、延時阻塞DelayQueue類

20.1 理解DelayQueue

• DelayQueue = Delayed + BlockingQueue。隊(duì)列中的元素必須實(shí)現(xiàn)Delayed接口。

public?class?DelayQueue<E?extends?Delayed>?extends?AbstractQueue<E>
????implements?BlockingQueue<E>?{

• 在創(chuàng)建元素時，可以指定多久可以從隊(duì)列中獲取到當(dāng)前元素。只有在延時期滿才能從隊(duì)列中獲取到當(dāng)前元素。

20.2 源碼解析

• 添加元素時，指定延時多久可以從隊(duì)列中獲取元素

public?boolean?offer(E?e,?long?timeout,?TimeUnit?unit)?{
????return?offer(e);
}

• 獲取元素的方法poll需要等待延時時間過了才能獲取到元素

if?(first?==?null?||?first.getDelay(NANOSECONDS)?>?0)
????return?null;
else
????return?q.poll();

20.3 應(yīng)用場景

• 緩存系統(tǒng)的設(shè)計：可以用DelayQueue保存緩存元素的有效期。然后用一個線程循環(huán)的查詢DelayQueue隊(duì)列，一旦能從DelayQueue中獲取元素時，表示緩存有效期到了。

• 定時任務(wù)調(diào)度：使用DelayQueue隊(duì)列保存當(dāng)天將會執(zhí)行的任務(wù)和執(zhí)行時間，一旦從DelayQueue中獲取到任務(wù)就開始執(zhí)行。比如Java中的TimerQueue就是使用DelayQueue實(shí)現(xiàn)的。

20.4 DelayQueue實(shí)現(xiàn)了哪些接口

• DelayQueue實(shí)現(xiàn)了 BlockingQueue接口，可作為阻塞隊(duì)列使用

這一篇花了很多心思在上面，看官方英文文檔、畫原理圖、寫demo代碼，排版。這恐怕是市面上最全最細(xì)講解Queue的。

關(guān)注，邁開成長的第一步