xylz,imxylz

在Set中有一個排序的集合SortedSet，用來保存按照自然順序排列的對象。Queue中同樣引入了一個支持排序的FIFO模型。

并發隊列與Queue簡介 中介紹了，PriorityQueue和PriorityBlockingQueue就是支持排序的Queue。顯然一個支持阻塞的排序Queue要比一個非線程安全的Queue實現起來要復雜的多，因此下面只介紹PriorityBlockingQueue，至于PriorityQueue只需要去掉Blocking功能就基本相同了。

排序的BlockingQueue — PriorityBlockingQueue

先簡單介紹下PriorityQueue，因為PriorityBlockingQueue內部就是通過PriorityQueue適配實現的，只不過通過鎖進行同步和阻塞而已。

PriorityQueue是一個數組實現的，是一個二叉樹的實現，這個二叉樹的任意一個節點都比其子節點要小，這樣頂點就是最小的節點。每一個元素或者節點要么本身是可比較的（Comparable），或者隊列本身帶有一個比較器（Comparator<? super E>），所有元素就是靠比較自身的大小來確定順序的。而數組中頂點就是數組的第0個元素，因此出隊列的話總是取第0個元素。對于第0個元素，其子節點是第1個元素和第2個元素，對于第1個元素，其子元素又是第3/4個元素，以此類推，第i個元素的父節點就是(i-1)/2。這樣任意一個元素加入隊列就從其父節點(i-1)/2開始比較，一旦新節點比父節點小就交換兩個節點，然后繼續比較新節點與其新的父節點。知道所有節點都是按照父節點一定比子節點小的順序排列。這是一個有點復雜的算法，此處不再討論更多的細節。不管是刪除還是查找，我們只需要了解的頂點（索引為0的元素）總是最小的。

特別需要說明的是PriorityQueue是一個無界的隊列，也就是說一旦元素的個數達到了數組的大小，那么就將數組擴大50%，這樣這個數組就是無窮大的。當然了如果達到了整數的最大值就會得到一個OutOfMemoryError，這個是由邏輯保證的。

對于PriorityBlockingQueue而言，由于是無界的，因此就只有非空的信號，也就是說只有take()才能阻塞，put是永遠不會阻塞（除非達到Integer.MAX_VALUE直到拋出一個OutOfMemoryError異常）。

只有take()操作的時候才可能因為隊列為空而掛起。同時其它需要操作隊列變化和大小的只需要使用獨占鎖ReentrantLock就可以了，非常方便。需要說明的是PriorityBlockingQueue采用了一個公平的鎖。

總的來說PriorityBlockingQueue 不是一個FIFO的隊列，而是一個有序的隊列，這個隊列總是取“自然順序”最小的對象，同時又是一個只能出隊列阻塞的BlockingQueue，對于入隊列卻不是阻塞的。所有操作都是線程安全的。

直接交換的BlockingQueue — SynchronousQueue

這是一個很有意思的阻塞隊列，其中每個插入操作必須等待另一個線程的移除操作，同樣任何一個移除操作都等待另一個線程的插入操作。因此此隊列內部其實沒有任何一個元素，或者說容量是0，嚴格說并不是一種容器。由于隊列沒有容量，因此不能調用peek操作，因為只有移除元素時才有元素。

一個沒有容量的并發隊列有什么用了？或者說存在的意義是什么？

SynchronousQueue 的實現非常復雜，當然了如果真要去分析還是能夠得到一些經驗的，但是前面分析了過多的結構后，發現越來越陷于數據結構與算法里面了。我的初衷是通過研究并發實現的原理來更好的利用并發來最大限度的利用可用資源。所以在后面的章節中盡可能的少研究數據結構和算法，但是為了弄清楚里面的原理，必不可免的會涉及到一些這方面的知識，希望后面能夠適可而止。

再回到話題。SynchronousQueue 內部沒有容量，但是由于一個插入操作總是對應一個移除操作，反過來同樣需要滿足。那么一個元素就不會再SynchronousQueue 里面長時間停留，一旦有了插入線程和移除線程，元素很快就從插入線程移交給移除線程。也就是說這更像是一種信道（管道），資源從一個方向快速傳遞到另一方向。

需要特別說明的是，盡管元素在SynchronousQueue 內部不會“停留”，但是并不意味之SynchronousQueue 內部沒有隊列。實際上SynchronousQueue 維護者線程隊列，也就是插入線程或者移除線程在不同時存在的時候就會有線程隊列。既然有隊列，同樣就有公平性和非公平性特性，公平性保證正在等待的插入線程或者移除線程以FIFO的順序傳遞資源。

顯然這是一種快速傳遞元素的方式，也就是說在這種情況下元素總是以最快的方式從插入著（生產者）傳遞給移除著（消費者），這在多任務隊列中是最快處理任務的方式。在線程池的相關章節中還會更多的提到此特性。

事實上在《并發隊列與Queue簡介》中介紹了還有一種BlockingQueue的實現DelayQueue，它描述的是一種延時隊列。這個隊列的特性是，隊列中的元素都要延遲時間（超時時間），只有一個元素達到了延時時間才能出隊列，也就是說每次從隊列中獲取的元素總是最先到達延時的元素。這種隊列的場景就是計劃任務。比如以前要完成計劃任務，很有可能是使用Timer/TimerTask，這是一種循環檢測的方式，也就是在循環里面遍歷所有元素總是檢測元素是否滿足條件，一旦滿足條件就執行相關任務。顯然這中方式浪費了很多的檢測工作，因為大多數時間總是在進行無謂的檢測。而DelayQueue 卻能避免這種無謂的檢測。在線程池的計劃任務部分還有更加詳細的討論此隊列實現。

下面就對常見的BlockingQueue進行小節下，這里不包括雙向的隊列，盡管ConcurrentLinkedQueue不是可阻塞的Queue，但是這里還是將其放在一起進行對比。

如果不需要阻塞隊列，優先選擇ConcurrentLinkedQueue；如果需要阻塞隊列，隊列大小固定優先選擇ArrayBlockingQueue，隊列大小不固定優先選擇LinkedBlockingQueue；如果需要對隊列進行排序，選擇PriorityBlockingQueue；如果需要一個快速交換的隊列，選擇SynchronousQueue；如果需要對隊列中的元素進行延時操作，則選擇DelayQueue。