導(dǎo)言：

在計(jì)算機(jī)發(fā)明之初是為了計(jì)算，所以叫計(jì)算機(jī)，對(duì)我們給定的一個(gè)算式，然后給定的一套規(guī)則 加，減，乘，除，等，它就可以自己進(jìn)行計(jì)算了，然后返回一個(gè)結(jié)果給我們

對(duì)于一般的算式 ： 2+3+4 很顯然，從左往右依次掃描，依次相加很簡單的計(jì)算出來，因?yàn)樗鼈兪峭?jí)運(yùn)算，可以很簡單的做到

但是，常見的運(yùn)算不只是 加法，還有乘除等，它們的優(yōu)先級(jí)都是要高于加法的，如： 3+6*4/9? ，如果依次掃描，很顯然6和4的乘法優(yōu)先級(jí)更高，不能先3和6進(jìn)行加法

當(dāng)然，有問題的提出就有問題的解決：可以使用后綴表達(dá)式和棧結(jié)合來應(yīng)對(duì)復(fù)雜的計(jì)算

一.簡述棧

什么是棧？

棧 (Stack)是操作系統(tǒng)在建立某個(gè)進(jìn)程時(shí)或者線程（在支持多線程的操作系統(tǒng)中是線程）為這個(gè)線程建立的存儲(chǔ)區(qū)域，該區(qū)域具有FILO的特性，在編譯的時(shí)候可以指定需要的Stack的大小

棧的特點(diǎn)：先進(jìn)后出 ，即Frist IN Last Out（FILO）

棧這種數(shù)據(jù)結(jié)構(gòu)就特別適合解決導(dǎo)言提出來的那種問題，對(duì)于復(fù)雜的計(jì)算，算式中帶有優(yōu)先級(jí)的符號(hào)，我們可以使用棧存儲(chǔ)后綴表達(dá)式來計(jì)算

既然要用到后綴表達(dá)式，那么我們就需要把我們熟知的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式才能計(jì)算

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

?我們這里使用的中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的方法是，補(bǔ)填括號(hào)，如果運(yùn)算有括號(hào)的部分就不需要自己添加了，要是無括號(hào)就需要添加

差不多有幾個(gè)符號(hào)，最后填完括號(hào)后就是有幾個(gè)括號(hào)，符號(hào)數(shù)和括號(hào)數(shù)對(duì)應(yīng)

然后把符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)外面，前綴和后綴表達(dá)式都是這樣的，自己可以試試轉(zhuǎn)換前綴表達(dá)式

最后要注意的就是，前后綴表達(dá)式是沒有括號(hào)的，所以最后一步是去括號(hào)（即使中綴表達(dá)式自帶的括號(hào)一樣去掉）

棧和后綴表達(dá)式的結(jié)合計(jì)算

棧在這里是扮演的存儲(chǔ)角色，我們在計(jì)算的時(shí)候會(huì)從左往右的依次進(jìn)行入棧操作，是數(shù)字就入棧，是運(yùn)算符號(hào)我們就需要從棧頂拿出兩個(gè)元素計(jì)算，

但是記住，是有順序的，棧頂?shù)脑胤庞疫?，后面出來的元素放左邊，符?hào)放中間就可以計(jì)算了

棧的特點(diǎn)是先進(jìn)的后出，后進(jìn)的先出，不存在在棧中間的數(shù)據(jù)先出來的情況，所以依次出棧就能保證數(shù)據(jù)運(yùn)算時(shí)邏輯順序不會(huì)發(fā)生改變

我們接下來簡單舉例來看看這個(gè)運(yùn)算：

?這就是我們使用棧結(jié)構(gòu)來解決的導(dǎo)言中的比較復(fù)雜運(yùn)算，這里我們就能很明顯的知道棧的結(jié)構(gòu)特點(diǎn)

棧結(jié)構(gòu)使用最多的還是計(jì)算機(jī)底層的運(yùn)算，比如，操作系統(tǒng)的中斷系統(tǒng)中，操作系統(tǒng)做的斷點(diǎn)記錄是棧結(jié)構(gòu)存儲(chǔ)的，還有函數(shù)和主函數(shù)的調(diào)用方式，遞歸的實(shí)現(xiàn)，都是棧機(jī)制

對(duì)應(yīng)的棧操作就兩個(gè)：push （入棧），pop（入棧）

不管是出棧還是入棧它們都是原子操作，可以交叉的使用邊出棧邊入棧，也可以邊入棧邊出棧，但是在宏觀上它們一定是有序的，不會(huì)有棧頂元素未出棧，棧底元素已出棧的情況

?二.棧的順序存儲(chǔ)實(shí)現(xiàn)

