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

• 2020 年 9 月 9 日
• 筆記
• 26-Java並發, 92-JAVA, JAVA, Queue, 並發, 隊列, 集合

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

本篇主要內容如下：

幫你總結好的阻塞隊列：

一、Queue自我介紹

1.1 Queue自我介紹

hi，大家好，我的英文名叫Queue，中文名叫隊列，無論現實生活中還是計算機的世界中，我都是一個很重要的角色哦~

我是一種數據結構，大家可以把我想像成一個數組，元素從我的一頭進入、從另外一頭出去，稱為FIFO原則（先進先出原則）。

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

1.2 現實生活中的場景

• 海底撈排號等位（先排號的優先進餐廳）
• 郵政員寄送信件（信箱是隊列）

1.3 計算機世界中的場景

• 消息隊列 RabbitMQ
• UDP協議（接收端將消息存放在隊列中，從隊列中讀取數據）

二、高屋建瓴，縱覽全局

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

弄清楚下面的繼承實現關係對後面理解18種隊列有很大幫助。

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

注意：

• Deque：全稱Double-Ended queue，表示雙端隊列。
• 類實現接口，用implements
• 接口繼承接口，用 extends
• 類繼承類，用extends

三、萬物歸宗Queue接口

2.1 深入理解Queue接口的本質

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

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

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

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

• 每個Queue必須指定排序屬性。

2.2 Queue接口的核心方法

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

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

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

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

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

• （5）Queue實現類通常不允許插入null元素，儘管一些實現類比如LinkedList不禁止插入null，但是還是不建議插入null，因為null也被用在poll方法的特殊返回值，以說明隊列不包含元素。

四、雙端可用Deque接口

4.1 深入理解Deque接口的原理

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

（2）Deque方法說明：

**說明： **

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

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

• 插入操作的後一種形式專門設計用於容量限制的Deque實現，大多數實現中，插入操作不能失敗，所以可以用插入操作的後一種形式。

• Deque接口擴展了Queue接口，當使用deque作為隊列時，作為FIFO。元素將添加到deque的末尾，並從頭開始刪除。

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

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

• Deque也可以用作LIFO（後進先出）棧，這個接口優於傳統的Stack類。當作為棧使用時，元素被push到deque隊列的頭，而pop也是從隊列的頭pop出來。

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

  

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

4.1 哪些類實現了Deque接口

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

4.2 哪些類繼承了Deque接口

• BlockingDeque接口

五、隊列骨架AbstractQueue抽象類

5.1 深入理解AbstractQueue抽象類

AbstractQueue是一個抽象類，繼承了Queue接口，提供了一些Queue操作的骨架實現。

方法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（阻塞隊列）

• BlockQueue滿了，PUT操作被阻塞

• BlockQueue為空，Take操作被阻塞

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

（3）阻塞的插入：當隊列滿時，隊列會阻塞插入元素的線程，直到隊列不滿。

（4）阻塞的移除：當隊列為空，獲取元素的線程會等待隊列變為非空。

（5）應用場景：生產者和消費者，生產者線程向隊列里添加元素，消費者線程從隊列里移除元素，阻塞隊列時獲取和存放元素的容器。

（6）為什麼要用阻塞隊列：生產者生產和消費者消費的速率不一樣，需要用隊列來解決速率差問題，當隊列滿了或空的時候，則需要阻塞生產或消費動作來解決隊列滿或空的問題。

6.2 案例解析

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

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

6.3 操刀BlockingQueue接口

BlockingQueue接口的10個核心方法：

10個核心方法總結如下：

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

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

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

• 當往隊列里插入一個元素時，如果隊列不可用，那麼阻塞生產者主要通過LockSupport. park（this）來實現。
• park這個方法會阻塞當前線程，只有以下4種情況中的一種發生時，該方法才會返回。
  • 與park對應的unpark執行或已經執行時。「已經執行」是指unpark先執行，然後再執行park的情況。
  • 線程被中斷時。
  • 等待完time參數指定的毫秒數時。
  • 異常現象發生時，這個異常現象沒有任何原因。

6.5 哪些類繼承了BlockingQueue接口？

