? 工欲善其事，必先利其器。

棧和隊(duì)列 - Stack And Queue

棧

如何理解棧呢？

后進(jìn)者先出，先進(jìn)者后出，這就是典型的 "棧" 結(jié)構(gòu)。

04_棧和隊(duì)列-棧結(jié)構(gòu)

從棧的操作特性上來看，棧是一種“操作受限”的線性表，只允許在一端插入和刪除數(shù)據(jù)。

事實(shí)上，從功能上來說，數(shù)組或者鏈表確實(shí)都可以替代棧，但你要知道，特定的數(shù)據(jù)結(jié)構(gòu)是對特定場景的抽象，而且，數(shù)組或鏈表暴漏了太多的操作接口，操作上的確靈活運(yùn)用，但同時(shí)使用時(shí)就變的不可控，自然也就更容易出錯(cuò)。

當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足后進(jìn)先出、先進(jìn)后出的特性，就應(yīng)該首選“棧”這種數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn)棧

既然數(shù)組或者鏈表可以替代棧，那么同樣的，使用數(shù)組和鏈表可以實(shí)現(xiàn)棧。用數(shù)組實(shí)現(xiàn)的棧叫做順序棧，用鏈表實(shí)現(xiàn)的棧叫做鏈?zhǔn)綏！?/p>//?基于數(shù)組實(shí)現(xiàn)的順序棧
public?class?ArrayStack?{
??private?String[]?items;??//?數(shù)組
??private?int?count;???????//?棧中元素個(gè)數(shù)
??private?int?n;???????????//棧的大小

??//?初始化數(shù)組，申請一個(gè)大小為n的數(shù)組空間
??public?ArrayStack(int?n)?{
????this.items?=?new?String[n];
????this.n?=?n;
????this.count?=?0;
??}

??//?入棧操作
??public?boolean?push(String?item)?{
????//?數(shù)組空間不夠了，直接返回false，入棧失敗。
????if?(count?==?n)?return?false;
????//?將item放到下標(biāo)為count的位置，并且count加一
????items[count]?=?item;
????++count;
????return?true;
??}
??
??//?出棧操作
??public?String?pop()?{
????//?棧為空，則直接返回null
????if?(count?==?0)?return?null;
????//?返回下標(biāo)為count-1的數(shù)組元素，并且棧中元素個(gè)數(shù)count減一
????String?tmp?=?items[count-1];
????--count;
????return?tmp;
??}
}

上面代碼是拷貝網(wǎng)上的，使用java的數(shù)組實(shí)現(xiàn)棧。

了解了定義和基本操作，那它的操作的時(shí)間、空間復(fù)雜度是多少呢？

不管是順序棧還是鏈?zhǔn)綏?#xff0c;存儲(chǔ)數(shù)據(jù)只需要一個(gè)大小為 n 的數(shù)組就夠了。在入棧和出棧過程中，只需要一兩個(gè)臨時(shí)變量存儲(chǔ)空間，所以空間復(fù)雜度是 O(1)。

注意，這里存儲(chǔ)數(shù)據(jù)需要一個(gè)大小為 n 的數(shù)組，并不是說空間復(fù)雜度就是 O(n)。因?yàn)?#xff0c;這 n 個(gè)空間是必須的，無法省掉。所以我們說空間復(fù)雜度的時(shí)候，是指除了原本的數(shù)據(jù)存儲(chǔ)空間外，算法運(yùn)行還需要額外的存儲(chǔ)空間。

不管是順序棧還是鏈?zhǔn)綏?#xff0c;入棧、出棧只涉及棧頂個(gè)別數(shù)據(jù)的操作，所以時(shí)間復(fù)雜度都是 O(1)。

棧的應(yīng)用 - 四則運(yùn)算

四則運(yùn)算是編譯器利用棧來實(shí)現(xiàn)的表達(dá)式求值。

對于四則運(yùn)算來說，我們大腦可以很快的計(jì)算出來，但是對于計(jì)算機(jī)而言，理解四則運(yùn)算本來就難。

那么編譯器如何通過棧來解決四則運(yùn)算，首先我們需要兩個(gè)棧，一個(gè)保存操作數(shù)，一個(gè)保存運(yùn)算符。從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。

