如何理解棧

棧就是一個(gè)后入先出拳亿，先入后出的數(shù)據(jù)結(jié)構(gòu)。
從操作特性上看调榄，棧是一種操作受限的線性表踊赠，只允許在一端插入和刪除數(shù)據(jù)。
雖然使用數(shù)組和鏈表能夠替代棧這種數(shù)據(jù)結(jié)構(gòu)每庆，但是數(shù)組與鏈表向外暴露了太多的api接口筐带，操作上面雖然自由，但是使用的時(shí)候就比較不可控缤灵，自然也就更容易出錯(cuò)伦籍。

當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除操作，并且滿足先入后入腮出，后入先出特性帖鸦，我們應(yīng)該選擇棧這種數(shù)據(jù)結(jié)構(gòu)。

如何實(shí)現(xiàn)一個(gè)棧胚嘲？

椬鞫總共就兩個(gè)數(shù)據(jù)結(jié)構(gòu)，一個(gè)是出棧馋劈，一個(gè)是入棧攻锰。我們只需要實(shí)現(xiàn)這兩個(gè)即可。
椉宋恚可以使用數(shù)組或者鏈表來實(shí)現(xiàn)娶吞。

• 使用數(shù)組實(shí)現(xiàn)的棧叫做順序棧
• 使用鏈表實(shí)現(xiàn)的棧叫做鏈?zhǔn)綏?br> 順序棧的實(shí)現(xiàn)如下圖所示：

public class ArrayStack {

    String[] arrayStack;
    int count;
    int n;

    ArrayStack(int num) {
        arrayStack = new String[num];
        count = num;
        n = 0;
    }

    public String pop() {
        if (n == 0){
            return null;
        }
        //先取值，然后再進(jìn)行自減操作
        return arrayStack[n--];
    }

    public boolean push(String item) {
        if (n >= count){
            return false;
        }
        //先賦值君珠，然后再進(jìn)行自增操作
        arrayStack[n++] = item;
        return true;
    }
}

鏈?zhǔn)綏５膶?shí)現(xiàn)如下圖所示：

public class LinkedStack {

    private Item dummy = new Item("dummy");
    //作為棧中最后一個(gè)節(jié)點(diǎn)
    private Item head;

    LinkedStack() {
        head = dummy;
    }

    boolean pop() {
        if (dummy.next == null) {
            return false;
        } else {
            head = head.before;
            head.next = null;
            return true;
        }
    }

    boolean push(String val) {
        Item item = new Item(val);
        item.next = null;
        item.before = head;
        head.next = item;
        head = head.next;
        return true;
    }
}

class Item {

    String val;
    //使用雙向鏈表來處理pop
    Item next;
    Item before;

    Item(String val) {
        this.val = val;
    }
}

其時(shí)間寝志、空間復(fù)雜度都為娇斑。

支持動(dòng)態(tài)擴(kuò)容的順序棧

上面所寫的棧是不支持動(dòng)態(tài)擴(kuò)容的策添，如果增加的item的個(gè)數(shù)超過了棧的大小，則會(huì)報(bào)錯(cuò)毫缆。
我們使棧動(dòng)態(tài)擴(kuò)容的方法很簡單唯竹，因?yàn)轫樞驐５牡讓邮菙?shù)組，當(dāng)超過數(shù)組的范圍時(shí)苦丁，新建一個(gè)兩倍原來大小的數(shù)組浸颓，然后將數(shù)據(jù)復(fù)制過去就可以了。

動(dòng)態(tài)擴(kuò)容的順序棧

棧在函數(shù)調(diào)用上的應(yīng)用

操作系統(tǒng)給每個(gè)線程都分配了一個(gè)獨(dú)立的內(nèi)存空間棵磷。這塊內(nèi)存空間被組織成“棧”這種形式晋涣，用來存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變量仪媒。在Java虛擬機(jī)中，就是其虛擬機(jī)棧谢鹊。
每進(jìn)入一個(gè)函數(shù)算吩，將臨時(shí)變量作為一個(gè)棧幀入棧，當(dāng)被調(diào)用函數(shù)完成的時(shí)候佃扼，這個(gè)棧幀出棧偎巢。

public class test {

    int main() {
        int a = 1;
        int ret = 0;
        int res = 0;
        ret = add(3, 5);
        res = ret + a;
        System.out.printf("%d", res);
        return res;
    }

    int add(int a, int b) {
        int sum = 0;
        sum = a + b;
        return sum;
    }
}

如上述代碼所示，main函數(shù)中調(diào)用了add函數(shù)兼耀。

方法棧幀

棧在表達(dá)式求值中的應(yīng)用

編譯器通過兩個(gè)棧來實(shí)現(xiàn)表達(dá)式求值压昼。
一個(gè)棧用來保存操作數(shù)，一個(gè)棧用來保存操作符翠订。
從左往右遍歷表達(dá)式的時(shí)候巢音，遇到操作數(shù)則將其入棧，遇到操作符尽超，則將其與操作符棧最頂端的元素進(jìn)行比較官撼，如果其比最頂端的操作度等級(jí)高（例如乘除比加減高），則將其入棧似谁，如果比其低傲绣，將最頂端的元素取出來，然后操作數(shù)棧最頂端的兩個(gè)元素也取出來進(jìn)行計(jì)算巩踏，將得到的結(jié)果壓入操作數(shù)棧秃诵，然后將操作符繼續(xù)比較。
一圖勝千言

棧在表達(dá)式求值中的應(yīng)用

棧在括號(hào)匹配中的應(yīng)用

同在表達(dá)式中的應(yīng)用一樣塞琼，我們使用一個(gè)棧來保存左括號(hào)菠净。遇到左括號(hào)就添加到棧頂。如果遇到右括號(hào)彪杉，則從棧頂?shù)綏５妆闅v毅往，如果某一括號(hào)與右括號(hào)類型相同，則把這個(gè)括號(hào)移除派近，不再往下遍歷攀唯，同時(shí)繼續(xù)尋找字符串中的下一個(gè)括號(hào)。如果字符串遍歷到底渴丸，棧中仍然有括號(hào)侯嘀，說明該字符串括號(hào)不匹配另凌，如果棧為空，則說明匹配戒幔。

如何實(shí)現(xiàn)前進(jìn)后退功能

首先我們分析該功能需要實(shí)現(xiàn)的幾個(gè)場景：

• A 點(diǎn)擊進(jìn)入 B吠谢， B能夠返回到A， A能夠前進(jìn)到B
• A點(diǎn)擊進(jìn)入 B, B點(diǎn)擊進(jìn)入C诗茎， C返回到B后囊卜，B點(diǎn)擊進(jìn)入D，此時(shí)D返回到B错沃，B返回到A栅组。

我們可以使用兩個(gè)棧，一個(gè)用來存儲(chǔ)已經(jīng)點(diǎn)擊進(jìn)入的網(wǎng)頁叫后退棧枢析，一個(gè)用來存儲(chǔ)后退時(shí)網(wǎng)頁棧pop掉的網(wǎng)頁叫前進(jìn)棧玉掸。
第一個(gè)場景只需要進(jìn)行普通的push、pop操作就行了醒叁。
第二個(gè)場景則需要特殊處理司浪，如果回退到某一網(wǎng)頁然后點(diǎn)擊新的網(wǎng)頁的話，后退棧正常操作把沼，但是前進(jìn)棧需要清空啊易，然后添加這個(gè)新網(wǎng)頁。