??????作者：
@小魚(yú)不會(huì)騎車(chē)
??????專(zhuān)欄：
《數(shù)據(jù)結(jié)構(gòu)》
??????個(gè)人簡(jiǎn)介：
一名專(zhuān)科大一在讀的小比特，努力學(xué)習(xí)編程是我唯一的出路??????

棧

一. 棧的基本概念

棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。

在我們的常見(jiàn)生活中，我們?cè)谑褂脼g覽器啊，寫(xiě)代碼啊，或者說(shuō)制作視頻都會(huì)發(fā)現(xiàn)有一個(gè)返回鍵，例如我們?cè)谟梦募A在訪問(wèn)內(nèi)容時(shí)，不小心點(diǎn)錯(cuò)文件，進(jìn)入了一個(gè)不是自己想要查找的文件時(shí)，我們便可以通過(guò)上方的返回鍵來(lái)返回上一個(gè)頁(yè)面。

這里涉及到的就是棧，也是棧經(jīng)常使用的場(chǎng)景，當(dāng)然！不同的程序他們的底層會(huì)用不同的代碼來(lái)實(shí)現(xiàn)，但是不變的就是棧這個(gè)思想，我們只需要了解棧的這個(gè)數(shù)據(jù)結(jié)構(gòu)就行。

1. 棧的定義

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂
出棧：棧的刪除操作叫做出棧，出數(shù)據(jù)在棧頂

棧在現(xiàn)實(shí)生活中的例子：

2. 棧的常見(jiàn)基本操作

二. 棧的順序存儲(chǔ)結(jié)構(gòu)

1. 棧的順序存儲(chǔ)

采用順序存儲(chǔ)的棧稱(chēng)為順序棧，它利用一組地址連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針（top）指示當(dāng)前棧頂元素的位置。

top的第一種初始化方法

對(duì)于top其實(shí)有兩種初始化的方法，一種就是初始化為0，

public class MyStack {
    int []array;
    int top;//記錄棧頂位置
    int capacity;//容量
    public MyStack(int x) {
        this.top=0;//初始化為0
        array=new int[x];//初始化一個(gè)x大小的數(shù)組
        capacity=x;
    }
    public MyStack() {
        this.top=0;//初始化為0
        array=new int[4];//默認(rèn)初始化為4個(gè)大小的數(shù)組
        capacity=4;

    }

對(duì)于top 初始化為0，其實(shí)就是每次棧頂添加新元素時(shí)，都是先進(jìn)行賦值，再top++，并且還需要對(duì)棧滿(mǎn)進(jìn)行判斷（top初始化為0時(shí)添加元素和判斷棧滿(mǎn)的條件如下）

    public void push(int x) {
        //判斷棧滿(mǎn)
        if(top==capacity) {
            //擴(kuò)容
        }
        array[top]=x;
        top++;
    }

如圖：

top的第二種初始化方法

當(dāng)我的top初始化為-1時(shí),由于我們添加元素需要從0下標(biāo)開(kāi)始添加，所以我們需要先top++，再賦值，此時(shí)我們的top記錄的就是棧頂元素的下標(biāo)，那么判滿(mǎn)的話(huà)，就需要和capacity-1進(jìn)行對(duì)比

public class MyStack {
    int []array;
    int top;//記錄棧頂位置
    int capacity;//容量
    public MyStack(int x) {
        this.top=-1;//初始化為-1
        array=new int[x];//初始化一個(gè)x大小的數(shù)組
        capacity=x;
    }
    public MyStack() {
        this.top=-1;//初始化為-1
        array=new int[4];//默認(rèn)初始化為4個(gè)大小的數(shù)組
        capacity=4;

    }
    public void push(int x) {
        //判斷棧滿(mǎn)
        if(top==capacity-1) {
            //擴(kuò)容
        }
        top++;
        array[top]=x;
    }
}

如圖：
此時(shí)的top就是棧頂元素對(duì)應(yīng)的下標(biāo)

2. 棧的基本方法

（1） 初始化

//兩個(gè)構(gòu)造方法
    public MyStack(int x) {
        this.top=-1;
        array=new int[x];//初始化一個(gè)x大小的數(shù)組
        capacity=x;
    }
    public MyStack() {
        this.top=-1;
        array=new int[4];//默認(rèn)初始化為4個(gè)大小的數(shù)組
        capacity=4;

    }

（2） 判空+判滿(mǎn)（top初始化為-1）

//判空，當(dāng)我的top為-1時(shí)就是沒(méi)有元素
    public boolean empty(){
        return top==-1;
    }
    //判滿(mǎn)，當(dāng)我的top+1==capacity時(shí)就代表?xiàng)M(mǎn)了
    public boolean full() {
        return top+1==capacity;
    }

（3） 進(jìn)棧