如果比運(yùn)算符棧頂元素的優(yōu)先級高，就將當(dāng)前運(yùn)算符壓入棧；如果比運(yùn)算符棧頂元素的優(yōu)先級低或者相同，從運(yùn)算符棧中取棧頂運(yùn)算符，從操作數(shù)棧的棧頂取 2 個(gè)操作數(shù)，然后進(jìn)行計(jì)算，再把計(jì)算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

04_棧和隊(duì)列-四則運(yùn)算

隊(duì)列

棧是后進(jìn)先出，那有沒有先進(jìn)先出的呢？當(dāng)然有，就是隊(duì)列。

先進(jìn)先出，這就是典型的“隊(duì)列”

棧只支持兩個(gè)基本操作：入棧 push()和出棧 pop()。隊(duì)列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個(gè)：入隊(duì) enqueue()，放一個(gè)數(shù)據(jù)到隊(duì)列尾部；出隊(duì) dequeue()，從隊(duì)列頭部取一個(gè)元素。

04_棧和隊(duì)列-隊(duì)列

所以，隊(duì)列跟棧一樣，也是一種操作受限的線性表數(shù)據(jù)結(jié)構(gòu)。

隊(duì)列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列的應(yīng)用也非常廣泛，特別是一些具有某些額外特性的隊(duì)列，比如循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列。它們在很多偏底層系統(tǒng)、框架、中間件的開發(fā)中，起著關(guān)鍵性的作用。比如高性能隊(duì)列 Disruptor、Linux 環(huán)形緩存，都用到了循環(huán)并發(fā)隊(duì)列；Java concurrent 并發(fā)包利用 ArrayBlockingQueue 來實(shí)現(xiàn)公平鎖等。

實(shí)現(xiàn)隊(duì)列

跟棧一樣，隊(duì)列可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫作順序棧，用鏈表實(shí)現(xiàn)的棧叫作鏈?zhǔn)綏！Ｍ瑯?#xff0c;用數(shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。

//?用數(shù)組實(shí)現(xiàn)的隊(duì)列
public?class?ArrayQueue?{
??//?數(shù)組：items，數(shù)組大小：n
??private?String[]?items;
??private?int?n?=?0;
??//?head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
??private?int?head?=?0;
??private?int?tail?=?0;

??//?申請一個(gè)大小為capacity的數(shù)組
??public?ArrayQueue(int?capacity)?{
????items?=?new?String[capacity];
????n?=?capacity;
??}

??//?入隊(duì)
??public?boolean?enqueue(String?item)?{
????//?如果tail?==?n?表示隊(duì)列已經(jīng)滿了
????if?(tail?==?n)?return?false;
????items[tail]?=?item;
????++tail;
????return?true;
??}

??//?出隊(duì)
??public?String?dequeue()?{
????//?如果head?==?tail?表示隊(duì)列為空
????if?(head?==?tail)?return?null;
????//?為了讓其他語言的同學(xué)看的更加明確，把--操作放到單獨(dú)一行來寫了
????String?ret?=?items[head];
????++head;
????return?ret;
??}
}

對于棧來說，我們只需要一個(gè)棧頂指針就可以了。但是隊(duì)列需要兩個(gè)指針：一個(gè)是 head 指針，指向隊(duì)頭；一個(gè)是 tail 指針，指向隊(duì)尾。

當(dāng) a、b、c、d 依次入隊(duì)之后，隊(duì)列中的 head 指針指向下標(biāo)為 0 的位置，tail 指針指向下標(biāo)為 4 的位置。

當(dāng)我們調(diào)用兩次出隊(duì)操作之后，隊(duì)列中 head 指針指向下標(biāo)為 2 的位置，tail 指針仍然指向下標(biāo)為 4 的位置。

04_棧和隊(duì)列-隊(duì)列運(yùn)行

隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作，head 和 tail 都會(huì)持續(xù)往后移動(dòng)。當(dāng) tail 移動(dòng)到最右邊，即使數(shù)組中還有空閑空間，也無法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了。