?第一種：基于結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)

棧的順序存儲(chǔ)通常是一個(gè)數(shù)組和一個(gè)記錄棧頂元素的變量實(shí)現(xiàn)的

?這里我們使用的是int型數(shù)組，存儲(chǔ)整型數(shù)據(jù)

top就是我們有數(shù)據(jù)數(shù)組的最大下標(biāo)

?入棧的時(shí)候需要檢查一下我們的棧是否為滿的，如果不是滿地還有空間那么就可以入棧，入棧的時(shí)候由于我們選用的數(shù)組存放，所以只需要把下標(biāo)后移一個(gè)就夠了

然后還要對(duì)記錄棧頂?shù)脑丶右?，這里代碼中我們其實(shí)是兩步一起做了的

?我們在出戰(zhàn)的時(shí)候是有返回值的，一定要記得類型要和入棧的數(shù)據(jù)類型匹配上

然后就是出棧也需要判斷棧是不是還有元素，沒有就是出不了棧的

出棧完成了以后也需要把記錄棧頂元素的變量減一

利用一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧

?這是一個(gè)經(jīng)典的棧空間劃分問題，我們在拿到問題之后可能很多人都想到的是對(duì)半分，一半數(shù)組構(gòu)成一個(gè)棧，理論上可以，但是實(shí)際上的開發(fā)不行，

因?yàn)閮蓚€(gè)棧的進(jìn)入順序其實(shí)是不一樣的，那么就有可能會(huì)導(dǎo)致有一個(gè)棧已經(jīng)滿了，另外的一個(gè)棧還有大量空間，為了充分利用數(shù)組空間，對(duì)半分劃分兩個(gè)?？隙ㄊ遣缓侠淼?/p>

后來我們想到可以使用數(shù)組的第一元素和最后一個(gè)元素作為兩個(gè)棧的棧底，然后都向中間靠來存放數(shù)據(jù)，不在是對(duì)半分，當(dāng)兩個(gè)棧的棧頂指針相遇的時(shí)候就是棧滿的時(shí)候

上面就是使用一個(gè)數(shù)組實(shí)現(xiàn)雙棧的偽代碼，主要是多了一個(gè)tag標(biāo)記，它的意思是用來選擇要操作那個(gè)棧的，我們現(xiàn)在不是有了兩個(gè)棧嘛

包括入棧和出棧都要選擇，如果選擇錯(cuò)了很顯然拿不到我們想要的結(jié)果的

使用這種方式構(gòu)建的雙棧有很高的利用率，不存在有內(nèi)碎片的情況。?

?第二種：基于鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

棧的鏈?zhǔn)酱鎯?chǔ)其實(shí)就是一個(gè)單鏈表，叫做鏈棧，插入和刪除只能在棧頂實(shí)現(xiàn)，那么鏈表的top指針指向那一頭呢？

我們可以先構(gòu)造從鏈表的尾部開始做 top指針，插入的時(shí)候就在尾部連接鏈表的新結(jié)點(diǎn)，但是刪除就有問題了，我們知道鏈表實(shí)現(xiàn)的棧是單鏈表它是沒有回頭指針的

也就是說，它只能找到它的下一個(gè)結(jié)點(diǎn)，但是找不到它的上一個(gè)結(jié)點(diǎn)，單鏈表有 Next指針，但是沒有 last指針，在刪除的時(shí)候肯定要回到上一個(gè)結(jié)點(diǎn)做尾結(jié)點(diǎn)，所以鏈表的尾部被pass掉

再來看看使用鏈表的頭部做top指針，每新來的結(jié)點(diǎn)都直接連接到已有的鏈表的后面，可以實(shí)現(xiàn)，刪除一個(gè)結(jié)點(diǎn)也就是頭部結(jié)點(diǎn)的next不需要了，連接到下下個(gè)結(jié)點(diǎn)去，可以實(shí)現(xiàn)

所以我們選用頭部結(jié)點(diǎn)來做top指針，這里我們需要注意的是我們要專門構(gòu)造一個(gè)頭部結(jié)點(diǎn)，它不存放數(shù)據(jù)，只用來連接新數(shù)據(jù)和刪除數(shù)據(jù)，它不管怎么更改始終是鏈表的第一個(gè)結(jié)點(diǎn)，使用這個(gè)結(jié)點(diǎn)來做 top指針

?這里的head頭結(jié)點(diǎn)就可以充當(dāng)top指針

我們再來看看對(duì)鏈表結(jié)構(gòu)體的定義，由于鏈表是動(dòng)態(tài)申請(qǐng)，故而沒有固定大小