    public void push(int x) {
        //判斷棧滿(mǎn)
        if(full()) {
        //每次棧滿(mǎn)擴(kuò)容二倍
           array=Arrays.copyOf(array,2*capacity);
            capacity*=2;
        }
        top++;
        array[top]=x;
    }

（4） 出棧

    //出棧
    public int pop() {
        if(empty()) {
            throw new ArrayEmptyException("棧空");
        }
        //先返回棧頂元素再--
        return array[top--];
    }
    //自定義異常，當(dāng)棧為空時(shí)拋出異常
class ArrayEmptyException extends RuntimeException{
    public ArrayEmptyException() {
    }
	//構(gòu)造方法
    public ArrayEmptyException(String message) {
        super(message);
    }
}

（5） 讀取棧頂元素

    public int peek() {
        if(empty()) {
            throw new ArrayEmptyException("?？?);
        }
        //直接返回棧頂元素
        return array[top];
    }

3. 進(jìn)棧出棧變化形式

我們現(xiàn)在已經(jīng)簡(jiǎn)單了解了棧的特性，那么大家思考一下，這個(gè)最先進(jìn)棧的元素只能是最后出棧嘛？

答案是不一定的！因?yàn)闂ｋm然限制了線性表的插入和刪除的位置，但是并沒(méi)有對(duì)元素的進(jìn)出進(jìn)行時(shí)間限制，也可以理解為，在不是所有元素都進(jìn)棧的情況下，事先進(jìn)去的元素也可以出棧，只要保證是棧頂元素出棧就可以。

舉例來(lái)說(shuō)，如果我們現(xiàn)在是有 3個(gè)整型數(shù)字元素1，2，3 依次進(jìn)棧，會(huì)有哪些出棧次序呢?

• 第一種（最容易理解的）：1，2，3依次進(jìn)棧，再依次出棧，出棧次序是3，2，1.
• 第二種：1進(jìn)棧，1出棧，2進(jìn)棧，3進(jìn)棧，3出棧，2出棧，出棧次序是1 ，3， 2.
• 第三種：1進(jìn)棧，1出棧，2進(jìn)棧，2出棧，3進(jìn)棧，3出棧，出棧次序是1 ，2 ，3.
• 第四種：1進(jìn)棧，2進(jìn)棧，2出棧，1出棧，3進(jìn)棧，3出棧，出棧次序是2， 1， 3.
• 第五種：1進(jìn)棧，2進(jìn)棧，2出棧，3進(jìn)棧，3出棧，1出棧，出棧次序是2 ，3， 1.
• 那我們的出棧次序可以是3 1 2嘛？答案是不可以，因?yàn)?進(jìn)棧后，此時(shí)棧內(nèi)一定是有1，2，此時(shí)棧頂是2，并且1在2的下面，由于只能從棧頂彈出，又因?yàn)椴豢梢灾苯犹^(guò)2去拿到1，所以此時(shí)不會(huì)出現(xiàn) 1 比 2 優(yōu)先出棧的情況。

對(duì)于棧的變化，光三個(gè)元素就有五種出棧次序，那么五個(gè)元素，甚至更多的元素，那么它的出棧變化會(huì)更多，所以這個(gè)知識(shí)點(diǎn)我們一定要弄明白！

這里有道題，大家可以試著做一下：

1. 若進(jìn)棧序列為 1,2,3,4 ，進(jìn)棧過(guò)程中可以出棧，則下列不可能的一個(gè)出棧序列是（）
   A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

答案是：c

4. 共享?xiàng)＃p棧）

其實(shí)對(duì)于共享?xiàng)＃褪潜M量減少內(nèi)存的浪費(fèi)，就像吃飯一樣，煮方便面一袋不夠吃，兩袋吃不完，那你就可以找一個(gè)小伙伴一起吃，然后煮三袋，這樣就不會(huì)吃不完了，并且還都能吃飽，這里開(kāi)個(gè)玩笑，真正的用法在下面。

（1） 共享?xiàng)５母拍?/h6>

利用棧底位置相對(duì)不變的特征，可讓兩個(gè)順序棧共享一個(gè)一維數(shù)組空間，將兩個(gè)棧的棧底分別設(shè)置在共享空間的兩端，兩個(gè)棧頂向共享空間的中間延伸，如下圖所示