在數(shù)組那一節(jié)，我們也遇到過類似的問題，就是數(shù)組的刪除操作會(huì)導(dǎo)致數(shù)組中的數(shù)據(jù)不連續(xù)。你還記得我們當(dāng)時(shí)是怎么解決的嗎？對，用數(shù)據(jù)搬移!

每次進(jìn)行出隊(duì)操作都相當(dāng)于刪除數(shù)組下標(biāo)為 0 的數(shù)據(jù)，要搬移整個(gè)隊(duì)列中的數(shù)據(jù)，這樣出隊(duì)操作的時(shí)間復(fù)雜度就會(huì)從原來的 O(1) 變?yōu)?O(n)。實(shí)際上，我們在出隊(duì)時(shí)可以不用搬移數(shù)據(jù)。如果沒有空閑空間了，我們只需要在入隊(duì)時(shí)，再集中觸發(fā)一次數(shù)據(jù)的搬移操作。

所以改造下上面的代碼后：

???//?入隊(duì)操作，將item放入隊(duì)尾
??public?boolean?enqueue(String?item)?{
????//?tail?==?n表示隊(duì)列末尾沒有空間了
????if?(tail?==?n)?{
??????//?tail?==n?&&?head==0，表示整個(gè)隊(duì)列都占滿了
??????if?(head?==?0)?return?false;
??????//?數(shù)據(jù)搬移
??????for?(int?i?=?head;?i?????????items[i-head]?=?items[i];
??????}
??????//?搬移完之后重新更新head和tail
??????tail?-=?head;
??????head?=?0;
????}
????
????items[tail]?=?item;
????++tail;
????return?true;
??}

從代碼中我們看到，當(dāng)隊(duì)列的 tail 指針移動(dòng)到數(shù)組的最右邊后，如果有新的數(shù)據(jù)入隊(duì)，我們可以將 head 到 tail 之間的數(shù)據(jù)，整體搬移到數(shù)組中 0 到 tail-head 的位置。

04_棧和隊(duì)列-隊(duì)列數(shù)據(jù)搬移

出隊(duì)操作的時(shí)間復(fù)雜度仍然是 O(1)，但是入隊(duì)操作時(shí)需要使用前面提到的時(shí)間復(fù)雜度中的攤還分析，時(shí)間復(fù)雜度仍是 O(1) 。

循環(huán)隊(duì)列

剛才用數(shù)組來實(shí)現(xiàn)隊(duì)列的時(shí)候，在 tail==n 時(shí)，會(huì)有數(shù)據(jù)搬移操作，這樣入隊(duì)操作性能就會(huì)受到影響。那有沒有辦法能夠避免數(shù)據(jù)搬移呢？我們來看看循環(huán)隊(duì)列的解決思路。

循環(huán)隊(duì)列，顧名思義，它長得像一個(gè)環(huán)。原本數(shù)組是有頭有尾的，是一條直線。現(xiàn)在我們把首尾相連，扳成了一個(gè)環(huán)。如下圖所示

04_棧和隊(duì)列-循環(huán)隊(duì)列

隊(duì)列應(yīng)用

隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)很基礎(chǔ)，平時(shí)的業(yè)務(wù)開發(fā)不大可能從零實(shí)現(xiàn)一個(gè)隊(duì)列，甚至都不會(huì)直接用到。而一些具有特殊特性的隊(duì)列應(yīng)用卻比較廣泛，比如阻塞隊(duì)列和并發(fā)隊(duì)列。

阻塞隊(duì)列其實(shí)就是在隊(duì)列基礎(chǔ)上增加了阻塞操作。簡單來說，就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞。因?yàn)榇藭r(shí)還沒有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后再返回。

線程安全的隊(duì)列我們叫作并發(fā)隊(duì)列。最簡單直接的實(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ù)據(jù)結(jié)構(gòu)(四)- 鏈表

算法與數(shù)據(jù)結(jié)構(gòu)(三)- 數(shù)組

算法與數(shù)據(jù)結(jié)構(gòu)(二)- 算法分析

算法與數(shù)據(jù)結(jié)構(gòu)(一)- 概述

總結(jié)

以上是生活随笔為你收集整理的队列的基本操作_算法与数据结构（五） 栈和队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。