国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

當(dāng)提及“棧”這個(gè)概念，很多初學(xué)者都會(huì)很迷茫。在C語言里，我們有一個(gè)內(nèi)存區(qū)域叫做棧區(qū)。在單片機(jī)里，我們又常常聽到一個(gè)操作叫做壓棧。而在算法中，我們也有一個(gè)同名結(jié)構(gòu)叫做棧。

我常常會(huì)問自己的學(xué)生“棧”這個(gè)字的意思到底是什么?大家想到的多是客棧。我們翻翻字典也不難發(fā)現(xiàn)，棧的第一個(gè)釋義是：儲存貨物或供旅客住宿的房屋。所以客棧的想法并沒有錯(cuò)，但是這也未免太過抽象。

我們先來解釋一下在計(jì)算機(jī)領(lǐng)域什么是棧。

棧某種意義上講，它像是一個(gè)開口的盒子，先放進(jìn)去的東西總是會(huì)被后放進(jìn)去的東西壓在下面，那么如果想拿出被壓住的東西，必須要先取出頂部的東西，也就是后放進(jìn)去的東西。換個(gè)說法就是先入后出。那它有點(diǎn)像什么呢?想象一下裝在盤子里的若干張油餅。

對，他們是摞在一起的。如果想拿下面的油餅是不是要先拿開上面的呢?或許，這就是棧的根源。但是，又和“棧”這個(gè)字有什么關(guān)系呢?單純的從釋義上看，好似找不出什么關(guān)聯(lián)性。但是當(dāng)我們打開漢英詞典：

對計(jì)算機(jī)中提及的“棧”的英文愿意是stack!我們一定要記得，是一群說英語的人創(chuàng)造了計(jì)算機(jī)，也是他們研究了初的算法。那么stack又是什么意思?

注意箭頭指向的那一摞書們，和餅們的相處方式是不是很像!堆疊到一起。那個(gè)根源出來了，其實(shí)棧就是一種將數(shù)據(jù)依次“堆疊”的一種數(shù)據(jù)組織方式。

或者到這里，我們恍然大悟，哦，原來是這樣!棧還有堆疊的意思。但是，我個(gè)人更覺得這是一種初期程序員之間的交流翻譯吳繆。暫且放下這個(gè)不談，至少我們明白一件事情，在某些領(lǐng)域，如果一個(gè)詞匯很生澀，那么，不妨去查找一下他的英文愿意，或許你會(huì)有更深入的收獲。

我們在來探討下一個(gè)話題——“棧”stack，這種摞大餅大數(shù)據(jù)組織方式到底有什么用?

比如說，你有一些書，我們通常會(huì)這樣擺放：

而不是這樣：

為什么呢?當(dāng)然是第二種擺放方式不方便拿其中的某一本書�？墒窃�“棧”(stack)結(jié)構(gòu)里面，“書”就是這樣擺放的。那也就是說，“棧”(stack)不適合存放需要隨機(jī)查找的東西。那它能做什么呢?

首先說說CPU里的“堆棧”。我們可以這樣設(shè)想：一個(gè)CPU等同于一個(gè)完全沒有記憶力的人，他只知道按照一份很詳細(xì)的說明文檔(也就是程序)來一步一步做某件事情，并且，他永遠(yuǎn)不會(huì)記得之前做過什么。我們在電影里常常會(huì)看到這樣的情節(jié)，失憶癥的人常常會(huì)隨身攜帶一些本子和照片，然后按順序把發(fā)生的事情記錄下來，方便自己查閱。CPU也有這樣的需求。

在CPU里，有一種機(jī)制叫做“中斷”interrupt，就是中途插一嘴的意思。怎么插呢?比方說，你正在玩兒一個(gè)單機(jī)游戲，在更要通關(guān)的時(shí)候，外面突然有人敲門。那么是不是要把你的游戲暫停一下?然后再去開門。然后正在你去開門的路上，廚房的煤氣報(bào)警器響起，是不是要趕緊去廚房看一下是不是誤報(bào)警?確認(rèn)是誤報(bào)警后，我們是先去開門呢?還是繼續(xù)打游戲呢?對于CPU來說，也會(huì)有同樣的困惑。對于人，我們或許可以思考一下——哦，開門這件事器比較緊迫，應(yīng)該先開門。但是對于CPU來說，又如何區(qū)分緊迫度呢?這就變成了一個(gè)很麻煩的問題。我們回頭再想想“棧”，他是如何組織數(shù)據(jù)的?先入后出。玩游戲是先發(fā)生的事情，那么打斷他的事情就是更緊迫的事情，開門雖然比游戲緊迫，但是他次于煤氣報(bào)警，所以，它才是緊迫的事情。不過到現(xiàn)在也應(yīng)該注意到了。緊迫的事情往往在后產(chǎn)生，又要被優(yōu)先處理。

在CPU的中斷機(jī)制里，每當(dāng)cpu執(zhí)行的一個(gè)任務(wù)被打斷時(shí)，cpu就需要備份當(dāng)前的處理狀態(tài)，就像沒有記憶的人，總是要記筆記拍照。那么cpu怎么區(qū)分優(yōu)先次序呢?就像你吃盤子里的餅!先拿上面的。而存儲數(shù)據(jù)的過程，就像你向盤子里放餅的過程。

再說說C語言分段里的“棧區(qū)”，我們都知道，局部自動(dòng)變量分配到內(nèi)存的“棧區(qū)”，棧區(qū)里的數(shù)據(jù)組織方式也類似摞餅，每當(dāng)你調(diào)用了一個(gè)子函數(shù)，那么編譯器會(huì)將子函數(shù)里的局部變量分配到棧區(qū)的棧頂位置(與當(dāng)前函數(shù)的空間相鄰)，當(dāng)子函數(shù)在再調(diào)用另一個(gè)函數(shù)是，也是會(huì)做同樣處理。兒關(guān)于局部變量的釋放，其實(shí)本質(zhì)就是講棧頂?shù)囊粔K空間的使用權(quán)歸還回去，看起來就好像客棧一樣，來人的時(shí)候開房，走人的時(shí)候退房�；蛟S這也是stack會(huì)被翻譯成“棧”的原由。

后在來說“棧”，這種單純的邏輯結(jié)構(gòu)。它和前兩者一樣，遵循類似先入后出的數(shù)據(jù)處理規(guī)則。

那這個(gè)“盒子“什么時(shí)候會(huì)用到呢?典型的例子，就是迷宮算法(具體細(xì)節(jié)可以自己搜索一下)，我們可以用棧來存放已經(jīng)走過的有效路線。也或者利用棧來模擬局部變量分配，實(shí)現(xiàn)將遞歸算法轉(zhuǎn)換為非遞歸。也或者利用棧來優(yōu)化，自己的程序處理邏輯，在實(shí)際問題解決中，如果你涉及到了臨時(shí)保存數(shù)據(jù)，那么你可以嘗試考慮一下使用棧，或許可以讓自己的程序在邏輯上變得更加清晰明了。

簡單的總結(jié)一下：所謂“棧”，其實(shí)就是一本 相互堆疊的便簽兒。我們可以逐次備份自己要保存的信息，然后在反向依次處理。