當(dāng)我的top0==-1時(shí)，0號(hào)棧底為空，當(dāng)我的top1==MaxSize時(shí)，1號(hào)棧底為空，當(dāng)我的top0+1==top1時(shí)，判斷為棧滿(mǎn)，0號(hào)棧進(jìn)棧時(shí)top0先加一再賦值，1號(hào)棧進(jìn)棧時(shí)top1先減一再賦值，0號(hào)出棧時(shí)先保存當(dāng)前元素再減一，1號(hào)棧出棧時(shí)和0號(hào)棧的出棧操作恰好相反。

（2） 共享?xiàng)５目臻g結(jié)構(gòu)

代碼如下：

public class SharedStack {

    int[]array;//定義一個(gè)數(shù)組成員
    int top0;//記錄0號(hào)棧的棧頂
    int top1;//記錄1號(hào)棧的棧頂
    //構(gòu)造方法，可以自己設(shè)置大小的數(shù)組
    public SharedStack(int x) {
        array=new int[x];
        top0=-1;
        top1=x;
    }
    public SharedStack() {
        //由于共享?xiàng)２缓脭U(kuò)容，所以直接開(kāi)辟50個(gè)大小的數(shù)組
        array=new int[50];
        top0=-1;
        top1=4;
    }

}

（3） 共享?xiàng)＿M(jìn)棧

由于是雙端棧，所以我們需要對(duì)它調(diào)用不同的棧進(jìn)行不同的寫(xiě)法，也就是需要判斷是0號(hào)棧還是1號(hào)棧，分別寫(xiě)出對(duì)于的push.

    public void push(int x,int stackNumber) {
        //判斷棧是否滿(mǎn)了
        if(top0+1==top1) {
            exit(0);
        }
        //通過(guò)stackNumber來(lái)控制調(diào)用0號(hào)?；?號(hào)棧
        if(stackNumber==0) {
            top0++;
            array[top0]=x;
        } else  {
            top1--;
            array[top1]=x;
        }
    }

（4） 共享?xiàng)３鰲?/h6>

    public int pop(int stackNumber) {
    //判斷調(diào)用幾號(hào)棧
        if(stackNumber==0) {
        //判空
            if(top0==-1) {
                System.out.println("棧空");
            exit(0);
            } else {
                return array[top0--];
            }
        }else if(stackNumber==1){
            //判空
            if(top1==array.length) {
               System.out.println("棧空");
                exit(0);
            }else {
                return array[top1++];
            }
        }
        System.out.println("stackNumber輸入錯(cuò)誤");
        //輸入的stackNumber錯(cuò)誤所以返回-1
        //我們認(rèn)為-1就是輸入錯(cuò)誤
        return -1;
    }

共享?xiàng)３Ｓ脠?chǎng)景

一般的常用場(chǎng)景是，兩個(gè)棧的空間需求有相反關(guān)系時(shí)，也就是一個(gè)棧增長(zhǎng)，一個(gè)棧縮小的情況，例如你去買(mǎi)菜，你買(mǎi)了一斤白菜，那么賣(mài)家就少了一斤白菜，就這樣我進(jìn)，你出，才會(huì)使兩棧空間的存儲(chǔ)方法有更大的意義，否則如果我一直買(mǎi)菜，但是賣(mài)家也在一直進(jìn)菜，那么很快就會(huì)因?yàn)闂M(mǎn)而溢出了。

當(dāng)然，這個(gè)只是針對(duì)兩個(gè)數(shù)據(jù)類(lèi)型相同的棧設(shè)計(jì)的一個(gè)技巧，如果是不相同的棧，那么這么做反而會(huì)使問(wèn)題變得更加復(fù)雜，所以大家要注意！

三. 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1. 鏈棧

我們不僅可以通過(guò)順序表實(shí)現(xiàn)棧，也是可以通過(guò)鏈表來(lái)實(shí)現(xiàn)的，但是有個(gè)前提，因?yàn)槲覀兊捻樞虮韺?shí)現(xiàn)的棧，它的插入和刪除時(shí)間復(fù)雜度是O(1),那么如果想通過(guò)鏈表來(lái)實(shí)現(xiàn)棧，那么我們就需要考慮時(shí)間復(fù)雜度能否達(dá)到O(1)，我們?nèi)绻峭ㄟ^(guò)雙向鏈表來(lái)實(shí)現(xiàn)棧的話(huà)，因?yàn)殡p向鏈表本身含有尾結(jié)點(diǎn)的指針，所以它的插入和刪除的時(shí)間復(fù)雜度是O（1），那么我們可以通過(guò)單鏈表來(lái)實(shí)現(xiàn)嘛？

