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

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

 轉自: http://www.aygfsteel.com/xylz/archive/2010/07/30/327582.htm

排序的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。