• BlockingDeque接口 – 雙端阻塞隊列
• TransferQueue接口 – 傳輸隊列

6.6 哪些類實現了BlockingQueue接口？

• ArrayBlockingQueue類 – 由數組構成的有界阻塞隊列
• LinkedBlockingQueue類 – 由鏈表構成的有界阻塞隊列，界限默認大小為Integer.MAX_Value（2^31-1），值非常大，相當於無界。
• LinkedBlockingDeque類 – 由鏈表構成的雙向阻塞隊列
• LinkedTransferQueue類 – 由鏈表構成的無界阻塞隊列
• SynchronousQueue類 – 不存儲元素的阻塞隊列，只有一個元素進行數據傳遞。
• LinkedTransferQueue類 – 由鏈表構成的無界阻塞TransferQueue隊列
• DelayQueue類 – 使用優先級隊列實現的延遲無界阻塞隊列

6.6 BlockingQueue接口繼承了哪些接口

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

七、雙端阻塞BlockingDeque接口

7.1 從原理圖上理解BlockDeque

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

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

7.2 BlockingDeque接口方法

是阻塞隊列BlockingQueue和雙向隊列Deque接口的結合。有如下方法：

示例：

嘗試執行以下方法：

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

最後隊列中的元素順序如下：

300, test1, 400。

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

7.3 BlockDeque和BlockQueue的對等方法

7.4 BlockingDeque的特點

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

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

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

7.6 哪些類實現了BlockDeque接口？

• LinkedBlockingDeque

八、使命必達TransferQueue接口

8.1 Transfer怎麼理解？

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

8.2 生活中的案例

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

8.3 TransferQueue的原理解析

• transfer(E e)

  原理如下圖所示：

  

  • 原理圖解釋：生產者線程Producer Thread嘗試將元素B傳給消費者線程，如果沒有消費者線程，則將元素B放到尾節點。並且生產者線程等待元素B被消費。當元素B被消費後，生產者線程返回。
  • 如果當前有消費者正在等待接收元素（消費者通過take方法或超時限制的poll方法時），transfer方法可以把生產者傳入的元素立刻transfer（傳輸）給消費者。
  • 如果沒有消費者等待接收元素，transfer方法會將元素放在隊列的tail（尾）節點，並等到該元素被消費者消費了才返回。

• tryTransfer(E e)

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

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

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

• getWaitingConsumerCount()

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

• hasWaitingConsumer()

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

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

• BlockingQueue接口，可作為阻塞隊列使用
• Queue接口，可作為隊列使用

8.4 哪些類實現了TransferQueue接口？

• LinkedTranferQueue接口

九、優先由你PriorityQueue類

9.1 理解PriorityQueue類

• 本應該按照升序排序

• 按照倒敘排序

• PriorityQueue是一個支持優先級的無界阻塞隊列。

• 默認自然順序升序排序。

• 可以通過構造參數Comparator來對元素進行排序。

public PriorityQueue(Comparator<? super E> comparator) {
     this(DEFAULT_INITIAL_CAPACITY, comparator);
}

• 自定義實現comapreTo()方法來指定元素排序規則。

public Comparator<? super E> comparator() {
    return comparator;
}

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

9.2 PriorityQueue類繼承了哪些類？

• AbstractQueue抽象類，具有隊列的功能

9.2 PriorityQueue類實現了哪些接口？

• Queue接口，可作為隊列使用。

十、雙向鏈表LinkedList類

10.1 LinkedList的結構

• LinkedList實現了List和Deque接口，所以是一種雙鏈表結構，可以當作堆棧、隊列、雙向隊列使用。
• 一個雙向列表的每一個元素都有三個整數值：元素、向後的節點鏈接、向前的節點鏈接

我們來看下節點類Node

