干貨 | 45張圖庖丁解牛18種Queue，你知道幾種？

在講《21張圖講解集合的線程不安全》那一篇，我留了一個(gè)彩蛋，就是Queue（隊(duì)列）還沒(méi)有講，這次我們重點(diǎn)來(lái)看看Java中的Queue家族，總共涉及到18種Queue。這篇恐怕是市面上最全最細(xì)講解Queue的。

本篇主要內(nèi)容如下：

幫你總結(jié)好的阻塞隊(duì)列：

一、Queue自我介紹

1.1 Queue自我介紹

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

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

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

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

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

1.3 計(jì)算機(jī)世界中的場(chǎng)景

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

二、高屋建瓴，縱覽全局

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

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

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

注意：

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

三、萬(wàn)物歸宗Queue接口

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

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

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

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

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

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

2.2 Queue接口的核心方法

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

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

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

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

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

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

四、雙端可用Deque接口

4.1 深入理解Deque接口的原理

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

（2）Deque方法說(shuō)明：

說(shuō)明：

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

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

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

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

• 作為FIFO時(shí)等價(jià)于Queue的方法如下表所示：

比如Queue的add方法和Deque的addLast方法等價(jià)。

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

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

  

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

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

• LinkedList類(lèi)
• ArrayDeque類(lèi)
• ConcurrentLinkedDeque類(lèi)
• LinkedBlockingDeque類(lèi)

4.2 哪些類(lèi)繼承了Deque接口

• BlockingDeque接口

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

5.1 ?深入理解AbstractQueue抽象類(lèi)

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

方法add、remove、element方法基于offer、poll和peek。也就是說(shuō)如果不能正常操作，則拋出異常。我們來(lái)看下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抽象類(lèi)則必須保證offer方法不允許null值插入。

5.2 哪些類(lèi)繼承了AbstractQueue抽象類(lèi)

• ArrayBlockingQueue類(lèi)、LinkendBlockingQueue類(lèi)、LinkedBlockingDeque類(lèi)、LinkedTransferQueue類(lèi)、SynchronousQueue類(lèi)、PriorityBlockQueue類(lèi)、DelayQueue類(lèi)繼承 了AbstractQueue抽象類(lèi)
• PriorityQueue類(lèi)和ConcurrentLinkedQueue類(lèi)繼承 了AbstractQueue抽象類(lèi)

六、阻塞緩沖BlockingQueue接口

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

• BlockQueue滿了，PUT操作被阻塞

• BlockQueue為空，Take操作被阻塞

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

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

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

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

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

6.2 案例解析

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

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

6.3 操刀BlockingQueue接口

BlockingQueue接口的10個(gè)核心方法：

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

有三大類(lèi)操作：插入、移除、檢查。

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

6.4 BlockingQueue通過(guò)什么來(lái)阻塞插入和移除的？

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

6.5 哪些類(lèi)繼承了BlockingQueue接口？

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

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

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

7.4 BlockingDeque的特點(diǎn)

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

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

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

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

• LinkedBlockingDeque

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

8.1 Transfer怎么理解？

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

8.2 生活中的案例

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

8.3 TransferQueue的原理解析

• transfer(E e)

  原理如下圖所示：

  

• 原理圖解釋?zhuān)荷a(chǎn)者線程Producer Thread嘗試將元素B傳給消費(fèi)者線程，如果沒(mé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)者通過(guò)take方法或超時(shí)限制的poll方法時(shí)），transfer方法可以把生產(chǎn)者傳入的元素立刻transfer（傳輸）給消費(fèi)者。
• 如果沒(méi)有消費(fèi)者等待接收元素，transfer方法會(huì)將元素放在隊(duì)列的tail（尾）節(jié)點(diǎn)，并等到該元素被消費(fèi)者消費(fèi)了才返回。

• tryTransfer(E e)

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

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

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

• getWaitingConsumerCount()

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

• hasWaitingConsumer()

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

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

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

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

• LinkedTranferQueue接口

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

9.1 理解PriorityQueue類(lèi)

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

• 按照倒敘排序

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

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

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

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

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

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

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

9.2 PriorityQueue類(lèi)繼承了哪些類(lèi)？

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

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

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

十、雙向鏈表LinkedList類(lèi)

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

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

我們來(lái)看下節(jié)點(diǎn)類(lèi)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的增加和刪除效率相對(duì)較高，而查找和修改的效率相對(duì)較低。

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