答案也是可以的 !

我們可以通過(guò)頭插頭刪來(lái)實(shí)現(xiàn)棧，由于我們單鏈表的頭插，頭刪的時(shí)間復(fù)雜度都是O(1)，并且我們的頭插頭刪也滿(mǎn)足了棧的先進(jìn)后出的特性. 在鏈棧沒(méi)有結(jié)點(diǎn)時(shí)，我們規(guī)定此時(shí)的head指向null.

鏈棧的優(yōu)點(diǎn)

由于我們是通過(guò)鏈表來(lái)實(shí)現(xiàn)的棧所以可以稱(chēng)為鏈棧，鏈棧幾乎不會(huì)存在棧滿(mǎn)的現(xiàn)象除非內(nèi)存已經(jīng)沒(méi)有可以使用的空間了，如果真的發(fā)生，那么說(shuō)明此時(shí)計(jì)算機(jī)已經(jīng)內(nèi)存被占滿(mǎn)處于即將死機(jī)崩潰的情況，而不是這個(gè)鏈棧是否溢出的問(wèn)題。

鏈棧的優(yōu)點(diǎn)：

• 便于多個(gè)棧共享存儲(chǔ)空間，提高內(nèi)存利用率。
• 幾乎不會(huì)存在棧滿(mǎn)的情況

2. 鏈棧的基本方法

（1） 鏈棧的入棧

鏈棧的結(jié)構(gòu)代碼：

public class MyLinkedStack {

    static class Node{
    //單鏈表需要的next和val
        public Node next;
        public int val;	
	//構(gòu)造方法
        public Node(int val) {
            this.val = val;
        }
    }
    //成員變量head
    public Node head;
   }

壓棧/入棧：

    public void push(int x) {
    //創(chuàng)建一個(gè)新節(jié)點(diǎn)
        Node node=new Node(x);
            //不管我的head是否為空，都可以將node的下一個(gè)結(jié)點(diǎn)指向head
            node.next = head;
            //head成為新結(jié)點(diǎn)
        	head=node;
    }

（2） 鏈棧的出棧

用變量n保存要?jiǎng)h除結(jié)點(diǎn)得值，頭節(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)，返回n.

    public int pop() {
    //判空，如果為空返回-1
        if(empty()) {
            return -1;
        }
        //記錄頭節(jié)點(diǎn)的值
        int n=head.val;
        //頭指針指向下一個(gè)結(jié)點(diǎn)
        head=head.next;
        return n;

    }

3. 對(duì)比鏈棧和順序棧

鏈棧的進(jìn)棧push和出棧pop操作都很簡(jiǎn)單，時(shí)間復(fù)雜度均為O(1)。

對(duì)比一下順序棧與鏈棧,它們?cè)跁r(shí)間復(fù)雜度上是一樣的,均為O(1)。對(duì)于空間性能,順序棧需要事先確定一個(gè)固定的長(zhǎng)度,可能會(huì)存在內(nèi)存空間浪費(fèi)的問(wèn)題,但它的優(yōu)勢(shì)是存取時(shí)定位很方便,而鏈棧則要求每個(gè)元素都有指針域,這同時(shí)也增加了一些內(nèi)存開(kāi)銷(xiāo),但對(duì)于棧的長(zhǎng)度無(wú)限制。所以它們的區(qū)別和線性表中討論的一樣,如果棧的使用過(guò)程中元素變化不可預(yù)料,有時(shí)很小,有時(shí)非常大,那么最好是用鏈棧,反之,如果它的變化在可控范圍內(nèi),建議使用順序棧會(huì)更好一些。

6
6

四. 棧的應(yīng)用——遞歸

1. 遞歸的定義

我們?cè)趯?xiě)遞歸時(shí)需要注意的就是邊界條件，一個(gè)遞歸必須要具有的就是邊界條件，如果沒(méi)有，那么遞歸將會(huì)一直進(jìn)行下去，直到內(nèi)存被棧滿(mǎn)，最后程序崩潰。

我們用求數(shù)字的階乘舉例，例如我們想要求5的階乘，那么我們可以寫(xiě)一個(gè)函數(shù).

    public static int func(int n) {
        //遞歸打印n的階層
        if(n==1) {
            return 1;
        }
        //每次返回當(dāng)前的n*前一個(gè)值
        return n*func(n-1);
    }
    public static void main(String[] args) {
        System.out.println(func(5));
    }

如果用畫(huà)圖解釋就是：

必須注意遞歸模型不是能是循環(huán)定義的，其必須滿(mǎn)足下面的條件