?從結(jié)構(gòu)體種我們可以看到，有裝數(shù)據(jù)的Data類型，還有一個(gè)結(jié)構(gòu)體指針，指向的是下一個(gè)結(jié)構(gòu)體，利用鏈表來做棧結(jié)構(gòu)首先要申請(qǐng)一個(gè)頭結(jié)點(diǎn)用于做top指針，這一步也可以叫初始化，

?這里式偽代碼實(shí)現(xiàn)的鏈?zhǔn)綏＝Y(jié)構(gòu)實(shí)現(xiàn)入棧和出棧

入棧的時(shí)候要注意每次申請(qǐng)一個(gè)新的結(jié)點(diǎn)，鏈表的插入實(shí)際上是結(jié)點(diǎn)的插入，結(jié)點(diǎn)上帶了數(shù)據(jù)和下一個(gè)結(jié)點(diǎn)的位置

因?yàn)殒準(zhǔn)酱鎯?chǔ)，它的大小是在不斷地申請(qǐng)中產(chǎn)生的所以它是沒有棧滿這個(gè)問題的，可以說只要操作系統(tǒng)給你多少內(nèi)存，你可以一直申請(qǐng)到撐爆它。

然后就是出棧，出棧是需要檢查一下有沒有結(jié)點(diǎn)的，可能沒有插入，在出棧的時(shí)候需要釋放剛剛的內(nèi)存，所以需要一個(gè)指針還沒執(zhí)行斷鏈的時(shí)候就指向它

等斷鏈以后，數(shù)據(jù)也備份到返回的臨時(shí)變量了，就可以釋放出棧元素原來所占用的內(nèi)存了，有申請(qǐng)有釋放，主打一個(gè)規(guī)范

?入棧圖示：

?出棧圖示：

?三.棧的簡單應(yīng)用

我們在簡述棧的時(shí)候就已經(jīng)了解過了，對(duì)于中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的方法，當(dāng)時(shí)我們使用的是加括號(hào)，然后通過我們?nèi)丝衫斫獾姆绞絹斫鉀Q的，

加括號(hào)可以快速的把中綴表達(dá)式轉(zhuǎn)換為前后綴表達(dá)式，但是這是我們?nèi)瞬拍茏龅竭@么快，但是機(jī)器呢？

對(duì)于計(jì)算機(jī)，他無法根據(jù)此規(guī)則加上相應(yīng)的括號(hào)，然后移動(dòng)符號(hào)，最后去掉括號(hào)，但是計(jì)算機(jī)它有一套自己的實(shí)現(xiàn)方法，也是通過棧來實(shí)現(xiàn)的

?通過上面的計(jì)算，利用棧的轉(zhuǎn)存就可以很輕松的計(jì)算出后綴表達(dá)式，當(dāng)然他必須要滿足相應(yīng)的一些規(guī)則：

中綴表達(dá)式從左向右掃描

• 遇到運(yùn)算數(shù)字就直接輸出
• 左括號(hào)在棧外的時(shí)候優(yōu)先級(jí)最高，直接壓入棧中，在棧內(nèi)優(yōu)先級(jí)最低
• 遇到右括號(hào)后，直接把左括號(hào)上的符號(hào)依次出棧，但是左右括號(hào)不需要再帶上了
• 其它運(yùn)算符，只要優(yōu)先級(jí)高的就入棧，比棧內(nèi)的低的，棧內(nèi)的彈出，然后與棧內(nèi)繼續(xù)比較，同級(jí)的也是棧內(nèi)的先彈出，然后棧外的入棧
• 對(duì)象掃描完以后，需要把棧內(nèi)的殘余的運(yùn)算符順序輸出

小結(jié)：

上面的操作并不是棧最常用的操作，棧作為最早出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)之一，其特點(diǎn)被大量的用在了底層中，操作系統(tǒng)中棧內(nèi)存是不可或缺的一份子，它對(duì)斷點(diǎn)的記錄有著離奇好的效果，

廣泛用于操作系統(tǒng)的斷點(diǎn)記錄，函數(shù)回溯參數(shù)還原

包括整個(gè)遞歸思想都是在棧機(jī)制上建立起來的，如果沒有棧機(jī)制，遞歸的思想可能很難被實(shí)現(xiàn)出來

圖的深度優(yōu)先探索，都需要棧來記錄它剛剛經(jīng)過的地方，在道路不可達(dá)的時(shí)候，需要回到棧記錄原來的地方

回溯算法等等

-

-

-

-

-

-

?文章來源地址http://www.zghlxwxcb.cn/news/detail-462299.html

博客編輯于

---------------------浙江大學(xué)陳越老師《數(shù)據(jù)結(jié)構(gòu)與算法》

?

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