如何理解“隊(duì)列”逞带？
隊(duì)列這個(gè)概念非常好理解。你可以把它想象成排隊(duì)買(mǎi)票纱新，先來(lái)的先買(mǎi)展氓，后來(lái)的人只能站末尾，不允許插隊(duì)脸爱。先進(jìn)者先出遇汞，這就是典型的“隊(duì)列”。
我們知道簿废，棧只支持兩個(gè)基本操作：入棧 push()和出棧 pop()空入。隊(duì)列跟棧非常相似，支持的操作也很有限族檬，最基本的操作也是兩個(gè)：入隊(duì) enqueue()歪赢，放一個(gè)數(shù)據(jù)到隊(duì)列尾部；出隊(duì) dequeue()单料，從隊(duì)列頭部取一個(gè)元素埋凯。
順序隊(duì)列和鏈?zhǔn)疥?duì)列
我們知道了，隊(duì)列跟棧一樣扫尖，也是一種抽象的數(shù)據(jù)結(jié)構(gòu)白对。它具有先進(jìn)先出的特性，支持在隊(duì)尾插入元素换怖，在隊(duì)頭刪除元素甩恼，那究竟該如何實(shí)現(xiàn)一個(gè)隊(duì)列呢？
跟棧一樣沉颂，隊(duì)列可以用數(shù)組來(lái)實(shí)現(xiàn)条摸，也可以用鏈表來(lái)實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫作順序棧兆览，用鏈表實(shí)現(xiàn)的棧叫作鏈?zhǔn)綏Ｇ取Ｍ瑯樱脭?shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列抬探，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列子巾。
我們先來(lái)看下基于數(shù)組的實(shí)現(xiàn)方法帆赢。
IQueue 接口定義
package com.s4.queue;
public interface IQueue {
// 隊(duì)列的已用長(zhǎng)度
public abstract int getLength();
// 隊(duì)列的預(yù)設(shè)長(zhǎng)度
public abstract int getPresetLength();
// 入隊(duì)操作
public abstract boolean enqueue(Object value);
public abstract boolean isEmpty();
public abstract boolean isFull();
// 出隊(duì)操作，復(fù)雜度是 O(1)
public abstract Object dequeue();
}
ArrayQueue 關(guān)鍵代碼
/*
* 入隊(duì)操作: 這個(gè)是優(yōu)化后的方案线梗。入隊(duì)操作的時(shí)間復(fù)雜度還是 O(1)
*/
@Override
public boolean enqueue(Object value) {
if (this.isFull()) {
if (this.head == 0) {
return false;
}
// 進(jìn)行遷移[head, tail) 左移 head 位
for (int i = this.head; i < this.tail; i++) {
this.datas[i - this.head] = this.datas[i];
}
// 搬移完之后更新 head 和 tail
this.tail -= this.head;
this.head = 0;
}
this.datas[this.tail] = value;
this.tail++;
return true;
}
// 入隊(duì)操作: 這是一個(gè)錯(cuò)誤示例椰于，一個(gè)較差的方法
public boolean enqueueBad(Object value) {
if (this.isFull()) {
return false;
}
this.datas[this.tail] = value;
this.tail++;
return true;
}
/*
* 出隊(duì)操作，復(fù)雜度是 O(1)
*/
@Override
public Object dequeue() {
if (this.isEmpty()) {
return null;
}
Object ret = this.datas[this.head];
this.head++;
return ret;
}
// 每次出隊(duì)都會(huì)遷移仪搔，會(huì)增加時(shí)間復(fù)雜度為O(n)瘾婿，因此不推薦這么做
@Deprecated
public Object dequeue2() {
if (this.isEmpty()) {
return null;
}
// 每次進(jìn)行出隊(duì)操作都相當(dāng)于刪除數(shù)組下標(biāo)為 0 的數(shù)據(jù)
Object ret = this.datas[0];
// [1, tail -1] 整體左移一位 [1, tail) | [0, tail - 1)
for (int i = 0; i < tail - 1; i++) {
this.datas[i] = this.datas[i + 1];
}
this.tail--;
this.datas[this.tail] = null;
return ret;
}
}
為了解決隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作烤咧，head 和 tail 都會(huì)持續(xù)往后移動(dòng)偏陪。當(dāng) tail 移動(dòng)到最右邊，即使數(shù)組中還有空閑空間煮嫌，也無(wú)法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了的問(wèn)題笛谦？
除了 dequeue2 這種思路外，可以在依舊保留出隊(duì)代碼不變的基礎(chǔ)上昌阿，在入隊(duì)的時(shí)候使用 enqueue 進(jìn)行數(shù)據(jù)遷移饥脑。
接下來(lái)，我們?cè)賮?lái)看下基于鏈表的隊(duì)列實(shí)現(xiàn)方法懦冰。
基于鏈表的實(shí)現(xiàn)灶轰，我們同樣需要兩個(gè)指針：head 指針和 tail 指針。它們分別指向鏈表的第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)刷钢。如圖所示笋颤，入隊(duì)時(shí)，tail->next= new_node, tail = tail->next闯捎；出隊(duì)時(shí)椰弊，head = head->next。我將具體的代碼放到 GitHub 上瓤鼻，你可以自己試著實(shí)現(xiàn)一下，然后再去 GitHub 上跟我實(shí)現(xiàn)的代碼對(duì)比下贤重，看寫(xiě)得對(duì)不對(duì)茬祷。
LinkedQueue 關(guān)鍵代碼
// 入隊(duì)操作
public boolean enqueue(Object value) {
if (this.isFull()) {
return false;
}
Node node = new Node();
node.data = value;
node.next = null;
if (this.isEmpty()) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
this.length++;
return true;
}
// 出隊(duì)操作，復(fù)雜度是 O(1)
public Object dequeue() {
if (this.isEmpty()) {
return null;
}
Node nextNode = this.head.next;
Object ret = this.head.data;
this.head.data = null;
this.head.next = null;
this.head = nextNode;
if (nextNode == null) {
this.tail = null;
}
this.length--;
return ret;
}
循環(huán)隊(duì)列
我們剛才用數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列的時(shí)候并蝗，在 tail==n 時(shí)祭犯，會(huì)有數(shù)據(jù)搬移操作，這樣入隊(duì)操作性能就會(huì)受到影響滚停。那有沒(méi)有辦法能夠避免數(shù)據(jù)搬移呢沃粗？我們來(lái)看看循環(huán)隊(duì)列的解決思路。
循環(huán)隊(duì)列键畴，顧名思義最盅，它長(zhǎng)得像一個(gè)環(huán)突雪。原本數(shù)組是有頭有尾的，是一條直線∥屑現(xiàn)在我們把首尾相連咏删，扳成了一個(gè)環(huán)。我畫(huà)了一張圖问词，你可以直觀地感受一下督函。
我們可以發(fā)現(xiàn)，圖中這個(gè)隊(duì)列的大小為 8激挪，當(dāng)前 head=4辰狡，tail=7。當(dāng)有一個(gè)新的元素 a 入隊(duì)時(shí)垄分，我們放入下標(biāo)為 7 的位置宛篇。但這個(gè)時(shí)候，我們并不把 tail 更新為 8锋喜，而是將其在環(huán)中后移一位些己，到下標(biāo)為 0 的位置。當(dāng)再有一個(gè)元素 b 入隊(duì)時(shí)嘿般，我們將 b 放入下標(biāo)為 0 的位置段标，然后 tail 加 1 更新為 1。所以炉奴，在 a逼庞，b 依次入隊(duì)之后，循環(huán)隊(duì)列中的元素就變成了下面的樣子：
通過(guò)這樣的方法瞻赶，我們成功避免了數(shù)據(jù)搬移操作赛糟。看起來(lái)不難理解砸逊，但是循環(huán)隊(duì)列的代碼實(shí)現(xiàn)難度要比前面講的非循環(huán)隊(duì)列難多了璧南。要想寫(xiě)出沒(méi)有 bug 的循環(huán)隊(duì)列的實(shí)現(xiàn)代碼，我個(gè)人覺(jué)得师逸，最關(guān)鍵的是司倚，確定好隊(duì)空和隊(duì)滿的判定條件。
- 隊(duì)列為空的判斷條件仍然是 head == tail
- 當(dāng)隊(duì)滿時(shí)篓像，(tail+1)%n=head,
- 當(dāng)隊(duì)滿時(shí)动知，圖中的 tail 指向的位置實(shí)際上是沒(méi)有存儲(chǔ)數(shù)據(jù)的。所以员辩，循環(huán)隊(duì)列會(huì)浪費(fèi)一個(gè)數(shù)組的存儲(chǔ)空間盒粮。
CircleQueue 關(guān)鍵代碼
/*
* 入隊(duì)
*/
@Override
public boolean enqueue(Object value) {
if (this.isFull()) {
return false;
}
this.datas[this.tail] = value;
this.tail = indexPlus(this.tail);
return true;
}
/*
* 出隊(duì)，復(fù)雜度是 O(1)
*/
@Override
public Object dequeue() {
if (this.isEmpty()) {
return null;
}
Object ret = this.datas[this.head];
this.head = this.indexPlus(this.head);
return ret;
}
阻塞隊(duì)列和并發(fā)隊(duì)列
前面講的內(nèi)容理論比較多奠滑，看起來(lái)很難跟實(shí)際的項(xiàng)目開(kāi)發(fā)扯上關(guān)系丹皱。確實(shí)妒穴，隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)很基礎(chǔ)，平時(shí)的業(yè)務(wù)開(kāi)發(fā)不大可能從零實(shí)現(xiàn)一個(gè)隊(duì)列种呐，甚至都不會(huì)直接用到宰翅。而一些具有特殊特性的隊(duì)列應(yīng)用卻比較廣泛，比如阻塞隊(duì)列和并發(fā)隊(duì)列爽室。
阻塞隊(duì)列其實(shí)就是在隊(duì)列基礎(chǔ)上增加了阻塞操作汁讼。簡(jiǎn)單來(lái)說(shuō)，就是在隊(duì)列為空的時(shí)候阔墩，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞嘿架。因?yàn)榇藭r(shí)還沒(méi)有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回啸箫；如果隊(duì)列已經(jīng)滿了耸彪，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)忘苛，然后再返回蝉娜。
你應(yīng)該已經(jīng)發(fā)現(xiàn)了，上述的定義就是一個(gè)“生產(chǎn)者 - 消費(fèi)者模型”扎唾！是的召川，我們可以使用阻塞隊(duì)列，輕松實(shí)現(xiàn)一個(gè)“生產(chǎn)者 - 消費(fèi)者模型”胸遇！
這種基于阻塞隊(duì)列實(shí)現(xiàn)的“生產(chǎn)者 - 消費(fèi)者模型”荧呐，可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過(guò)快纸镊，“消費(fèi)者”來(lái)不及消費(fèi)時(shí)倍阐，存儲(chǔ)數(shù)據(jù)的隊(duì)列很快就會(huì)滿了。這個(gè)時(shí)候逗威，生產(chǎn)者就阻塞等待峰搪，直到“消費(fèi)者”消費(fèi)了數(shù)據(jù)，“生產(chǎn)者”才會(huì)被喚醒繼續(xù)“生產(chǎn)”凯旭。
而且不僅如此罢艾，基于阻塞隊(duì)列，我們還可以通過(guò)協(xié)調(diào)“生產(chǎn)者”和“消費(fèi)者”的個(gè)數(shù)尽纽，來(lái)提高數(shù)據(jù)的處理效率。比如前面的例子童漩，我們可以多配置幾個(gè)“消費(fèi)者”弄贿，來(lái)應(yīng)對(duì)一個(gè)“生產(chǎn)者”。
前面我們講了阻塞隊(duì)列矫膨，在多線程情況下差凹，會(huì)有多個(gè)線程同時(shí)操作隊(duì)列期奔，這個(gè)時(shí)候就會(huì)存在線程安全問(wèn)題，那如何實(shí)現(xiàn)一個(gè)線程安全的隊(duì)列呢危尿？
線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列呐萌。最簡(jiǎn)單直接的實(shí)現(xiàn)方式是直接在 enqueue()、dequeue() 方法上加鎖谊娇，但是鎖粒度大并發(fā)度會(huì)比較低肺孤，同一時(shí)刻僅允許一個(gè)存或者取操作。實(shí)際上济欢，基于數(shù)組的循環(huán)隊(duì)列赠堵，利用 CAS 原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列法褥。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因茫叭。在實(shí)戰(zhàn)篇講 Disruptor 的時(shí)候，我會(huì)再詳細(xì)講并發(fā)隊(duì)列的應(yīng)用半等。
內(nèi)容小結(jié)
我的代碼實(shí)現(xiàn)
https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s4
今天我們講了一種跟棧很相似的數(shù)據(jù)結(jié)構(gòu)揍愁，隊(duì)列。關(guān)于隊(duì)列杀饵，你能掌握下面的內(nèi)容莽囤，這節(jié)就沒(méi)問(wèn)題了。
隊(duì)列最大的特點(diǎn)就是先進(jìn)先出凹髓，主要的兩個(gè)操作是入隊(duì)和出隊(duì)烁登。跟棧一樣，它既可以用數(shù)組來(lái)實(shí)現(xiàn)蔚舀，也可以用鏈表來(lái)實(shí)現(xiàn)饵沧。用數(shù)組實(shí)現(xiàn)的叫順序隊(duì)列，用鏈表實(shí)現(xiàn)的叫鏈?zhǔn)疥?duì)列赌躺。特別是長(zhǎng)得像一個(gè)環(huán)的循環(huán)隊(duì)列狼牺。
在數(shù)組實(shí)現(xiàn)隊(duì)列的時(shí)候，會(huì)有數(shù)據(jù)搬移操作礼患，要想解決數(shù)據(jù)搬移的問(wèn)題是钥，我們就需要像環(huán)一樣的循環(huán)隊(duì)列。循環(huán)隊(duì)列是我們這節(jié)的重點(diǎn)缅叠。要想寫(xiě)出沒(méi)有 bug 的循環(huán)隊(duì)列實(shí)現(xiàn)代碼悄泥，關(guān)鍵要確定好隊(duì)空和隊(duì)滿的判定條件，具體的代碼你要能寫(xiě)出來(lái)肤粱。
除此之外弹囚，我們還講了幾種高級(jí)的隊(duì)列結(jié)構(gòu)，阻塞隊(duì)列领曼、并發(fā)隊(duì)列鸥鹉，底層都還是隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)蛮穿，只不過(guò)在之上附加了很多其他功能。阻塞隊(duì)列就是入隊(duì)毁渗、出隊(duì)操作可以阻塞践磅，并發(fā)隊(duì)列就是隊(duì)列的操作多線程安全。
參考
09 | 隊(duì)列：隊(duì)列在線程池等有限資源池中的應(yīng)用
https://time.geekbang.org/column/article/41330
java/09_queue · 編程語(yǔ)言算法集/algo - 碼云 - 開(kāi)源中國(guó) https://gitee.com/TheAlgorithms/algo/tree/master/java/09_queue