• 頻繁訪問(wèn)列表中的一個(gè)元素。
• 只在列表的首尾添加元素。

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

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

10.3 LinkedList不是線程安全的

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

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

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

• LinkedList 繼承了 AbstractSequentialList 類(lèi)。

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

• LinkedList 繼承了 AbstractQueue抽象類(lèi)，具有隊(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 接口，即可支持序列化，能通過(guò)序列化去傳輸。

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

11.1 理解ConcurrentLinkedQueue

• ConcurrentLinked是由鏈表結(jié)構(gòu)組成的線程安全的先進(jìn)先出無(wú)界隊(duì)列。
• 當(dāng)多線程要共享訪問(wèn)集合時(shí)，ConcurrentLinkedQueue是一個(gè)比較好的選擇。
• 不允許插入null元素
• 支持非阻塞地訪問(wèn)并發(fā)安全的隊(duì)列，不會(huì)拋出ConcurrentModifiationException異常。
• size方法不是準(zhǔn)確的，因?yàn)樵诮y(tǒng)計(jì)集合的時(shí)候，隊(duì)列可能正在添加元素，導(dǎo)致統(tǒng)計(jì)不準(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類(lèi)繼承了哪些類(lèi)？

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

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

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

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

12.1 理解ArrayDeque

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

12.2 使用方法

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

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

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

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

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

13.1 理解ConcurrentLinkedDeque類(lèi)

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

13.2 ConcurrentLinkedDeque使用示例

創(chuàng)建兩個(gè)積木：三角形、四邊形，然后添加到隊(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類(lèi)

14.1 理解ArrayBlockingQueue

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

14.2 ArrayBlockingQueue使用示例

創(chuàng)建兩個(gè)積木：三角形、四邊形，然后添加到隊(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類(lèi)

15.1 理解LinkedBlockingQueue

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

15.2 LinkedBlockingQueue使用示例

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

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

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

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

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

十六、雙向阻塞LinkedBlockingDeque類(lèi)

16.1 理解LinkedBlockingDeque類(lèi)

• 由鏈LinkedBlockingDeque = 阻塞隊(duì)列+鏈表+雙端訪問(wèn)
• 線程安全。
• 多線程同時(shí)入隊(duì)時(shí)，因多了一端訪問(wèn)入口，所以減少了一半的競(jìng)爭(zhēng)。
• 默認(rèn)容量大小為Integer.MAX_VALUE。可指定容量大小。

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

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

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

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

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

十七、鏈表阻塞LinkedTransferQueue類(lèi)

17.1 理解LinkedTransferQueue類(lèi)

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

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

之前的TransferQueue也講到了3個(gè)案例來(lái)說(shuō)明TransferQueue的原理，大家可以回看TransferQueue。

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

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

17.3 LinkedTransferQueue代碼示例

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

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

• 消費(fèi)者依次從隊(duì)列首部開(kāi)始消費(fèi)元素，每次消費(fèi)前，先sleep 2s，來(lái)演示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方法來(lái)傳輸A和D，發(fā)現(xiàn)沒(méi)有消費(fèi)者線程接收，所以被阻塞。

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

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

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

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

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

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

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

十八、傳球好手SynchronousQueue類(lèi)

18.1 理解SynchronousQueue類(lèi)

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

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

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

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

• 適合傳遞性場(chǎng)景。

• 性能高于ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

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

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

• 消費(fèi)線程使用take來(lái)消費(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é)：說(shuō)明生產(chǎn)線程執(zhí)行put第一個(gè)元素"A" 操作后，需要等待消費(fèi)者線程take完“A”后，才能繼續(xù)往下執(zhí)行代碼。

18.1 SynchronousQueue應(yīng)用場(chǎng)景

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

18.2 SynchronousQueue和LinkedTransferQueue的區(qū)別

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

十九、優(yōu)先級(jí)阻塞PriorityBlockingQueue類(lèi)

19.1 理解PriorityBlockQueue類(lèi)

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

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

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

二十、延時(shí)阻塞DelayQueue類(lèi)

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)建元素時(shí)，可以指定多久可以從隊(duì)列中獲取到當(dāng)前元素。只有在延時(shí)期滿才能從隊(duì)列中獲取到當(dāng)前元素。

20.2 源碼解析

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

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

• 獲取元素的方法poll需要等待延時(shí)時(shí)間過(guò)了才能獲取到元素

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

20.3 應(yīng)用場(chǎng)景

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

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

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

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

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