1. 什么是棧惋耙？
棧的特點(diǎn)是后進(jìn)先出乱陡，是一種“操作受限”的線性表，只允許在一端插入和刪除蛋褥。當(dāng)某個數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)临燃，并且滿足后進(jìn)先出、先進(jìn)后出的特性烙心，就應(yīng)該首選“椧穑”這種數(shù)據(jù)結(jié)構(gòu)铆铆。
2. 如何實(shí)現(xiàn)棧碍论？
棧主要包含兩個操作鳍悠，入棧和出棧藏研。實(shí)際上，棧既可以用數(shù)組來實(shí)現(xiàn)弧岳，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫作順序棧消略，用鏈表實(shí)現(xiàn)的棧叫作鏈?zhǔn)綏?/strong>桐臊。用 Java 實(shí)現(xiàn)并不難，建議兩種方式都試一試。
不管是順序棧還是鏈?zhǔn)綏Ｎ装常霔＝樾凇⒊鰲Ｖ簧婕皸ｍ攤€別數(shù)據(jù)的操作嘹承，所以時間復(fù)雜度是 O(1)。在入棧和出棧過程中撼港，只需要一兩個臨時變量存儲空間，所以空間復(fù)雜度是 O(1)蒙揣。
3. 支持動態(tài)擴(kuò)容的順序棧
實(shí)際上，支持動態(tài)擴(kuò)容的順序棧扣汪，我們平時開發(fā)中并不常用到，講這個的目的是復(fù)雜度分析。
對于出棧操作來說，不會涉及內(nèi)存的重新申請和數(shù)據(jù)的搬移，所以出棧的時間復(fù)雜度仍然是 O(1)贬丛。對于入棧操作來說豺憔，在大部分情況下恭应，時間復(fù)雜度 O 都是 O(1)，只有在個別時刻才會退化為 O(n)毅桃，把耗時多的入棧操作的時間均攤到其他入棧操作上，平均情況下的耗時就接近 O(1)读宙。所以入棧操作的均攤時間復(fù)雜度就為 O(1)。
4. 棧的應(yīng)用舉例
- 在函數(shù)調(diào)用中的應(yīng)用
經(jīng)典的一個應(yīng)用場景就是函數(shù)調(diào)用棧桦锄。操作系統(tǒng)給每個線程分配了一塊獨(dú)立的內(nèi)存空間，這塊內(nèi)存被組織成“椊滥Γ”這種結(jié)構(gòu), 用來存儲函數(shù)調(diào)用時的臨時變量蜂厅。每進(jìn)入一個函數(shù)唇跨，就會將臨時變量作為一個棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成玉控，返回之后碾篡，將這個函數(shù)對應(yīng)的棧幀出棧开泽。
- 在表達(dá)式求值中的應(yīng)用
對于加減乘除這種數(shù)學(xué)運(yùn)算滩租，比如 34+13*9+44-12/3技即，編譯器通過兩個棧來實(shí)現(xiàn)。一個保存操作數(shù)的棧文搂，另一個是保存運(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 個操作數(shù)乡恕，然后進(jìn)行計算言询，再把計算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較傲宜。
詳情見 leetcode 224 號題目。
- 在括號匹配中的應(yīng)用
借助棧來檢查表達(dá)式中的括號是否匹配夫啊，比如 {}{()}函卒。假設(shè)表達(dá)式中只包含三種括號，圓括號 ()撇眯、方括號 [] 和花括號{}报嵌，并且它們可以任意嵌套。給出一個包含三種括號的表達(dá)式字符串熊榛，如何檢查它是否合法呢锚国？
用棧來保存未匹配的左括號，從左到右依次掃描字符串玄坦。當(dāng)掃描到左括號時血筑，則將其壓入棧中；當(dāng)掃描到右括號時煎楣，從棧頂取出一個左括號豺总。如果能夠匹配，則繼續(xù)掃描剩下的字符串择懂。如果掃描的過程中喻喳，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)困曙，則說明為非法格式表伦。當(dāng)所有的括號都掃描完成之后谦去，如果棧為空，則說明字符串為合法格式蹦哼；否則哪轿，說明有未匹配的左括號，為非法格式翔怎。
詳情見 leetcode 20 號題目窃诉。
- 實(shí)現(xiàn)瀏覽器的前進(jìn)后退功能
使用兩個棧 X 和 Y，把首次瀏覽的頁面依次壓入棧 X赤套，當(dāng)點(diǎn)擊后退按鈕時飘痛，再依次從棧 X 中出棧，并將出棧的數(shù)據(jù)依次放入棧 Y容握。當(dāng)點(diǎn)擊前進(jìn)按鈕時梗掰，依次從棧 Y 中取出數(shù)據(jù)，放入棧 X 中相种。當(dāng)棧 X 中沒有數(shù)據(jù)時遣妥，那就說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)棧 Y 中沒有數(shù)據(jù)谈跛，那就說明沒有頁面可以點(diǎn)擊前進(jìn)按鈕瀏覽了羊苟。
思考
為什么函數(shù)調(diào)用要用“棧”來保存臨時變量呢感憾？用其他數(shù)據(jù)結(jié)構(gòu)不行嗎蜡励？
其實(shí)，我們不一定非要用棧來保存臨時變量阻桅，只不過如果這個函數(shù)調(diào)用符合后進(jìn)先出的特性凉倚，用棧這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，是順理成章的選擇嫂沉。
練習(xí)題
- 用數(shù)組實(shí)現(xiàn)一個順序棧
- 用鏈表實(shí)現(xiàn)一個鏈?zhǔn)綏?/li>
- 編程模擬實(shí)現(xiàn)一個瀏覽器的前進(jìn)稽寒、后退功能
