1唁桩、簡介
Queue（隊列）：一種特殊的線性表号杠，它只允許在表的前端（front）進(jìn)行刪除操作蚪腋，只允許在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊尾姨蟋，進(jìn)行刪除操作的端稱為隊頭屉凯。
每個元素總是從隊列的rear端進(jìn)入隊列，然后等待該元素之前的所有元素出隊之后眼溶，當(dāng)前元素才能出對神得，遵循先進(jìn)先出（FIFO）原則。
下面是Queue類的繼承關(guān)系圖：
圖中我們可以看到偷仿，最上層是Collection接口哩簿，Queue滿足集合類的所有方法：
- add(E e)：增加元素；
- remove(Object o)：刪除元素酝静；
- clear()：清除集合中所有元素节榜；
- size()：集合元素的大小别智；
- isEmpty()：集合是否沒有元素宗苍；
- contains(Object o)：集合是否包含元素o。
2薄榛、隊列
2.1讳窟、Queue
Queue：隊列的上層接口，提供了插入敞恋、刪除丽啡、獲取元素這3種類型的方法，而且對每一種類型都提供了兩種方式硬猫，先來看看插入方法：
- add(E e)：插入元素到隊尾补箍，插入成功返回true改执，沒有可用空間拋出異常 IllegalStateException。
- offer(E e)： 插入元素到隊尾坑雅，插入成功返回true辈挂，否則返回false。
add和offer作為插入方法的唯一不同就在于隊列滿了之后的處理方式裹粤。add拋出異常终蒂，而offer返回false。
再來看看刪除和獲取元素方法（和插入方法類似）：
- remove()：獲取并移除隊首的元素遥诉，該方法和poll方法的不同之處在于后豫，如果隊列為空該方法會拋出異常，而poll不會突那。
- poll()：獲取并移除隊首的元素挫酿，如果隊列為空，返回null愕难。
- element()：獲取隊列首的元素早龟，該方法和peek方法的不同之處在于，如果隊列為空該方法會拋出異常猫缭，而peek不會葱弟。
- peek()：獲取隊列首的元素，如果隊列為空猜丹，返回null芝加。
如果隊列是空，remove和element方法會拋出異常射窒，而poll和peek返回null藏杖。
當(dāng)然，Queue只是單向隊列脉顿，為了提供更強大的功能蝌麸，JDK在1.6的時候新增了一個雙向隊列Deque，用來實現(xiàn)更靈活的隊列操作艾疟。
2.2来吩、Deque
Deque在Queue的基礎(chǔ)上，增加了以下幾個方法：
- addFirst(E e)：在前端插入元素蔽莱，異常處理和add一樣弟疆；
- addLast(E e)：在后端插入元素，和add一樣的效果盗冷；
- offerFirst(E e)：在前端插入元素怠苔，異常處理和offer一樣；
- offerLast(E e)：在后端插入元素正塌，和offer一樣的效果嘀略；
- removeFirst()：移除前端的一個元素，異常處理和remove一樣乓诽；
- removeLast()：移除后端的一個元素帜羊，和remove一樣的效果；
- pollFirst()：移除前端的一個元素鸠天，和poll一樣的效果讼育；
- pollLast()：移除后端的一個元素，異常處理和poll一樣稠集；
- getFirst()：獲取前端的一個元素奶段，和element一樣的效果；
- getLast()：獲取后端的一個元素剥纷，異常處理和element一樣痹籍；
- peekFirst()：獲取前端的一個元素，和peek一樣的效果晦鞋；
- peekLast()：獲取后端的一個元素蹲缠，異常處理和peek一樣；
- removeFirstOccurrence(Object o)：從前端開始移除第一個是o的元素悠垛；
- removeLastOccurrence(Object o)：從后端開始移除第一個是o的元素线定；
- push(E e)：和addFirst一樣的效果；
- pop()：和removeFirst一樣的效果确买。
可以發(fā)現(xiàn)斤讥，其實很多方法的效果都是一樣的，只不過名字不同湾趾。比如Deque為了實現(xiàn)Stack的語義芭商，定義了push和pop兩個方法。
3搀缠、阻塞隊列
3.1蓉坎、BlockingQueue
BlockingQueue（阻塞隊列），在Queue的基礎(chǔ)上實現(xiàn)了阻塞等待的功能胡嘿。它是JDK 1.5中加入的接口蛉艾，它是指這樣的一個隊列：當(dāng)生產(chǎn)者向隊列添加元素但隊列已滿時，生產(chǎn)者會被阻塞衷敌；當(dāng)消費者從隊列移除元素但隊列為空時勿侯，消費者會被阻塞。
先給出BlockingQueue新增的方法：
- put(E e)：向隊尾插入元素缴罗。如果隊列滿了助琐，阻塞等待，直到被中斷為止面氓。
- boolean offer(E e, long timeout, TimeUnit unit)：向隊尾插入元素兵钮。如果隊列滿了蛆橡，阻塞等待timeout個時長，如果到了超時時間還沒有空間掘譬，拋棄該元素泰演。
- take()：獲取并移除隊首的元素。如果隊列為空葱轩，阻塞等待睦焕，直到被中斷為止。
- poll(long timeout, TimeUnit unit)：獲取并移除隊首的元素靴拱。如果隊列為空垃喊，阻塞等待timeout個時長，如果到了超時時間還沒有元素袜炕，則返回null本谜。
- remainingCapacity()：返回在無阻塞的理想情況下（不存在內(nèi)存或資源約束）此隊列能接受的元素數(shù)量，如果該隊列是無界隊列偎窘，返回Integer.MAX_VALUE耕突。
- drainTo(Collection<? super E> c)：移除此隊列中所有可用的元素，并將它們添加到給定 collection 中评架。
- drainTo(Collection<? super E> c, int maxElements)：最多從此隊列中移除給定數(shù)量的可用元素眷茁，并將這些元素添加到給定 collection 中。
BlockingQueue最重要的也就是關(guān)于阻塞等待的幾個方法纵诞，而這幾個方法正好可以用來實現(xiàn)生產(chǎn)-消費的模型上祈。
從圖中我們可以知道實現(xiàn)了BlockingQueue的類有以下幾個：
- ArrayBlockingQueue：一個由數(shù)組結(jié)構(gòu)組成的有界阻塞隊列。
- LinkedBlockingQueue：一個由鏈表結(jié)構(gòu)組成的有界阻塞隊列浙芙。
- PriorityBlockingQueue：一個支持優(yōu)先級排序的無界阻塞隊列登刺。
- SynchronousQueue：一個不存儲元素的阻塞隊列。
- DelayQueue：一個使用優(yōu)先級隊列實現(xiàn)的無界阻塞隊列嗡呼。
ArrayBlockingQueue
ArrayBlockingQueue是一個用數(shù)組實現(xiàn)的有界阻塞隊列纸俭。此隊列按照先進(jìn)先出（FIFO）的原則對元素進(jìn)行排序。默認(rèn)情況下不保證訪問者公平的訪問隊列南窗，所謂公平訪問隊列是指阻塞的所有生產(chǎn)者線程或消費者線程揍很，當(dāng)隊列可用時，可以按照阻塞的先后順序訪問隊列万伤，即先阻塞的生產(chǎn)者線程窒悔，可以先往隊列里插入元素，先阻塞的消費者線程敌买，可以先從隊列里獲取元素简珠。通常情況下為了保證公平性會降低吞吐量。我們可以使用以下代碼創(chuàng)建一個公平的阻塞隊列：
ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(1000, true);
訪問者的公平性是使用可重入鎖實現(xiàn)的虹钮，代碼如下：
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();
}
LinkedBlockingQueue
LinkedBlockingQueue是一個用鏈表實現(xiàn)的有界阻塞隊列聋庵。此隊列的默認(rèn)和最大長度為Integer.MAX_VALUE膘融。此隊列按照先進(jìn)先出的原則對元素進(jìn)行排序。
PriorityBlockingQueue
PriorityBlockingQueue是一個支持優(yōu)先級的無界隊列祭玉。默認(rèn)情況下元素采取自然順序排列氧映，也可以通過比較器comparator來指定元素的排序規(guī)則。元素按照升序排列攘宙。
SynchronousQueue
SynchronousQueue是一個不存儲元素的阻塞隊列屯耸。每一個put操作必須等待一個take操作拐迁，否則不能繼續(xù)添加元素蹭劈。SynchronousQueue可以看成是一個傳球手，負(fù)責(zé)把生產(chǎn)者線程處理的數(shù)據(jù)直接傳遞給消費者線程线召。隊列本身并不存儲任何元素铺韧，非常適合于傳遞性場景,比如在一個線程中使用的數(shù)據(jù)，傳遞給另外一個線程使用缓淹，SynchronousQueue的吞吐量高于LinkedBlockingQueue 和 ArrayBlockingQueue哈打。
DelayQueue
DelayQueue是一個支持延時獲取元素的無界阻塞隊列。隊列使用PriorityQueue來實現(xiàn)讯壶。隊列中的元素必須實現(xiàn)Delayed接口料仗，在創(chuàng)建元素時可以指定多久才能從隊列中獲取當(dāng)前元素。只有在延遲期滿時才能從隊列中提取元素伏蚊。我們可以將DelayQueue運用在以下應(yīng)用場景：
- 緩存系統(tǒng)的設(shè)計：可以用DelayQueue保存緩存元素的有效期立轧，使用一個線程循環(huán)查詢DelayQueue，一旦能從DelayQueue中獲取元素時躏吊，表示緩存有效期到了氛改。
- 定時任務(wù)調(diào)度。使用DelayQueue保存當(dāng)天將會執(zhí)行的任務(wù)和執(zhí)行時間比伏，一旦從DelayQueue中獲取到任務(wù)就開始執(zhí)行胜卤，從比如TimerQueue就是使用DelayQueue實現(xiàn)的。
3.2赁项、BlockingDeque
BlockingDeque（阻塞雙端隊列）在Deque的基礎(chǔ)上實現(xiàn)了雙端阻塞等待的功能葛躏。和第2節(jié)說的類似，BlockingDeque也提供了雙端隊列該有的阻塞等待方法：
- putFirst(E e)：在隊首插入元素悠菜，如果隊列滿了紫新，阻塞等待，直到被中斷為止李剖。
- putLast(E e)：在隊尾插入元素芒率，如果隊列滿了，阻塞等待篙顺，直到被中斷為止偶芍。
- offerFirst(E e, long timeout, TimeUnit unit)：向隊首插入元素充择。如果隊列滿了，阻塞等待timeout個時長匪蟀，如果到了超時時間還沒有空間椎麦，拋棄該元素。
- offerLast(E e, long timeout, TimeUnit unit)：向隊尾插入元素材彪。如果隊列滿了观挎，阻塞等待timeout個時長，如果到了超時時間還沒有空間段化，拋棄該元素嘁捷。
- takeFirst()：獲取并移除隊首的元素。如果隊列為空显熏，阻塞等待雄嚣，直到被中斷為止。
- takeLast()：獲取并移除隊尾的元素喘蟆。如果隊列為空缓升，阻塞等待，直到被中斷為止蕴轨。
- pollFirst(long timeout, TimeUnit unit)：獲取并移除隊首的元素港谊。如果隊列為空，阻塞等待timeout個時長橙弱，如果到了超時時間還沒有元素歧寺，則返回null。
- pollLast(long timeout, TimeUnit unit)：獲取并移除隊尾的元素膘螟。如果隊列為空成福，阻塞等待timeout個時長，如果到了超時時間還沒有元素荆残，則返回null奴艾。
- removeFirstOccurrence(Object o)：從隊首開始移除第一個和o相等的元素。
- removeLastOccurrence(Object o)：從隊尾開始移除第一個和o相等的元素内斯。
從圖中我們可以知道實現(xiàn)了BlockingDeque的類有：
- LinkedBlockingDeque：一個由鏈表結(jié)構(gòu)組成的雙向阻塞隊列蕴潦。
3.3、TransferQueue
TransferQueue是JDK 1.7對于并發(fā)類庫新增加的一個接口俘闯，它擴(kuò)展自BlockingQueue潭苞，所以自然保持著阻塞隊列的所有特性。
有人這樣評價它：TransferQueue是是ConcurrentLinkedQueue真朗、SynchronousQueue (公平模式下)此疹、無界的LinkedBlockingQueues等的超集。
TransferQueue對比與BlockingQueue更強大的一點是，生產(chǎn)者會一直阻塞直到所添加到隊列的元素被某一個消費者所消費（不僅僅是添加到隊列里就完事）蝗碎。新添加的transfer方法用來實現(xiàn)這種約束湖笨。顧名思義，阻塞就是發(fā)生在元素從一個線程transfer到另一個線程的過程中蹦骑，它有效地實現(xiàn)了元素在線程之間的傳遞（以建立Java內(nèi)存模型中的happens-before關(guān)系的方式）慈省。
我們來看看該接口提供的標(biāo)準(zhǔn)方法：
- tryTransfer(E e)：若當(dāng)前存在一個正在等待獲取的消費者線程（使用take()或者poll()函數(shù)），使用該方法會即刻轉(zhuǎn)移/傳輸對象元素e并立即返回true眠菇；若不存在边败，則返回false，并且不進(jìn)入隊列捎废。這是一個不阻塞的操作笑窜。
- transfer(E e)：若當(dāng)前存在一個正在等待獲取的消費者線程，即立刻移交之缕坎；否則怖侦，會插入當(dāng)前元素e到隊列尾部篡悟，并且等待進(jìn)入阻塞狀態(tài)谜叹，到有消費者線程取走該元素。
- tryTransfer(E e, long timeout, TimeUnit unit)：若當(dāng)前存在一個正在等待獲取的消費者線程搬葬，會立即傳輸給它;否則將插入元素e到隊列尾部荷腊，并且等待被消費者線程獲取消費掉；若在指定的時間內(nèi)元素e無法被消費者線程獲取急凰，則返回false女仰，同時該元素被移除。
- hasWaitingConsumer()：判斷是否存在消費者線程抡锈。
- getWaitingConsumerCount()：獲取所有等待獲取元素的消費線程數(shù)量疾忍。
其實transfer方法在SynchronousQueue的實現(xiàn)中就已存在了,只是沒有做為API暴露出來。SynchronousQueue有一個特性:它本身不存在容量,只能進(jìn)行線程之間的元素傳送床三。SynchronousQueue在執(zhí)行offer操作時一罩，如果沒有其他線程執(zhí)行poll，則直接返回false.線程之間元素傳送正是通過transfer方法完成的撇簿。
TransferQueue相比SynchronousQueue用處更廣聂渊、更好用，因為你可以決定是使用BlockingQueue的方法（例如put方法）還是確保一次傳遞完成（即transfer方法）四瘫。在隊列中已有元素的情況下汉嗽，調(diào)用transfer方法，可以確保隊列中被傳遞元素之前的所有元素都能被處理找蜜。
從圖中我們可以知道實現(xiàn)了TransferQueue的類有：
- LinkedTransferQueue：一個由鏈表結(jié)構(gòu)組成的無界阻塞隊列饼暑。
好了，隊列的API先說到這里，下面我會另起一文重點說說阻塞隊列的那些個實現(xiàn)類的原理弓叛。
轉(zhuǎn)自 http://benjaminwhx.com/2018/05/05/%E8%AF%B4%E8%AF%B4%E9%98%9F%E5%88%97Queue/
