xylz,imxylz

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

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

排序的BlockingQueue — PriorityBlockingQueue

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

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

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

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

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

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

直接交換的BlockingQueue — SynchronousQueue

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

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

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

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

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

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

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

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

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