• 遞歸表達(dá)式（遞歸體）
• 邊界條件（遞歸出口）

遞歸的優(yōu)點(diǎn)就是能夠?qū)⒃紗?wèn)題轉(zhuǎn)化為屬性相同單規(guī)模較小的問(wèn)題。
在遞歸調(diào)用的過(guò)程中,系統(tǒng)為每一層的返回點(diǎn)、局部變量、傳入實(shí)參等開(kāi)辟了遞歸工作棧來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ),遞歸次數(shù)過(guò)多容易造成棧溢出等。而其效率不高的原因是遞歸調(diào)用過(guò)程中包含很多重復(fù)的計(jì)算。

如下圖：

如圖可知，程序每往下遞歸一次，就會(huì)把運(yùn)算結(jié)果放到棧中保存，直到程序執(zhí)行到臨界條件，然后便會(huì)把保存在棧中的值按照先進(jìn)后出的順序一個(gè)個(gè)返回，最終得出結(jié)果。

五. 棧的應(yīng)用——逆波蘭表達(dá)式求值

逆波蘭表達(dá)式求值也可以叫做后綴表達(dá)式求值，我們把平時(shí)所用的標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式，也就是例如 " ( A + B ）* C / ( D - E ) "叫做中綴表達(dá)式,因?yàn)樗械倪\(yùn)算符號(hào)都在倆數(shù)字之間。

表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中一個(gè)最基本的問(wèn)題，它的實(shí)現(xiàn)是棧應(yīng)用的一個(gè)典型范例，中綴表達(dá)式不僅依賴(lài)運(yùn)算符的優(yōu)先級(jí)，而且還要處理括號(hào)。

相反：對(duì)于后綴表達(dá)式，它的運(yùn)算符在操作數(shù)的后面，在后綴表達(dá)式中已經(jīng)考慮了運(yùn)算符的優(yōu)先級(jí)，沒(méi)有括號(hào)，只有操作數(shù)和運(yùn)算符。例如上述講到的中綴表達(dá)式（ A + B ）* C / ( D - E )，它對(duì)應(yīng)的后綴表達(dá)式就是A B + C * D E - /。

后綴表達(dá)式計(jì)算規(guī)則：從左到右遍歷表達(dá)式的每個(gè)數(shù)字和符號(hào)，遇到是數(shù)字就進(jìn)棧，遇到是符號(hào)，就將處于棧頂兩個(gè)數(shù)字出棧，進(jìn)項(xiàng)運(yùn)算，運(yùn)算結(jié)果進(jìn)棧，一直到最終獲得結(jié)果。

后綴表達(dá)式 A B + C * D E - /求值的過(guò)程需要 步，如下表所示：

六. 棧的應(yīng)用——中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

前面已經(jīng)對(duì)中綴表達(dá)式進(jìn)行了大概了解，也就是所有的運(yùn)算符號(hào)都在兩數(shù)字的中間,現(xiàn)在我們的問(wèn)題就是中綴到后綴的轉(zhuǎn)化。

規(guī)則:從左到右遍歷中綴表達(dá)式的每個(gè)數(shù)字和符號(hào),若是數(shù)字就輸出,即成為后綴表達(dá)式的一部分;若是符號(hào),則判斷其與棧頂符號(hào)的優(yōu)先級(jí),是右括號(hào)或優(yōu)先級(jí)低于棧頂符號(hào)(乘除優(yōu)先加減)則棧頂元素依次出棧并輸出,并將當(dāng)前符號(hào)進(jìn)棧,一直到最終輸出后綴表達(dá)式為止。

例：將中綴表達(dá)式a + b ? a ? ( ( c + d ) / e ? f ) + g 轉(zhuǎn)化為相應(yīng)的后綴表達(dá)式。

分析：需要根據(jù)操作符的優(yōu)先級(jí)來(lái)進(jìn)行棧的變化,我們用icp來(lái)表示當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級(jí),該運(yùn)算符進(jìn)棧后的優(yōu)先級(jí)為isp,則運(yùn)算符的優(yōu)先級(jí)如下表所示[isp是棧內(nèi)優(yōu)先( in stack priority)數(shù),icp是棧外優(yōu)先( in coming priority)數(shù)]。

我們?cè)诒磉_(dá)式后面加上符號(hào)‘#’,表示表達(dá)式結(jié)束。具體轉(zhuǎn)換過(guò)程如下：

即相應(yīng)的后綴表達(dá)式為a b + a c d + e / f ? ? ? g +。

