什么是阻塞隊(duì)列
阻塞隊(duì)列有兩個(gè)特點(diǎn)：
- 當(dāng)隊(duì)列中沒(méi)有元素時(shí)，從隊(duì)列中獲取元素會(huì)被阻塞
- 當(dāng)隊(duì)列滿了時(shí)衔彻，添加元素會(huì)被阻塞
阻塞隊(duì)列常用于生產(chǎn)者和消費(fèi)者的場(chǎng)景薇宠，生產(chǎn)者是向隊(duì)列里添加元素，消費(fèi)者則從隊(duì)列里取元素艰额。
隊(duì)列Queue接口核心方法
阻塞隊(duì)列澄港，本質(zhì)上來(lái)說(shuō)還是屬于隊(duì)列，也就是說(shuō)阻塞隊(duì)列繼承了隊(duì)列的功能柄沮，這里我們先來(lái)看看Queue接口中的幾個(gè)核心方法：
| 方法 | 功能 |
|---|---|
| add(e) | 添加一個(gè)元素回梧，成功返回true，如果空間滿了則拋出異常 |
| offer(e) | 添加一個(gè)元素祖搓，成功返回true狱意，如果空間滿了則返回false,處理有界隊(duì)列時(shí)優(yōu)于add方法 |
| remove() | 檢索并移除隊(duì)列頭元素，成功則返回移除的元素拯欧，如果隊(duì)列為空則拋出異常 |
| poll() | 檢索并移除隊(duì)列頭元素详囤，成功則返回移除的元素，如果隊(duì)列為空則返回null |
| element() | 檢索并返回隊(duì)列頭元素镐作，如果隊(duì)列為空則拋出異常 |
| peek() | 檢索并返回隊(duì)列頭元素藏姐，如果位列為空則返回null |
這幾個(gè)方法是隊(duì)列接口所提供的蚓再，然而這些方法并不會(huì)阻塞，所以需要重新定義阻塞隊(duì)列的接口包各，下面我們看看阻塞隊(duì)列中的核心方法摘仅。
阻塞隊(duì)列BlockigQueue接口核心方法
| 方法 | 功能 |
|---|---|
| put(e) | 添加一個(gè)元素，成功返回true问畅，如果空間滿了則阻塞等待 |
| offer(e,time,unit) | 添加一個(gè)元素娃属，成功返回true，如果空間滿了則阻塞指定時(shí)間护姆，到達(dá)指定時(shí)間還沒(méi)空間則返回null |
| take() | 檢索并移除隊(duì)列頭元素矾端，成功則返回移除的元素，如果隊(duì)列為空則阻塞 |
| poll(time,unit) | 檢索并移除隊(duì)列頭元素卵皂，成功則返回移除的元素秩铆，如果隊(duì)列為空則阻塞指定時(shí)間，到達(dá)指定時(shí)間后隊(duì)列還是空則返回null |
| drainTo(Collection) | 一次性獲取隊(duì)列所有元素放到指定的集合中灯变，并返回轉(zhuǎn)移個(gè)數(shù) |
| drainTo(c,n) | 一次性獲取隊(duì)列中指定個(gè)數(shù)的元素放到指定的集合中殴玛，并返回轉(zhuǎn)移個(gè)數(shù) |
| remainingCapacity() | 返回隊(duì)列中理想情況下可添加元素個(gè)數(shù) |
在Java中，提供了7種常用的阻塞隊(duì)列添祸。
- ArrayBlockingQueue：由數(shù)組結(jié)構(gòu)組成的有界阻塞隊(duì)列
- LinkedBlockingQueue：由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列
- PriorityBlockingQueue：支持優(yōu)先級(jí)排序的無(wú)界阻塞隊(duì)列
- DelayQueue：使用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)的無(wú)界阻塞隊(duì)列
- SynchronousQueue：不存儲(chǔ)元素的阻塞隊(duì)列
- LinkedTransferQueue：由鏈表結(jié)構(gòu)組成的無(wú)界阻塞隊(duì)列
- LinkedBlockingDeque：由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列
ArrayBlockingQueue
ArrayBlockingQueue是一個(gè)用數(shù)組實(shí)現(xiàn)的有界阻塞隊(duì)列滚粟。此隊(duì)列按照先進(jìn)先出（FIFO）的原則對(duì)元素進(jìn)行排序。默認(rèn)情況下采用非公平鎖的方式實(shí)現(xiàn)刃泌，可以通過(guò)構(gòu)造器傳參控制是采用公平鎖還是非公平鎖實(shí)現(xiàn)凡壤。先看看ArrayBlockingQueue類圖關(guān)系：
可以看到有3個(gè)構(gòu)造器，其實(shí)最終都是會(huì)調(diào)用上圖中第二個(gè)構(gòu)造器進(jìn)行初始化,第三個(gè)構(gòu)造器在初始化之后會(huì)再進(jìn)行賦值(如果傳入的Collection不為空)耙替。
ArrayBlockingQueue nonFairQueue = new ArrayBlockingQueue(10);//默認(rèn)非公平鎖實(shí)現(xiàn)
ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(10,true);//true表示公平鎖
模擬實(shí)現(xiàn)生產(chǎn)者消費(fèi)者
package com.zwx.concurrent.queue.block;
import java.util.concurrent.ArrayBlockingQueue;
public class ArrayBlockingQueueDemo {
public static void main(String[] args) throws InterruptedException {
ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue(100);//默認(rèn)非公平鎖實(shí)現(xiàn)
new Thread(new ConsumerThread(queue)).start();
Thread.sleep(2000);
new Thread(new ProcuctThread(queue)).start();
}
}
class ProcuctThread extends Thread{
private ArrayBlockingQueue queue;
public ProcuctThread(ArrayBlockingQueue queue) {
this.queue = queue;
}
@Override
public void run() {
for (int i=0;i<100;i++){
try {
queue.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class ConsumerThread extends Thread{
private ArrayBlockingQueue queue;
public ConsumerThread(ArrayBlockingQueue queue) {
this.queue = queue;
}
@Override
public void run() {
while (true){
try {
int a = (int)queue.take();
System.out.println("消費(fèi)：" + a);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
上面的示例中亚侠，我們先啟動(dòng)了消費(fèi)者模式，運(yùn)行之后可以發(fā)現(xiàn)俗扇，因?yàn)殛?duì)列是空的硝烂，所以會(huì)阻塞等待生產(chǎn)者添加元素之后輸出。
初始化隊(duì)列
首先是初始化兩個(gè)Condition隊(duì)列分別用于阻塞生產(chǎn)者和消費(fèi)者線程狐援，關(guān)于Condition隊(duì)列钢坦，想詳細(xì)了解的可以點(diǎn)擊這里。
添加元素(生產(chǎn)者)
添加元素的時(shí)候啥酱，如果隊(duì)列滿了爹凹，就阻塞，不滿則調(diào)用enque方法添加元素
獲取元素時(shí)通過(guò)內(nèi)部維護(hù)的putIndex逐個(gè)往后添加元素镶殷，滿了則重新從0開(kāi)始
獲取元素(消費(fèi)者)
首先會(huì)判斷隊(duì)列是不是空了禾酱，空了就阻塞，否則調(diào)用dequeue方法獲取元素
調(diào)用dequeue方法移除元素，并喚醒添加元素線程颤陶。
LinkedBlockingQueue
一個(gè)由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列,此隊(duì)列按照先進(jìn)先出（FIFO）的原則對(duì)元素進(jìn)行排序颗管，和ArrayBlockingQueue的區(qū)別是ArrayBlockingQueue內(nèi)部維護(hù)的是一個(gè)數(shù)組，通過(guò)數(shù)組下標(biāo)來(lái)維護(hù)隊(duì)列滓走，而LinkedBlockingQueue維護(hù)的是一個(gè)鏈表垦江，通過(guò)Node來(lái)維護(hù)隊(duì)列。還是先來(lái)看看類圖關(guān)系：
LinkedBlockingQueue依然有3個(gè)構(gòu)造函數(shù)搅方，第一個(gè)和第三個(gè)構(gòu)造器最終也是會(huì)調(diào)用第二個(gè)構(gòu)造器比吭，而且默認(rèn)會(huì)初始化一個(gè)Integer.MAX_VALUE大小隊(duì)列，第三個(gè)構(gòu)造器在初始化隊(duì)列之后會(huì)進(jìn)行賦值(如果傳入的Collection不為空)姨涡。
初始化隊(duì)列
Node是LinkedBlockingQueue中的一個(gè)靜態(tài)內(nèi)部類：
所以第一次初始化之后Node節(jié)點(diǎn)中的item是默認(rèn)為null值的衩藤。初始化之后得到如下隊(duì)列：
這個(gè)頭節(jié)點(diǎn)也是一個(gè)哨兵，和AQS同步隊(duì)列一樣涛漂，設(shè)置了一個(gè)空信息的節(jié)點(diǎn)作為哨兵赏表。
添加元素(生產(chǎn)者)
添加元素獲取的是putLock，后面可以看到匈仗，獲取元素獲取的的takeLock瓢剿，采用了讀寫雙鎖分離方式實(shí)現(xiàn)性能上的提升。
再看下添加元素的enqueue方法：
添加元素后得到如下隊(duì)列：
獲取元素(消費(fèi)者)
這里消費(fèi)者獲取的是另一把鎖takeLock锚沸，這里的邏輯也應(yīng)該是比較容易看懂跋选，我們進(jìn)入真正獲取元素的dequeue方法：
1、我們先看219行哗蜈，執(zhí)行之后得到如下隊(duì)列：
2、繼續(xù)看221行代碼坠韩，執(zhí)行之后得到如下結(jié)果：
經(jīng)過(guò)這兩步距潘，其實(shí)原先的E1節(jié)點(diǎn)已經(jīng)被移除了，那么從上圖可以看到只搁，原先舊的head節(jié)點(diǎn)中next還持有了當(dāng)前head節(jié)點(diǎn)的引用音比，這時(shí)候根據(jù)GC的可達(dá)性算法，是無(wú)法回收的氢惋，所以需要將next的引用去掉(也就是上面218行代碼的作用)洞翩，這樣Node節(jié)點(diǎn)就沒(méi)有持有其他對(duì)象的引用了，GC就可以將其當(dāng)做垃圾回收掉焰望，這個(gè)和之前在AQS同步隊(duì)列以及Condition隊(duì)列中做法是一個(gè)意思骚亿，都是為了取消其引用，方便GC熊赖。
LinkedBlockingDeque
LinkedBlockingDeque是和LinkedBlockingQeque一樣均是由鏈表結(jié)構(gòu)組成来屠，也就是說(shuō)內(nèi)部都是通過(guò)一個(gè)Node內(nèi)部類來(lái)實(shí)現(xiàn)聊表，而LinkedBlockingDeque是雙向的阻塞隊(duì)列，故而Node中肯定會(huì)比單向的多了一個(gè)prev指向前一個(gè)節(jié)點(diǎn)俱笛。
雙向隊(duì)列因?yàn)槎嗔艘粋€(gè)操作隊(duì)列的入口捆姜，所以相比較于LinkedBlockingQeque單向隊(duì)列中多了addFirst、 addLast迎膜、offerFirst泥技、offerLast、peekFirst和peekLast等方法磕仅。另外零抬，插入方法add等同于addLast，移除方法remove等效于removeFirst宽涌，而take方法卻等同于takeFirst平夜，這些事實(shí)需要注意的，為了避免混亂卸亮，建議使用的時(shí)候還是帶上First和Last關(guān)鍵字忽妒。
首先還是來(lái)看一看類圖：
可以看出相比較于單項(xiàng)隊(duì)列，多了一個(gè)Deque(雙向)接口兼贸，構(gòu)造器和單向列表一樣段直，也是提供了3個(gè)。
初始化隊(duì)列
這里可以看到溶诞，初始化的時(shí)候沒(méi)有設(shè)置任何節(jié)點(diǎn)鸯檬，僅僅只是設(shè)置了一個(gè)容量。
添加元素(生產(chǎn)者)
從First添加
這里基本沒(méi)有邏輯螺垢，主要看linkFirst(Node)方法：
從Last添加
這個(gè)方法也是一樣沒(méi)有邏輯喧务，主要看linkLast(Node)方法：
獲取元素(消費(fèi)者)
從First獲取
繼續(xù)看unlinkFirst這個(gè)方法：
這些邏輯和上面的單向隊(duì)列是差不多的，只是多了一個(gè)prev指向
從Last獲取
繼續(xù)看unlinkLast()方法：
總結(jié)
本文主要講述了Java提供的7種隊(duì)列中的其中三種隊(duì)列枉圃，這三種隊(duì)列實(shí)現(xiàn)方式比較接近功茴，而且源碼比較容易理解。
