數(shù)據(jù)結(jié)構(gòu)-棧結(jié)構(gòu)

如何理解“椦奁”？

有一個非常貼切的例子对雪，就是一摞疊在一起的盤子河狐。我們平時放盤子的時候，都是從下往上一個一個放；取的時候馋艺，我們也是從上往下一個一個地依次取栅干，不能從中間任意抽出。后進(jìn)者先出捐祠，先進(jìn)者后出碱鳞，這就是典型的“棧”結(jié)構(gòu)踱蛀。

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

如何實現(xiàn)一個“棻琅荩”？

棧主要包含兩個操作猬膨，入棧和出棧角撞，也就是在棧頂插入一個數(shù)據(jù)和從棧頂刪除一個數(shù)據(jù)。理解了棧的定義之后勃痴，我們來看一看如何用代碼實現(xiàn)一個棧谒所。

實際上，棧既可以用數(shù)組來實現(xiàn)沛申，也可以用鏈表來實現(xiàn)劣领。用數(shù)組實現(xiàn)的棧，我們叫作順序棧污它，用鏈表實現(xiàn)的棧剖踊，我們叫作鏈?zhǔn)綏！?/p>

不管是順序棧還是鏈?zhǔn)綏Ｉ辣幔覀兇鎯?shù)據(jù)只需要一個大小為 n 的數(shù)組就夠了德澈。在入棧和出棧過程中，只需要一兩個臨時變量存儲空間固惯，所以空間復(fù)雜度是 O(1)梆造。

注意，這里存儲數(shù)據(jù)需要一個大小為 n 的數(shù)組葬毫，并不是說空間復(fù)雜度就是 O(n)镇辉。因為，這 n 個空間是必須的贴捡，無法省掉忽肛。所以我們說空間復(fù)雜度的時候，是指除了原本的數(shù)據(jù)存儲空間外烂斋，算法運行還需要額外的存儲空間屹逛。

空間復(fù)雜度分析是不是很簡單础废？時間復(fù)雜度也不難。不管是順序棧還是鏈?zhǔn)綏：蹦＃霔Ｆ老佟⒊鰲Ｖ簧婕皸ｍ攤€別數(shù)據(jù)的操作，所以時間復(fù)雜度都是 O(1)淑掌。

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

如果要實現(xiàn)一個支持動態(tài)擴(kuò)容的棧蒿讥，我們只需要底層依賴一個支持動態(tài)擴(kuò)容的數(shù)組就可以了。當(dāng)棧滿了之后抛腕，我們就申請一個更大的數(shù)組芋绸，將原來的數(shù)據(jù)搬移到新數(shù)組中。

實際上兽埃，支持動態(tài)擴(kuò)容的順序棧侥钳，我們平時開發(fā)中并不常用到适袜。我講這一塊的目的柄错，主要還是希望帶你練習(xí)一下前面講的復(fù)雜度分析方法。所以這一小節(jié)的重點還是復(fù)雜度分析苦酱。

對于出棧操作來說售貌，我們不會涉及內(nèi)存的重新申請和數(shù)據(jù)的搬移，所以出棧的時間復(fù)雜度仍然是 O(1)疫萤。但是颂跨，對于入棧操作來說，情況就不一樣了扯饶。當(dāng)棧中有空閑空間時恒削，入棧操作的時間復(fù)雜度為 O(1)。但當(dāng)空間不夠時尾序，就需要重新申請內(nèi)存和數(shù)據(jù)搬移钓丰，所以時間復(fù)雜度就變成了 O(n)。也就是說每币，對于入棧操作來說携丁，最好情況時間復(fù)雜度是 O(1)，最壞情況時間復(fù)雜度是 O(n)兰怠。平均情況下的時間復(fù)雜度又是 O(1)梦鉴。

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

我們再來看棧的另一個常見的應(yīng)用場景，編譯器如何利用棧來實現(xiàn)表達(dá)式求值揭保。

為了方便解釋肥橙，我將算術(shù)表達(dá)式簡化為只包含加減乘除四則運算，比如：34+13*9+44-12/3秸侣。對于這個四則運算存筏，我們?nèi)四X可以很快求解出答案娜庇，但是對于計算機來說，理解這個表達(dá)式本身就是個挺難的事兒方篮。如果換作你名秀，讓你來實現(xiàn)這樣一個表達(dá)式求值的功能，你會怎么做呢藕溅？

實際上匕得，編譯器就是通過兩個棧來實現(xiàn)的。其中一個保存操作數(shù)的棧巾表，另一個是保存運算符的棧汁掠。我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字集币，我們就直接壓入操作數(shù)棧考阱；當(dāng)遇到運算符，就與運算符棧的棧頂元素進(jìn)行比較鞠苟。

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

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