從剛才的推導(dǎo)中你會(huì)發(fā)現(xiàn)，要想讓計(jì)算機(jī)具有處理我們通常的標(biāo)準(zhǔn)（中綴）表達(dá)式的能力，最重要的就是兩步：

1. 將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式（棧用來(lái)進(jìn)出運(yùn)算的符號(hào)）
2. 將后綴表達(dá)式進(jìn)行運(yùn)算得到結(jié)果（棧用來(lái)進(jìn)出運(yùn)算的數(shù)字）

隊(duì)列

一. 隊(duì)列的基本概念

1. 隊(duì)列的定義

隊(duì)列（Queue） 只是允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱(chēng)FIFO。允許插入的一端稱(chēng)為隊(duì)尾，允許刪除的一端稱(chēng)為隊(duì)頭。

如圖：

進(jìn)出隊(duì)列如圖

進(jìn)隊(duì)列：

出隊(duì)列：

我們一般在醫(yī)院看見(jiàn)的出號(hào)機(jī)就是通過(guò)隊(duì)列來(lái)實(shí)現(xiàn)的，按順序取號(hào)，先取號(hào)的就會(huì)先被叫到，這有個(gè)好處就是，省去了復(fù)雜的排隊(duì)，在你領(lǐng)完號(hào)之后就可以找個(gè)地方休息了，坐等叫號(hào)就行。

隊(duì)頭（Front）：允許刪除的一端，又稱(chēng)隊(duì)首。
隊(duì)尾（Rear）：允許插入的一端。
空隊(duì)列：不包含任何元素的空表。

2. 隊(duì)列的常見(jiàn)基本操作

二. 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

1.順序隊(duì)列

隊(duì)列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲(chǔ)單元存放隊(duì)列中的元素，并附設(shè)兩個(gè)指針：隊(duì)頭指針 front 指向隊(duì)頭元素，隊(duì)尾指針 rear 指向隊(duì)尾元素的下一個(gè)位置。

隊(duì)列的順序存儲(chǔ)類(lèi)型可以描述為:

public class MyQueue {
    int []array;
    int front;//記錄隊(duì)頭
    int rear;//記錄隊(duì)尾

    public MyQueue(int n) {
        //控制一次開(kāi)辟多少內(nèi)存
        array=new int[n];
    }
    public MyQueue() {
        //默認(rèn)開(kāi)辟四個(gè)內(nèi)存
        array=new int[4];
    }

}

初始狀態(tài)：（隊(duì)列為空）：front=rear=0。
進(jìn)棧操作：隊(duì)不滿(mǎn)時(shí),先給隊(duì)尾下標(biāo)對(duì)應(yīng)的數(shù)組賦值，再隊(duì)尾指針加1。
出棧操作：隊(duì)不為空，先取出隊(duì)頭的元素，再隊(duì)頭指針減1。

進(jìn)棧操作如圖：

出棧操作：

假溢出：隊(duì)列出現(xiàn)“上溢出”，然而卻又不是真正的溢出，所以是一種“假溢出”。

大家看下圖：在我的隊(duì)尾指針=5時(shí)，說(shuō)明隊(duì)列已經(jīng)滿(mǎn)了，但是在下標(biāo)為0和1的位置還是空閑的，我們稱(chēng)這種現(xiàn)象為“ 假溢出 ”（所以一般的隊(duì)列會(huì)使用循環(huán)隊(duì)列或者鏈表實(shí)現(xiàn)）

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

解決假溢出的方法就是后面滿(mǎn)了，就再?gòu)念^開(kāi)始，也就是頭尾相接的循環(huán)。我們把隊(duì)列的這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為循環(huán)隊(duì)列。

當(dāng)隊(duì)首指針front = array.length-1后，再前進(jìn)一個(gè)位置就自動(dòng)到0，這可以利用除法取余運(yùn)算（%）來(lái)實(shí)現(xiàn)。

下面是循環(huán)隊(duì)列需要用到的一些公式，后續(xù)介紹。

初始時(shí)：front =rear=0。
判空：front=rear
判滿(mǎn)：(rear+1)%array.length
隊(duì)首指針進(jìn)1：front = (front + 1) % array.length
隊(duì)尾指針進(jìn)1：rear = (rear + 1) % array.length
隊(duì)列長(zhǎng)度：(rear - front + array.length) % array.length

循環(huán)隊(duì)列如圖（下圖中下標(biāo)應(yīng)該是從0開(kāi)始，小魚(yú)不小心寫(xiě)成了1，但是對(duì)于判斷下面的推論沒(méi)什么影響）：

我們需要思考一個(gè)問(wèn)題：如何判斷這個(gè)循環(huán)隊(duì)列是空隊(duì)列，還是滿(mǎn)隊(duì)列？

