詳解 18 種佇列，你知道幾種？

語言: CN / TW / HK
時間 2021-10-28 12:33:18

本篇主要內容如下：

本篇主要內容

幫你總結好的阻塞佇列：

18種Queue總結

一、Queue自我介紹

佇列原理圖

1.1 Queue自我介紹

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

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

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

1.2 現實生活中的場景

  • 海底撈排號等位（先排號的優先進餐廳）

  • 郵政員寄送信件（信箱是佇列）

1.3 計算機世界中的場景

  • 訊息佇列 RabbitMQ

  • UDP協議（接收端將訊息存放在佇列中，從佇列中讀取資料）

二、高屋建瓴，縱覽全域性

18種佇列分為三大類：介面、抽象類、普通類。

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

18個Queue的繼承實現關係圖
  • 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組方法，每一組方法對應兩個方法。如下圖所示：

Queue的核心方法
動作 拋異常 返回特殊值
Insert add(e) offer(e)
Remove remove() poll
Examine element() peek()

  • （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介面的原理

雙端佇列Deque

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

（2）Deque方法說明：

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操作的骨架實現。

AbstractQueue的方法

方法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個核心方法總結如下：

BlockingQueue介面的10個核心方法

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

  • 插入有四種方法：add、offer、put、offer超時版。

    • IllegalStateException - 佇列滿了
    • ClassCastException - 新增的元素型別不匹配
    • NullPointerException - 新增的元素為null
    • IllegalArgumentException - 新增的元素某些屬性不匹配

    • add方法特別之處用於新增失敗時丟擲異常，共有四種異常：

    • offer方法特別之處用於新增失敗時只返回false

    • put方法特別之處用於當阻塞佇列滿時，生產者如果往佇列裡put元素，則佇列會一直阻塞生產者執行緒，直到佇列可用或者響應中斷退出

    • offer超時方法特別之處用於當阻塞佇列滿時，生產者如果往佇列裡面插入元素，佇列會阻塞生產者執行緒一段時間，如果超過了指定時間，生產者執行緒會退出，並返回false。

  • 移除有四種方法：remove、poll、take、poll超時版

    • NoSuchElementException - 如果這個佇列是空的

    • remove方法特別之處用於移除失敗時丟擲異常

    • 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操作被阻塞

BlockingDeque滿了

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

BlockQueue為空

7.2 BlockingDeque介面方法

是阻塞佇列 BlockingQueue 和雙向佇列 Deque 介面的結合。有如下方法：

BlockingDeque介面方法

示例：

嘗試執行以下方法：

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的對等方法

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)

    原理如下圖所示：

    transfer方法的原理

    • 原理圖解釋：生產者執行緒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()

  • 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介面，所以是一種雙鏈表結構，可以當作堆疊、佇列、雙向佇列使用。

  • 一個雙向列表的每一個元素都有三個整數值：元素、向後的節點連結、向前的節點連結

LinkedList的結構

我們來看下節點類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

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類

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類

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

ArrayBlockingQueuey原理圖

  • 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原理

  • 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原理圖

  • 由鏈LinkedBlockingDeque = 阻塞佇列+連結串列+雙端訪問

  • 執行緒安全。

  • 多執行緒同時入隊時，因多了一端訪問入口，所以減少了一半的競爭。

  • 預設容量大小為Integer.MAX_VALUE。可指定容量大小。

16.2 LinkedBlockingDeque的應用場景

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

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

16.3 LinkedBlockingDeque實現了哪些介面

  • LinkedBlockingDeque繼承了 BlockingDeque類，可作為阻塞佇列使用

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

  • LinkedBlockingDeque實現了 java.io.Serializable 介面，即可支援序列化，能通過序列化去傳輸。

十七、連結串列阻塞LinkedTransferQueue類

17.1 理解LinkedTransferQueue類

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

生產者1 依次往佇列中新增 A、B、C

  • 生產者2 依次往佇列中新增 D、E、F

生產者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負責把生產者產生的資料傳遞給消費者執行緒。

  • SynchronousQueue本身不儲存資料，呼叫了put方法後，佇列裡面也是空的。

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

  • 適合傳遞性場景。

  • 效能高於ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

我們建立了兩個執行緒，一個執行緒用於生產，一個執行緒用於消費

  • 生產的執行緒依次put A、B、C三個值

生產的執行緒依次put A、B、C三個值

  • 消費執行緒使用take來消費阻塞佇列中的內容，每次消費前，等待5秒

消費執行緒每隔5s呼叫take方法

  • 執行結果

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

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

18.2 SynchronousQueue和LinkedTransferQueue的區別

  • SynchronousQueue 不儲存元素，而LinkedTransferQueue儲存元素。

  • SynchronousQueue 佇列裡面沒有元素，而LinkedTransferQueue可以有多個儲存在佇列等待傳輸。

  • LinkedTransferQueue還支援若傳輸不了，則丟到佇列裡面去。

  • LinkedTransferQueue還支援若超過一定時間傳輸不了，則丟到佇列裡面去。

十九、優先順序阻塞PriorityBlockingQueue類

19.1 理解PriorityBlockQueue類

PriorityBlockQueue的原理圖

  • PriorityBlockQueue = PriorityQueue + BlockingQueue

  • 之前我們也講到了PriorityQueue的原理，支援對元素排序。

  • 元素預設自然排序。

  • 可以自定義CompareTo()方法來指定元素排序規則。

  • 可以通過建構函式構造引數Comparator來對元素進行排序。

19.2 PriorityBlockQueue實現了哪些介面

  • LinkedBlockingQueue繼承了 BlockingQueue介面，可作為阻塞佇列使用

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

  • LinkedBlockingQueue實現了 java.io.Serializable 介面，即可支援序列化，能通過序列化去傳輸。

二十、延時阻塞DelayQueue類

20.1 理解DelayQueue

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();
poll方法

20.3 應用場景

  • 快取系統的設計：可以用DelayQueue儲存快取元素的有效期。然後用一個執行緒迴圈的查詢DelayQueue佇列，一旦能從DelayQueue中獲取元素時，表示快取有效期到了。

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

20.4 DelayQueue實現了哪些介面

  • DelayQueue實現了 BlockingQueue介面，可作為阻塞佇列使用

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

- END -

點亮，伺服器三年不宕機

「」
「」