什么(me)是棧？
時(shi)間：2018-09-26 ; 來源：未知
當提及(ji)“棧”這個概念，很多初學者(zhe)都會很迷茫。在(zai)C語言里，我(wo)們有一(yi)(yi)個內存區域叫做(zuo)棧區。在(zai)單片(pian)機里，我(wo)們又(you)常(chang)常(chang)聽到(dao)一(yi)(yi)個操作叫做(zuo)壓棧。而(er)在(zai)算法(fa)中(zhong)，我(wo)們也有一(yi)(yi)個同名結構叫做(zuo)棧。
我常常會問自(zi)己的(de)學生“棧”這個字的(de)意思(si)到底(di)是什么?大(da)家想(xiang)到的(de)多是客棧。我們翻翻字典也不(bu)難發現(xian)，棧的(de)第一個釋(shi)義是：儲存貨物或供旅客住宿(su)的(de)房(fang)屋。所以客棧的(de)想(xiang)法并(bing)沒有(you)錯(cuo)，但是這也未免太過抽象。
我們先(xian)來解釋一(yi)下在計(ji)算(suan)機領域什么是棧。
棧某種意(yi)義上講，它像是一個(ge)(ge)開口(kou)的盒子(zi)，先(xian)(xian)放(fang)(fang)進去的東西(xi)總是會被(bei)后(hou)放(fang)(fang)進去的東西(xi)壓在下面，那么如果想拿出(chu)被(bei)壓住的東西(xi)，必須要先(xian)(xian)取(qu)出(chu)頂部的東西(xi)，也(ye)就(jiu)是后(hou)放(fang)(fang)進去的東西(xi)。換個(ge)(ge)說法(fa)就(jiu)是先(xian)(xian)入后(hou)出(chu)。那它有(you)點像什么呢(ni)?想象一下裝在盤子(zi)里的若干張油餅。
對，他們(men)是(shi)(shi)摞在一起的。如(ru)果想(xiang)拿下面的油餅(bing)是(shi)(shi)不是(shi)(shi)要先拿開上面的呢?或許(xu)，這就是(shi)(shi)棧的根(gen)源(yuan)。但是(shi)(shi)，又和“棧”這個字有什(shen)(shen)么關系呢?單純的從釋義上看，好似找不出什(shen)(shen)么關聯性。但是(shi)(shi)當我們(men)打(da)開漢英詞典：
對計算(suan)機(ji)中提及的“棧”的英(ying)文(wen)愿意是stack!我們(men)一定(ding)要記得，是一群說英(ying)語的人創(chuang)造了計算(suan)機(ji)，也(ye)是他們(men)研究了初(chu)的算(suan)法。那么(me)stack又(you)是什么(me)意思?
注(zhu)意箭頭指向的那一摞(luo)書(shu)們，和餅(bing)們的相(xiang)處方式是不(bu)是很(hen)像!堆(dui)疊(die)(die)到一起。那個根源出(chu)來(lai)了，其實棧就是一種將數據依次“堆(dui)疊(die)(die)”的一種數據組織方式。
或者到這(zhe)里，我們(men)恍然大悟，哦，原(yuan)來是(shi)這(zhe)樣(yang)!棧還有堆疊的意(yi)思(si)。但是(shi)，我個人(ren)更(geng)覺得這(zhe)是(shi)一(yi)(yi)種(zhong)初(chu)期程序員(yuan)之間的交流翻譯(yi)吳繆。暫且放下這(zhe)個不(bu)(bu)談，至少我們(men)明(ming)白(bai)一(yi)(yi)件(jian)事情，在某些領(ling)域，如果(guo)一(yi)(yi)個詞匯(hui)很生澀，那么，不(bu)(bu)妨去(qu)查找一(yi)(yi)下他(ta)的英文愿(yuan)意(yi)，或許你(ni)會有更(geng)深入(ru)的收(shou)獲。
我們在來探討下一個(ge)話題——“棧”stack，這種摞大餅大數據組織方式到底(di)有什(shen)么用?
比如說，你有(you)一些書(shu)，我們(men)通常會這樣擺放：
而不是這樣：
為什(shen)么呢?當(dang)然(ran)是第二種擺放(fang)方式不方便拿(na)其中的某一本書(shu)。可(ke)是在“棧”(stack)結構里面(mian)，“書(shu)”就是這(zhe)樣擺放(fang)的。那(nei)也就是說，“棧”(stack)不適合存放(fang)需要隨機查(cha)找(zhao)的東西(xi)。那(nei)它能做什(shen)么呢?
首先說(shuo)說(shuo)CPU里(li)的(de)“堆棧(zhan)”。我(wo)們可(ke)以這樣設想：一(yi)個CPU等同于一(yi)個完全沒有記(ji)憶力的(de)人(ren)，他只(zhi)知道按照(zhao)一(yi)份很詳細的(de)說(shuo)明文檔(也就是程序(xu)(xu))來(lai)一(yi)步一(yi)步做某件事(shi)情(qing)(qing)，并(bing)且，他永(yong)遠不會記(ji)得(de)之前做過什(shen)么。我(wo)們在(zai)電影里(li)常(chang)常(chang)會看到(dao)這樣的(de)情(qing)(qing)節，失(shi)憶癥的(de)人(ren)常(chang)常(chang)會隨(sui)身攜帶一(yi)些本(ben)子和照(zhao)片(pian)，然后按順(shun)序(xu)(xu)把發生的(de)事(shi)情(qing)(qing)記(ji)錄下來(lai)，方便自己查閱。CPU也有這樣的(de)需求。
在CPU里，有一(yi)種機制叫做“中斷”interrupt，就(jiu)是(shi)中途插一(yi)嘴的(de)意思(si)。怎么(me)插呢?比(bi)方說(shuo)(shuo)，你正在玩兒一(yi)個單(dan)機游(you)戲(xi)，在更要(yao)通關的(de)時候，外面突然有人敲門。那么(me)是(shi)不(bu)是(shi)要(yao)把你的(de)游(you)戲(xi)暫(zan)停一(yi)下(xia)(xia)?然后再(zai)去(qu)開(kai)門。然后正在你去(qu)開(kai)門的(de)路(lu)上，廚房的(de)煤(mei)氣(qi)報(bao)警(jing)器響起(qi)，是(shi)不(bu)是(shi)要(yao)趕緊去(qu)廚房看一(yi)下(xia)(xia)是(shi)不(bu)是(shi)誤報(bao)警(jing)?確認是(shi)誤報(bao)警(jing)后，我們是(shi)先(xian)(xian)(xian)(xian)去(qu)開(kai)門呢?還(huan)是(shi)繼續打游(you)戲(xi)呢?對(dui)(dui)于(yu)CPU來說(shuo)(shuo)，也(ye)會有同樣的(de)困惑。對(dui)(dui)于(yu)人，我們或許(xu)可(ke)以(yi)思(si)考(kao)一(yi)下(xia)(xia)——哦，開(kai)門這件事(shi)器比(bi)較(jiao)緊迫(po)(po)，應(ying)該(gai)先(xian)(xian)(xian)(xian)開(kai)門。但是(shi)對(dui)(dui)于(yu)CPU來說(shuo)(shuo)，又(you)如何區分緊迫(po)(po)度呢?這就(jiu)變成(cheng)了一(yi)個很(hen)麻煩的(de)問題。我們回頭(tou)再(zai)想(xiang)想(xiang)“棧(zhan)”，他是(shi)如何組(zu)織數(shu)據的(de)?先(xian)(xian)(xian)(xian)入后出。玩游(you)戲(xi)是(shi)先(xian)(xian)(xian)(xian)發生的(de)事(shi)情(qing)(qing)，那么(me)打斷他的(de)事(shi)情(qing)(qing)就(jiu)是(shi)更緊迫(po)(po)的(de)事(shi)情(qing)(qing)，開(kai)門雖然比(bi)游(you)戲(xi)緊迫(po)(po)，但是(shi)他次于(yu)煤(mei)氣(qi)報(bao)警(jing)，所以(yi)，它(ta)才是(shi)緊迫(po)(po)的(de)事(shi)情(qing)(qing)。不(bu)過到現(xian)在也(ye)應(ying)該(gai)注意到了。緊迫(po)(po)的(de)事(shi)情(qing)(qing)往(wang)往(wang)在后產生，又(you)要(yao)被(bei)優先(xian)(xian)(xian)(xian)處理。
在CPU的(de)(de)中斷機制里，每當cpu執行的(de)(de)一個(ge)任務被打斷時，cpu就需要備份(fen)當前的(de)(de)處理狀(zhuang)態，就像(xiang)(xiang)沒有記憶的(de)(de)人，總是(shi)要記筆記拍(pai)照。那么cpu怎(zen)么區分優先次序呢?就像(xiang)(xiang)你吃盤子里的(de)(de)餅(bing)!先拿上面的(de)(de)。而存儲(chu)數據的(de)(de)過程，就像(xiang)(xiang)你向盤子里放餅(bing)的(de)(de)過程。
再(zai)說(shuo)說(shuo)C語言分段里的(de)(de)(de)(de)(de)“棧(zhan)區”，我們都知道，局(ju)部(bu)自動變(bian)量(liang)分配到(dao)內(nei)存的(de)(de)(de)(de)(de)“棧(zhan)區”，棧(zhan)區里的(de)(de)(de)(de)(de)數(shu)據組織方式也類似摞餅，每(mei)當你調(diao)用(yong)了(le)一(yi)個子(zi)函(han)(han)數(shu)，那么編譯(yi)器會(hui)將(jiang)子(zi)函(han)(han)數(shu)里的(de)(de)(de)(de)(de)局(ju)部(bu)變(bian)量(liang)分配到(dao)棧(zhan)區的(de)(de)(de)(de)(de)棧(zhan)頂(ding)位置(與當前函(han)(han)數(shu)的(de)(de)(de)(de)(de)空(kong)間(jian)相(xiang)鄰)，當子(zi)函(han)(han)數(shu)在再(zai)調(diao)用(yong)另一(yi)個函(han)(han)數(shu)是，也是會(hui)做同樣處理(li)。兒關于局(ju)部(bu)變(bian)量(liang)的(de)(de)(de)(de)(de)釋放，其實本(ben)質就是講棧(zhan)頂(ding)的(de)(de)(de)(de)(de)一(yi)塊空(kong)間(jian)的(de)(de)(de)(de)(de)使用(yong)權歸還回去，看起來就好像客棧(zhan)一(yi)樣，來人(ren)的(de)(de)(de)(de)(de)時候開(kai)房(fang)，走人(ren)的(de)(de)(de)(de)(de)時候退房(fang)。或許這也是stack會(hui)被翻(fan)譯(yi)成“棧(zhan)”的(de)(de)(de)(de)(de)原由。
后(hou)在來說“棧”，這種單純的邏輯結(jie)構。它(ta)和前兩者一樣，遵(zun)循類似(si)先入后(hou)出的數據處理規則(ze)。
那(nei)這個(ge)“盒子“什么時候(hou)會用到(dao)呢?典型的例(li)子，就(jiu)是迷(mi)宮算(suan)法(具體細節可以(yi)自(zi)己(ji)搜索一下(xia))，我們可以(yi)用棧(zhan)來(lai)(lai)存放已經(jing)走(zou)過的有效路線。也(ye)或者(zhe)利(li)用棧(zhan)來(lai)(lai)模擬(ni)局部變(bian)量(liang)分(fen)配，實(shi)現(xian)將遞歸算(suan)法轉換(huan)為非遞歸。也(ye)或者(zhe)利(li)用棧(zhan)來(lai)(lai)優化，自(zi)己(ji)的程序處理邏(luo)輯(ji)(ji)，在(zai)實(shi)際(ji)問題解決中，如果你(ni)涉及到(dao)了(le)臨時保存數據，那(nei)么你(ni)可以(yi)嘗試考(kao)慮一下(xia)使用棧(zhan)，或許可以(yi)讓自(zi)己(ji)的程序在(zai)邏(luo)輯(ji)(ji)上變(bian)得更(geng)加清晰明了(le)。
簡單的總結(jie)一(yi)下：所謂“棧(zhan)”，其實(shi)就是(shi)一(yi)本 相互堆疊的便(bian)簽兒(er)。我們可(ke)以逐(zhu)次備份自(zi)己要保存的信(xin)息，然后在反(fan)向依(yi)次處理。