我們可以看到，在 rear==front 時(shí)，即使空隊(duì)列又是滿(mǎn)隊(duì)列，這就很麻煩，該如何解決呢？

• 方法（1）：我們可以創(chuàng)建一個(gè)成員變量 size，只有當(dāng) size==隊(duì)列長(zhǎng)度時(shí) ，才判滿(mǎn)，當(dāng) size==0 為空隊(duì)列。

• 方法（2) ：我們也可以犧牲一個(gè)空間：

• 方法（3）：類(lèi)型中增設(shè)tag 數(shù)據(jù)成員，以區(qū)分是隊(duì)滿(mǎn)還是隊(duì)空。tag 等于0時(shí)，若因刪除導(dǎo)致 front = = rear ，則為隊(duì)空；tag 等于 1 時(shí)，若因插入導(dǎo)致 front == rear ，則為隊(duì)滿(mǎn)。

這里著重講解第二種方法(在這里將下標(biāo)更正為0)！

就是當(dāng)我們的尾指針+1==頭指針時(shí)(此時(shí)的判斷不完全正確)，說(shuō)明滿(mǎn)了，雖然這樣會(huì)浪費(fèi)一個(gè)空間，但是對(duì)于程序運(yùn)行的效率和降低書(shū)寫(xiě)代碼的難度都是有不錯(cuò)的效果的！

正確判滿(mǎn)的公式應(yīng)該是：（rear+1）%array.length==front

上圖舉例。此時(shí)我的rear=7,但是7+1==8并不等于front,但是這個(gè)隊(duì)列明明確確的已經(jīng)滿(mǎn)了，解決方法就是 (rear + 1 ) % 數(shù)組長(zhǎng)度,當(dāng)我的rear=7時(shí)，（7+1）%8=0，又因?yàn)榇藭r(shí)的 front=0,所以此時(shí)循環(huán)隊(duì)列是滿(mǎn)的。

再舉個(gè)例子：

如上圖：此時(shí)rear=1,并且此時(shí)的隊(duì)列是滿(mǎn)的，那我們就套公式（1+1）%8=2,此時(shí)front=2,說(shuō)明隊(duì)列是滿(mǎn)的！

其實(shí)%的主要作用就是，每次當(dāng)我的 rear 為數(shù)組最后一個(gè)元素的下標(biāo)時(shí)，當(dāng)他需要再前進(jìn)一個(gè)位置時(shí)，便讓他重新回到0下標(biāo)。

判空： rear== front
判滿(mǎn)：（rear+1）%array.length == front

求隊(duì)列長(zhǎng)度：上述的公式是 (rear - front + array.length) % array.length
怎么理解呢？依舊是看圖，這里分為普通情況和特殊情況

普通情況&特殊情況：

特殊情況指的就是當(dāng)我的差為負(fù)數(shù)時(shí)，通過(guò) (rear-front+array.length)%array.length 這個(gè)公式，對(duì)于差是正數(shù)時(shí)沒(méi)有影響，但是對(duì)于差是負(fù)數(shù)時(shí)，便可以求出正確的元素個(gè)數(shù)。

3. 循環(huán)隊(duì)列的常見(jiàn)基本算法

（1）循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

class SqQueue{

    int []array;
    int front;//頭指針
    int rear;//尾指針
    public SqQueue(int n) {
        //控制一次開(kāi)辟多少內(nèi)存
        array=new int[n];
    }
    public SqQueue() {
        //默認(rèn)開(kāi)辟四個(gè)內(nèi)存
        array=new int[4];
    }
    
}

（2） 循環(huán)隊(duì)列判空

    public boolean isEmpty() {
    //當(dāng)相等時(shí)為空
        return rear==front;
    }

（3）求循環(huán)隊(duì)列長(zhǎng)度

    public int QueueLength() {
    //當(dāng)
        return (rear-front+array.length)%array.length;
    }

（4）循環(huán)隊(duì)列入隊(duì)

	//判滿(mǎn)
    public boolean full() {
    //公式如上
        return (rear+1)%array.length==front;
    }
    public void offer(int x) {
        if(full()) {
            return;
        }
        //先插入
        array[rear]=x;
        //當(dāng)rear為數(shù)組的最后一個(gè)元素時(shí)，如果進(jìn)一，就讓他重新回到0結(jié)點(diǎn)
        rear=(rear+1)%array.length;
    }