private static class Node<E> {
    E item; //元素
    Node<E> next; //向後的節點鏈接
    Node<E> prev; //向前的節點鏈接

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

10.2 與ArrayList的區別

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

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

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

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

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

10.3 LinkedList不是線程安全的

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

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

10.4 LinkedList的家庭成員關係

• LinkedList 繼承了 AbstractSequentialList 類。

• LinkedList 實現了 Queue 接口，可作為隊列使用。

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

• LinkedList 實現了 List 接口，可進行列表的相關操作。

• LinkedList 實現了 Deque 接口，可作為雙向隊列使用。

• LinkedList 實現了 Cloneable 接口，可實現克隆。

• LinkedList 實現了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十一、並發安全ConcurrentLinkedQueue類

10.1 理解ConcurrentLinkedQueue

• ConcurrentLinked是由鏈表結構組成的線程安全的先進先出無界隊列。
• 當多線程要共享訪問集合時，ConcurrentLinkedQueue是一個比較好的選擇。
• 不允許插入null元素
• 支持非阻塞地訪問並發安全的隊列，不會拋出ConcurrentModifiationException異常。
• size方法不是準確的，因為在統計集合的時候，隊列可能正在添加元素，導致統計不準。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保證原子性（操作不可分割）
• 添加元素happen-before其他線程移除元素。
• 用法如下：

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

10.2 ConcurrentLinkedQueue類繼承了哪些類？

• AbstractQueue抽象類，具有隊列的功能

10.3 ConcurrentLinkedQueue類實現了哪些接口？

• Queue接口，可作為隊列使用

十二、雙向數組ArrayDeque類

12.1 理解ArrayDeque

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

12.2 使用方法

創建一個ArrayDeque，往arrayDeque隊尾添加元素。

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

12.3 ArrayDeque實現了哪些接口

• Deque接口 – 可用於雙端隊列

十三、雙向並發ConcurrentLinkedDeque類

13.1 理解ConcurrentLinkedDeque類

• 由鏈表結構組成的雙向無界阻塞隊列
• 插入、刪除和訪問操作可以並發進行，線程安全的類
• 不允許插入null元素
• 在並發場景下，計算隊列的大小是不準確的，因為計算時，可能有元素加入隊列。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保證原子性（操作不可分割）

13.2 ConcurrentLinkedDeque使用示例

創建兩個積木：三角形、四邊形，然後添加到隊列：

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

13.3 ConcurrentLinkedDeque實現了哪些接口

• Deque接口 – 可用於雙端隊列

十四、數組阻塞ArrayBlockingQueue類

14.1 理解ArrayBlockingQueue

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

14.2 ArrayBlockingQueue使用示例

創建兩個積木：三角形、四邊形，然後添加到隊列：

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實現了哪些接口

• Deque接口 – 可用於雙端隊列

十五、鏈表阻塞LinkedBlockingQueue類

15.1 理解LinkedBlockingQueue

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

15.2 LinkedBlockingQueue使用示例

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

15.3 LinkedBlockingQueue的應用場景

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

15.4 LinkedBlockingQueue實現了哪些接口

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

十六、雙向阻塞LinkedBlockingDeque類

16.1 理解LinkedBlockingDeque類

• 由鏈LinkedBlockingDeque = 阻塞隊列+鏈表+雙端訪問
• 線程安全。
• 多線程同時入隊時，因多了一端訪問入口，所以減少了一半的競爭。
• 默認容量大小為Integer.MAX_VALUE。可指定容量大小。

16.2 LinkedBlockingDeque的應用場景

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

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

16.3 LinkedBlockingDeque實現了哪些接口

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

十七、鏈表阻塞LinkedTransferQueue類

17.1 理解LinkedTransferQueue類

LinkedTransferQueue = 阻塞隊列+鏈表結構+TransferQueue

之前我們講「使命必達TransferQueue接口時已經介紹過了TransferQueue接口 ，所以LinkedTransferQueue接口跟它相似，只是加入了阻塞插入和移除的功能，以及結構是鏈表結構。

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

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

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

17.3 LinkedTransferQueue代碼示例

• 創建一個LinkedTransferQueue，生產者1 依次往隊列中添加 A、B、C

• 生產者2 依次往隊列中添加 D、E、F

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

• 運行結果

生產者1     transfer A 
生產者2     transfer D 

2s後...
  
消費者      take A
生產者1     put B 
 
2s後...
     
消費者      take D
生產者2     transfer E 
    
2s後...
  
消費者      take B
生產者1     transfer C 

• 代碼執行結果分析

（1）首先生產者線程1和2 調用transfer方法來傳輸A和D，發現沒有消費者線程接收，所以被阻塞。

（2）消費者線程過了2s後將A拿走了，然後生產者1 被釋放繼續執行，傳輸元素B，發現又沒有消費者消費，所以進行了等待。

（3）消費者線程過了2s後，將排在隊列首部的D元素拿走，生產者2繼續往下執行，傳輸元素E，發現沒有消費者，所以進行了等待。

（4）消費者線程過了2s後，將排在隊列首部的B元素拿走，生產者1傳輸C元素，等待消費者拿走。

（5）消費者不再消費了，所以生產者1和生產者2都被阻塞了，元素C和，元素E都沒有被拿走，而且生產者2的F元素還沒有開始傳輸，因為在等待元素D被拿走。

（6）看下隊列裏面確實有C和E元素，而且E排在隊列的首部。

17.4 LinkedTransferQueue實現了哪些接口

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

十八、傳球好手SynchronousQueue類

18.1 理解SynchronousQueue類

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

• SynchronousQueue負責把生產者產生的數據傳遞給消費者線程。

• SynchronousQueue本身不存儲數據，調用了put方法後，隊列裏面也是空的。

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

• 適合傳遞性場景。

• 性能高於ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

我們創建了兩個線程，一個線程用於生產，一個線程用於消費

• 生產的線程依次put A、B、C三個值

• 消費線程使用take來消費阻塞隊列中的內容，每次消費前，等待5秒

• 運行結果

t1     put A 
t2     take A 

5秒後...

t1     put B 
t2     take B 

5秒後...

t1     put C 
t2     take C 

小結：說明生產線程執行put第一個元素”A” 操作後，需要等待消費者線程take完「A」後，才能繼續往下執行代碼。

18.3 SynchronousQueue應用場景

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

18.4 SynchronousQueue和LinkedTransferQueue的區別

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

十九、優先級阻塞PriorityBlockingQueue類

19.1 理解PriorityBlockQueue類

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

19.2 PriorityBlockQueue實現了哪些接口

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

二十、延時阻塞DelayQueue類

20.1 理解DelayQueue

• DelayQueue = Delayed + BlockingQueue。隊列中的元素必須實現Delayed接口。

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

• 在創建元素時，可以指定多久可以從隊列中獲取到當前元素。只有在延時期滿才能從隊列中獲取到當前元素。

20.2 源碼解析

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

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 應用場景

• 緩存系統的設計：可以用DelayQueue保存緩存元素的有效期。然後用一個線程循環的查詢DelayQueue隊列，一旦能從DelayQueue中獲取元素時，表示緩存有效期到了。

• 定時任務調度：使用DelayQueue隊列保存當天將會執行的任務和執行時間，一旦從DelayQueue中獲取到任務就開始執行。比如Java中的TimerQueue就是使用DelayQueue實現的。

20.4 DelayQueue實現了哪些接口

• DelayQueue實現了 BlockingQueue接口，可作為阻塞隊列使用

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

我是悟空，一隻努力變強的碼農！我要變身超級賽亞人啦！

你好，我是悟空哥，7年項目開發經驗，全棧工程師，開發組長，超喜歡圖解編程底層原理。正在編寫兩本PDF，分別是 1、Spring Cloud實戰項目（佳必過），2、Java並發必知必會。我還手寫了2個小程序，Java刷題小程序，PMP刷題小程序，點擊我的公眾號菜單打開！另外有111本架構師資料以及1000道Java面試題，都整理成了PDF，可以關注公眾號 【悟空聊架構】 回復 悟空 領取優質資料。

轉發->在看->點贊->收藏->評論！！！ 是對我最大的支持！

《Java並發必知必會》系列：

1.反制面試官 | 14張原理圖 | 再也不怕被問 volatile!

2.程序員深夜慘遭老婆鄙視，原因竟是CAS原理太簡單？

3.用積木講解ABA原理 | 老婆居然又聽懂了！

4.全網最細 | 21張圖帶你領略集合的線程不安全

5.5000字 | 24張圖帶你徹底理解Java中的21種鎖

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