除了用棧來實現(xiàn)表達(dá)式求值冀惭，我們還可以借助棧來檢查表達(dá)式中的括號是否匹配震叙。我們同樣簡化一下背景。

我們假設(shè)表達(dá)式中只包含三種括號散休，圓括號 ()媒楼、方括號[]和花括號{}，并且它們可以任意嵌套溃槐。比如匣砖，{[] ()[{}]}或[{()}([])]等都為合法格式，而{[}()]或[({)]為不合法的格式昏滴。那我現(xiàn)在給你一個包含三種括號的表達(dá)式字符串猴鲫，如何檢查它是否合法呢？

這里也可以用棧來解決谣殊。我們用棧來保存未匹配的左括號拂共，從左到右依次掃描字符串。當(dāng)掃描到左括號時姻几，則將其壓入棧中宜狐；當(dāng)掃描到右括號時势告，從棧頂取出一個左括號。如果能夠匹配抚恒，比如“(”跟“)”匹配咱台，“[”跟“]”匹配，“{”跟“}”匹配俭驮，則繼續(xù)掃描剩下的字符串回溺。如果掃描的過程中，遇到不能配對的右括號混萝，或者棧中沒有數(shù)據(jù)遗遵，則說明為非法格式。

當(dāng)所有的括號都掃描完成之后逸嘀，如果棧為空车要，則說明字符串為合法格式；否則崭倘，說明有未匹配的左括號翼岁，為非法格式。

代碼實現(xiàn)

基于數(shù)組實現(xiàn)的棧
基于鏈表實現(xiàn)的棧
使用前后棧實現(xiàn)瀏覽器的前進(jìn)后退
我們使用兩個棧绳姨，X 和 Y登澜，我們把首次瀏覽的頁面依次壓入棧 X阔挠，當(dāng)點擊后退按鈕時飘庄，再依次從棧 X 中出棧，并將出棧的數(shù)據(jù)依次放入棧 Y购撼。當(dāng)我們點擊前進(jìn)按鈕時跪削，我們依次從棧 Y 中取出數(shù)據(jù)，放入棧 X 中迂求。當(dāng)棧 X 中沒有數(shù)據(jù)時碾盐，那就說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)棧 Y 中沒有數(shù)據(jù)揩局，那就說明沒有頁面可以點擊前進(jìn)按鈕瀏覽了毫玖。

package com.s3.stack;

public class SampleBrowser {

    public static void main(String[] args) {
        SampleBrowser browser = new SampleBrowser();
        browser.openURL("http://www.soso.com");
        browser.openURL("http://www.qq.com/111");
        browser.openURL("http://www.qq.com/222");
        browser.back();
        browser.forward();
        browser.back();
        browser.openURL("http://news.qq.com");
        browser.forward();
        browser.back();
        browser.back();
    }

    private LinkedStack forwardStack = new LinkedStack(100);
    private LinkedStack backStack = new LinkedStack(100);

    public void openURL(String url) {
        this.loadURL(url);
        this.forwardStack.push(url);
        this.backStack.clear();
    }

    private void loadURL(String url) {
        System.out.println("load ..." + url);
    }

    public void back() {
        // 如果 forwardStack 不為空才能繼續(xù)
        if (this.canBack()) {
            this.backStack.push(this.forwardStack.pop());
            this.loadURL((String) this.forwardStack.getTopData());
        } else {
            System.out.println("can not back");
        }
    }

    public void forward() {
        // 如果 forwardStack 不為空才能繼續(xù)
        if (this.canForward()) {
            Object data = this.backStack.pop();
            this.forwardStack.push(data);
            this.loadURL((String) data);
        } else {
            System.out.println("can not forward");
        }
    }

    private boolean canBack() {
        // 當(dāng)前進(jìn)棧里面至少有 2 個元素的時候
        return forwardStack.getUsedLength() >= 2;
    }

    private boolean canForward() {
        return !this.backStack.isEmpty();
    }
}

內(nèi)容小結(jié)

我的代碼實現(xiàn)
https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s3

棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，只支持入棧和出棧操作凌盯。后進(jìn)先出是它最大的特點付枫。棧既可以通過數(shù)組實現(xiàn)，也可以通過鏈表來實現(xiàn)驰怎。不管基于數(shù)組還是鏈表阐滩，入棧、出棧的時間復(fù)雜度都為 O(1)县忌。除此之外掂榔，我們還講了一種支持動態(tài)擴(kuò)容的順序棧继效，你需要重點掌握它的均攤時間復(fù)雜度分析方法。

參考

08 | 棧：如何實現(xiàn)瀏覽器的前進(jìn)和后退功能装获？
https://time.geekbang.org/column/article/41222