（5）循環(huán)隊(duì)列出隊(duì)

    public int poll() {
        //如果為空還要?jiǎng)h除就直接終止程序
        if(isEmpty()) {
            exit(0);
        }
        int n=array[front];
        //如果是數(shù)組的最后一個(gè)元素，那么進(jìn)一就重新回到0下標(biāo)
        front=(front+1)%array.length;
        return n;
    }

三. 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1. 鏈隊(duì)列

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示為鏈隊(duì)列，它實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表，只不過(guò)它只能尾進(jìn)頭出而已.

并且鏈隊(duì)列的插入和刪除的時(shí)間復(fù)雜度都是O(1),也可以通過(guò)雙向鏈表實(shí)現(xiàn)。

如圖：

2. 鏈隊(duì)的常見(jiàn)基本算法

（1）鏈隊(duì)列存儲(chǔ)類(lèi)型

class LinkQueue {
    
    static class Node{
        Node next;
        int val;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node front;//頭指針
    public Node rear;//尾指針
    
}

（2）鏈隊(duì)列入隊(duì)

    public void offer(int x) {
        Node node=new Node(x);
        if(front==null) {
            front=node;
        } else {
            rear.next=node;
        }
        rear=node;
    }

（3）鏈隊(duì)列出隊(duì)

出隊(duì)操作時(shí)，就是頭結(jié)點(diǎn)出隊(duì)，將頭結(jié)點(diǎn)的后繼改為新的頭節(jié)點(diǎn)結(jié)點(diǎn)，若新頭節(jié)點(diǎn)指向 null ,此時(shí)鏈表為空需要讓 rear 也指向 null , 避免野指針異常！

    public int poll() {
        if(front==null) {
            //如果頭節(jié)點(diǎn)為空就說(shuō)明沒(méi)有結(jié)點(diǎn)
            return -1;
        }
        int n=front.val;
        front=front.next;
        //若頭指針為空說(shuō)明沒(méi)有結(jié)點(diǎn)，避免空指針異常使rear也指向null
        if(front==null) {
            rear=null;
        }
        return n;
    }

鏈隊(duì)列和循環(huán)隊(duì)列的比較

對(duì)于循環(huán)隊(duì)列與鏈隊(duì)列的比較，可以從兩方面考慮，從時(shí)間上，他們的基本操作都是常數(shù)時(shí)間O（1），不過(guò)循環(huán)隊(duì)列是事先申請(qǐng)好空間，使用期間不釋放，而對(duì)于鏈隊(duì)列，每次申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一些時(shí)間開(kāi)銷(xiāo)，如果入隊(duì)頻繁，則兩者還是有細(xì)微差異，對(duì)于空間上來(lái)說(shuō)，循環(huán)隊(duì)列必須有一個(gè)固定的長(zhǎng)度，所以就有了存儲(chǔ)元素個(gè)數(shù)和空間上的浪費(fèi)，而鏈表不存在這個(gè)問(wèn)題，盡管它需要一個(gè)指針域，會(huì)產(chǎn)生一些空間上的開(kāi)銷(xiāo)，但是也可以接受，所以在空間上，鏈隊(duì)更加的靈活。

總的來(lái)說(shuō)：在可以確定隊(duì)列最大值的情況下，建議使用循環(huán)隊(duì)列，如果你無(wú)法預(yù)估隊(duì)列的長(zhǎng)度時(shí)，則用鏈表。

四. 雙端隊(duì)列

1. 定義

雙端隊(duì)列（deque） 是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列，deque 是 “double ended queue” 的簡(jiǎn)稱(chēng)。
如下圖所示。其元素的邏輯結(jié)構(gòu)仍是線性結(jié)構(gòu)。將隊(duì)列的兩端分別稱(chēng)為前端和后端，兩端都可以入隊(duì)和出隊(duì)。

五. java中集合的用法

在我們需要使用棧的時(shí)候我們可以通過(guò)如下代碼來(lái)使用java中封裝好的。

  Stack<Integer> stack=new Stack<>();

從上圖中可以看到，Stack繼承了Vector，Vector和ArrayList類(lèi)似，都是動(dòng)態(tài)的順序表，不同的是Vector是線程安全的。

由于ArrayDeque和LinkedList都實(shí)現(xiàn)了Deque這個(gè)接口，所以可以通過(guò)這兩個(gè)類(lèi)來(lái)進(jìn)行雙端隊(duì)列的實(shí)現(xiàn)。

Deque q1 = new ArrayDeque<>();//雙端隊(duì)列的線性實(shí)現(xiàn)
Deque q2 = new LinkedList<>();//雙端隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-777262.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：棧和隊(duì)列（詳細(xì)講解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！