Java中的5大隊(duì)列,快來康康!
作者 | 王磊
來源 | Java中文社群（ID：javacn666）
本文已收錄至 https://github.com/vipstone/algorithm 《算法圖解》系列。
通過前面文章的學(xué)習(xí)《一文詳解「隊(duì)列」，手?jǐn)]隊(duì)列的3種方法！》我們知道了隊(duì)列（Queue）是先進(jìn)先出（FIFO）的，并且我們可以用數(shù)組、鏈表還有 List 的方式來實(shí)現(xiàn)自定義隊(duì)列，那么本文我們來系統(tǒng)的學(xué)習(xí)一下官方是如何實(shí)現(xiàn)隊(duì)列的。
Java 中的隊(duì)列有很多，例如：ArrayBlockingQueue、LinkedBlockingQueue、PriorityQueue、DelayQueue、SynchronousQueue 等，那它們的作用是什么？又是如何分類的呢？
其實(shí) Java 中的這些隊(duì)列可以從不同的維度進(jìn)行分類，例如可以從阻塞和非阻塞進(jìn)行分類，也可以從有界和無界進(jìn)行分類，而本文將從隊(duì)列的功能上進(jìn)行分類，例如：優(yōu)先隊(duì)列、普通隊(duì)列、雙端隊(duì)列、延遲隊(duì)列等。
雖然本文的重點(diǎn)是從功能上對(duì)隊(duì)列進(jìn)行解讀，但其它分類也是 Java 中的重要概念，所以我們先來了解一下它們。
阻塞隊(duì)列和非阻塞隊(duì)列
阻塞隊(duì)列（Blocking Queue）提供了可阻塞的 put 和 take 方法，它們與可定時(shí)的 offer 和 poll 是等價(jià)的。如果隊(duì)列滿了 put 方法會(huì)被阻塞等到有空間可用再將元素插入；如果隊(duì)列是空的，那么 take 方法也會(huì)阻塞，直到有元素可用。當(dāng)隊(duì)列永遠(yuǎn)不會(huì)被充滿時(shí)，put 方法和 take 方法就永遠(yuǎn)不會(huì)阻塞。
我們可以從隊(duì)列的名稱中知道此隊(duì)列是否為阻塞隊(duì)列，阻塞隊(duì)列中包含 BlockingQueue 關(guān)鍵字，比如以下這些：
ArrayBlockingQueue LinkedBlockingQueue PriorityBlockingQueue .......
阻塞隊(duì)列功能演示
接下來我們來演示一下當(dāng)阻塞隊(duì)列的容量滿了之后會(huì)怎樣，示例代碼如下：
import java.util.Date;
import java.util.concurrent.ArrayBlockingQueue;
public class BlockingTest {
public static void main(String[] args) throws InterruptedException {
// 創(chuàng)建一個(gè)長(zhǎng)度為 5 的阻塞隊(duì)列
ArrayBlockingQueue q1 = new ArrayBlockingQueue(5);
// 新創(chuàng)建一個(gè)線程執(zhí)行入列
new Thread(() -> {
// 循環(huán) 10 次
for (int i = 0; i < 10; i++) {
try {
q1.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(new Date() + " | ArrayBlockingQueue Size:" + q1.size());
}
System.out.println(new Date() + " | For End.");
}).start();
// 新創(chuàng)建一個(gè)線程執(zhí)行出列
new Thread(() -> {
for (int i = 0; i < 5; i++) {
try {
// 休眠 1S
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
if (!q1.isEmpty()) {
try {
q1.take(); // 出列
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
}
以上代碼的執(zhí)行結(jié)果如下：
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:1
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:2
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:3
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:4
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:13 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:14 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:15 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:16 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:17 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:17 CST 2020 | For End.
從上述結(jié)果可以看出，當(dāng) ArrayBlockingQueue 隊(duì)列滿了之后就會(huì)進(jìn)入阻塞，當(dāng)過了 1 秒有元素從隊(duì)列中移除之后，才會(huì)將新的元素入列。
非阻塞隊(duì)列
非阻塞隊(duì)列也就是普通隊(duì)列，它的名字中不會(huì)包含 BlockingQueue 關(guān)鍵字，并且它不會(huì)包含 put 和 take 方法，當(dāng)隊(duì)列滿之后如果還有新元素入列會(huì)直接返回錯(cuò)誤，并不會(huì)阻塞的等待著添加元素，如下圖所示：
非阻塞隊(duì)列的典型代表是 ConcurrentLinkedQueue 和 PriorityQueue。
有界隊(duì)列和無界隊(duì)列
有界隊(duì)列：是指有固定大小的隊(duì)列，比如設(shè)定了固定大小的 ArrayBlockingQueue，又或者大小為 0 的 SynchronousQueue。
無界隊(duì)列：指的是沒有設(shè)置固定大小的隊(duì)列，但其實(shí)如果沒有設(shè)置固定大小也是有默認(rèn)值的，只不過默認(rèn)值是 Integer.MAX_VALUE，當(dāng)然實(shí)際的使用中不會(huì)有這么大的容量（超過 Integer.MAX_VALUE），所以從使用者的角度來看相當(dāng)于 “無界”的。
按功能分類
接下來就是本文的重點(diǎn)了，我們以功能來劃分一下隊(duì)列，它可以被分為：普通隊(duì)列、優(yōu)先隊(duì)列、雙端隊(duì)列、延遲隊(duì)列、其他隊(duì)列等，接下來我們分別來看。
1.普通隊(duì)列
普通隊(duì)列（Queue）是指實(shí)現(xiàn)了先進(jìn)先出的基本隊(duì)列，例如 ArrayBlockingQueue 和 LinkedBlockingQueue，其中 ArrayBlockingQueue 是用數(shù)組實(shí)現(xiàn)的普通隊(duì)列，如下圖所示：
而 LinkedBlockingQueue 是使用鏈表實(shí)現(xiàn)的普通隊(duì)列，如下圖所示：
常用方法
普通隊(duì)列中的常用方法有以下這些：
offer()：添加元素，如果隊(duì)列已滿直接返回 false，隊(duì)列未滿則直接插入并返回 true； poll()：刪除并返回隊(duì)頭元素，當(dāng)隊(duì)列為空返回 null； add()：添加元素，此方法是對(duì) offer 方法的簡(jiǎn)單封裝，如果隊(duì)列已滿，拋出 IllegalStateException 異常； remove()：直接刪除隊(duì)頭元素； put()：添加元素，如果隊(duì)列已經(jīng)滿，則會(huì)阻塞等待插入； take()：刪除并返回隊(duì)頭元素，當(dāng)隊(duì)列為空，則會(huì)阻塞等待； peek()：查詢隊(duì)頭元素，但不會(huì)進(jìn)行刪除； element()：對(duì) peek 方法進(jìn)行簡(jiǎn)單封裝，如果隊(duì)頭元素存在則取出并不刪除，如果不存在拋出 NoSuchElementException 異常。
注意：一般情況下 offer() 和 poll() 方法配合使用，put() 和 take() 阻塞方法配合使用，add() 和 remove() 方法會(huì)配合使用，程序中常用的是 offer() 和 poll() 方法，因此這兩個(gè)方法比較友好，不會(huì)報(bào)錯(cuò)。
接下來我們以 LinkedBlockingQueue 為例，演示一下普通隊(duì)列的使用：
import java.util.concurrent.LinkedBlockingQueue;
static class LinkedBlockingQueueTest {
public static void main(String[] args) {
LinkedBlockingQueue queue = new LinkedBlockingQueue();
queue.offer("Hello");
queue.offer("Java");
queue.offer("中文社群");
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}
以上代碼的執(zhí)行結(jié)果如下：
Hello
Java
中文社群
2.雙端隊(duì)列
雙端隊(duì)列（Deque）是指隊(duì)列的頭部和尾部都可以同時(shí)入隊(duì)和出隊(duì)的數(shù)據(jù)結(jié)構(gòu)，如下圖所示：
接下來我們來演示一下雙端隊(duì)列 LinkedBlockingDeque 的使用：
import java.util.concurrent.LinkedBlockingDeque;
/**
* 雙端隊(duì)列示例
*/
static class LinkedBlockingDequeTest {
public static void main(String[] args) {
// 創(chuàng)建一個(gè)雙端隊(duì)列
LinkedBlockingDeque deque = new LinkedBlockingDeque();
deque.offer("offer"); // 插入首個(gè)元素
deque.offerFirst("offerFirst"); // 隊(duì)頭插入元素
deque.offerLast("offerLast"); // 隊(duì)尾插入元素
while (!deque.isEmpty()) {
// 從頭遍歷打印
System.out.println(deque.poll());
}
}
}
以上代碼的執(zhí)行結(jié)果如下：
offerFirst
offer
offerLast
3.優(yōu)先隊(duì)列
優(yōu)先隊(duì)列（PriorityQueue）是一種特殊的隊(duì)列，它并不是先進(jìn)先出的，而是優(yōu)先級(jí)高的元素先出隊(duì)。
優(yōu)先隊(duì)列是根據(jù)二叉堆實(shí)現(xiàn)的，二叉堆的數(shù)據(jù)結(jié)構(gòu)如下圖所示：
二叉堆分為兩種類型：一種是最大堆一種是最小堆。以上展示的是最大堆，在最大堆中，任意一個(gè)父節(jié)點(diǎn)的值都大于等于它左右子節(jié)點(diǎn)的值。
因?yàn)閮?yōu)先隊(duì)列是基于二叉堆實(shí)現(xiàn)的，因此它可以將優(yōu)先級(jí)最好的元素先出隊(duì)。
接下來我們來演示一下優(yōu)先隊(duì)列的使用：
import java.util.PriorityQueue;
public class PriorityQueueTest {
// 自定義的實(shí)體類
static class Viper {
private int id; // id
private String name; // 名稱
private int level; // 等級(jí)
public Viper(int id, String name, int level) {
this.id = id;
this.name = name;
this.level = level;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
}
public static void main(String[] args) {
PriorityQueue queue = new PriorityQueue(10, new Comparator<Viper>() {
@Override
public int compare(Viper v1, Viper v2) {
// 設(shè)置優(yōu)先級(jí)規(guī)則（倒序，等級(jí)越高權(quán)限越大）
return v2.getLevel() - v1.getLevel();
}
});
// 構(gòu)建實(shí)體類
Viper v1 = new Viper(1, "Java", 1);
Viper v2 = new Viper(2, "MySQL", 5);
Viper v3 = new Viper(3, "Redis", 3);
// 入列
queue.offer(v1);
queue.offer(v2);
queue.offer(v3);
while (!queue.isEmpty()) {
// 遍歷名稱
Viper item = (Viper) queue.poll();
System.out.println("Name：" + item.getName() +
" Level：" + item.getLevel());
}
}
}
以上代碼的執(zhí)行結(jié)果如下：
Name：MySQL Level：5
Name：Redis Level：3
Name：Java Level：1
從上述結(jié)果可以看出，優(yōu)先隊(duì)列的出隊(duì)是不考慮入隊(duì)順序的，它始終遵循的是優(yōu)先級(jí)高的元素先出隊(duì)。
4.延遲隊(duì)列
延遲隊(duì)列（DelayQueue）是基于優(yōu)先隊(duì)列 PriorityQueue 實(shí)現(xiàn)的，它可以看作是一種以時(shí)間為度量單位的優(yōu)先的隊(duì)列，當(dāng)入隊(duì)的元素到達(dá)指定的延遲時(shí)間之后方可出隊(duì)。
我們來演示一下延遲隊(duì)列的使用：
import lombok.Getter;
import lombok.Setter;
import java.text.DateFormat;
import java.util.Date;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
public class CustomDelayQueue {
// 延遲消息隊(duì)列
private static DelayQueue delayQueue = new DelayQueue();
public static void main(String[] args) throws InterruptedException {
producer(); // 調(diào)用生產(chǎn)者
consumer(); // 調(diào)用消費(fèi)者
}
// 生產(chǎn)者
public static void producer() {
// 添加消息
delayQueue.put(new MyDelay(1000, "消息1"));
delayQueue.put(new MyDelay(3000, "消息2"));
}
// 消費(fèi)者
public static void consumer() throws InterruptedException {
System.out.println("開始執(zhí)行時(shí)間：" +
DateFormat.getDateTimeInstance().format(new Date()));
while (!delayQueue.isEmpty()) {
System.out.println(delayQueue.take());
}
System.out.println("結(jié)束執(zhí)行時(shí)間：" +
DateFormat.getDateTimeInstance().format(new Date()));
}
static class MyDelay implements Delayed {
// 延遲截止時(shí)間（單位：毫秒）
long delayTime = System.currentTimeMillis();
// 借助 lombok 實(shí)現(xiàn)
@Getter
@Setter
private String msg;
/**
* 初始化
* @param delayTime 設(shè)置延遲執(zhí)行時(shí)間
* @param msg 執(zhí)行的消息
*/
public MyDelay(long delayTime, String msg) {
this.delayTime = (this.delayTime + delayTime);
this.msg = msg;
}
// 獲取剩余時(shí)間
@Override
public long getDelay(TimeUnit unit) {
return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
// 隊(duì)列里元素的排序依據(jù)
@Override
public int compareTo(Delayed o) {
if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
return 1;
} else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
return -1;
} else {
return 0;
}
}
@Override
public String toString() {
return this.msg;
}
}
}
以上代碼的執(zhí)行結(jié)果如下：
開始執(zhí)行時(shí)間：2020-10-20 20:17:28
消息1
消息2
結(jié)束執(zhí)行時(shí)間：2020-10-20 20:17:31
從上述結(jié)束執(zhí)行時(shí)間和開始執(zhí)行時(shí)間可以看出，消息 1 和消息 2 都正常實(shí)現(xiàn)了延遲執(zhí)行的功能。
5.其他隊(duì)列
在 Java 的隊(duì)列中有一個(gè)比較特殊的隊(duì)列 SynchronousQueue，它的特別之處在于它內(nèi)部沒有容器，每次進(jìn)行 put() 數(shù)據(jù)后（添加數(shù)據(jù)），必須等待另一個(gè)線程拿走數(shù)據(jù)后才可以再次添加數(shù)據(jù)，它的使用示例如下：
import java.util.concurrent.SynchronousQueue;
public class SynchronousQueueTest {
public static void main(String[] args) {
SynchronousQueue queue = new SynchronousQueue();
// 入隊(duì)
new Thread(() -> {
for (int i = 0; i < 3; i++) {
try {
System.out.println(new Date() + "，元素入隊(duì)");
queue.put("Data " + i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
// 出隊(duì)
new Thread(() -> {
while (true) {
try {
Thread.sleep(1000);
System.out.println(new Date() + "，元素出隊(duì)：" + queue.take());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
}
以上代碼的執(zhí)行結(jié)果如下：
Mon Oct 19 21:00:21 CST 2020，元素入隊(duì)
Mon Oct 19 21:00:22 CST 2020，元素出隊(duì)：Data 0
Mon Oct 19 21:00:22 CST 2020，元素入隊(duì)
Mon Oct 19 21:00:23 CST 2020，元素出隊(duì)：Data 1
Mon Oct 19 21:00:23 CST 2020，元素入隊(duì)
Mon Oct 19 21:00:24 CST 2020，元素出隊(duì)：Data 2
從上述結(jié)果可以看出，當(dāng)有一個(gè)元素入隊(duì)之后，只有等到另一個(gè)線程將元素出隊(duì)之后，新的元素才能再次入隊(duì)。
總結(jié)
本文講了 Java 中的 5 種隊(duì)列：普通隊(duì)列、雙端隊(duì)列、優(yōu)先隊(duì)列、延遲隊(duì)列、其他隊(duì)列。其中普通隊(duì)列的典型代表為 ArrayBlockingQueue 和 LinkedBlockingQueue，雙端隊(duì)列的代表為 LinkedBlockingDeque，優(yōu)先隊(duì)列的代表為 PriorityQueue，延遲隊(duì)列的代表為 DelayQueue，最后還講了內(nèi)部沒有容器的其他隊(duì)列 SynchronousQueue。
往期推薦
一文詳解「隊(duì)列」，手?jǐn)]隊(duì)列的3種方法！
動(dòng)圖演示：手?jǐn)]堆棧的兩種實(shí)現(xiàn)方法！
JDK 竟然是這樣實(shí)現(xiàn)棧的？