棧 是一種 “操作受限”的線性表，只允許在一端插入和刪除數(shù)據(jù)。

從功能是上來(lái)說(shuō)，數(shù)組和鏈表確實(shí)可以替代棧，但是特定的數(shù)據(jù)結(jié)構(gòu)是對(duì)特定場(chǎng)景的抽象，而且，數(shù)組或鏈表暴露了太多的操作接口，操作上的確靈活自由，但使用時(shí)就比較不可控，自然也就更容易出錯(cuò)。

當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足后進(jìn)先出、先進(jìn)后出的特性，這時(shí)我們就應(yīng)該首選“棧”這種數(shù)據(jù)結(jié)構(gòu)。

棧的應(yīng)用：

函數(shù)調(diào)用，操作系統(tǒng)給每個(gè)線程分配了一塊獨(dú)立的內(nèi)存空間，這個(gè)內(nèi)存被組織成“棧”這種結(jié)構(gòu)，用來(lái)存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變量。每進(jìn)入一個(gè)函數(shù)，就會(huì)將臨時(shí)變量作為一個(gè)棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個(gè)函數(shù)對(duì)應(yīng)的棧幀出棧。

表達(dá)式求值

比如 3 + 5 * 8 - 6，編譯器通過(guò)兩個(gè)棧來(lái)實(shí)現(xiàn)，其中一個(gè)保存操作數(shù)的棧，另一個(gè)是保存運(yùn)算符的棧，從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較。

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

image.jpeg

在括號(hào)匹配中的應(yīng)用

假設(shè)表達(dá)式中只包含三種括號(hào)，圓括號(hào)()、方括號(hào)[]和花括號(hào){}，并且他們可以任意套裝。比如，{[{}]}為合法格式，而 {[}()] 或 [({)]}為不合法格式，現(xiàn)在檢查其合法性。

用棧來(lái)保存未匹配的左括號(hào)，從左到右依次掃描字符串。當(dāng)掃描到左括號(hào)時(shí)，則將其壓入棧中；當(dāng)掃描到右括號(hào)時(shí)，從棧頂取出一個(gè)左括號(hào)，如果能夠匹配，比如 ) 跟 ( 匹配， [ 跟 ] 匹配，則繼續(xù)掃描剩下的字符串，如果在掃描的過(guò)程中，遇到不能配對(duì)的右括號(hào)，或者棧中沒(méi)有數(shù)據(jù)，則說(shuō)明為非法格式。

當(dāng)所有的括號(hào)都掃描完成之后，如果棧為空，則說(shuō)明字符串為合法格式；否則，說(shuō)明有未匹配的左括號(hào)，為非法格式。

瀏覽器的前進(jìn)和后退功能

使用兩個(gè)棧，X 和 Y， 把首次瀏覽的頁(yè)面一次壓入棧 X， 當(dāng)點(diǎn)擊后退按鈕時(shí)，再一次從棧 X 中出棧，并將出棧的數(shù)據(jù)一次放入棧 Y。 當(dāng)我們點(diǎn)擊前進(jìn)按鈕時(shí)，依次從棧 Y 中取出數(shù)據(jù)，放入棧 X 中。當(dāng)棧 X 中沒(méi)有數(shù)據(jù)時(shí)，那就說(shuō)明沒(méi)有頁(yè)面可以繼續(xù)后退瀏覽了，當(dāng)棧 Y 中沒(méi)有數(shù)據(jù)時(shí)，說(shuō)明沒(méi)有頁(yè)面可以點(diǎn)擊前進(jìn)按鈕瀏覽了。

比如，順序查看了 a, b, c 三個(gè)頁(yè)面，依次把 a, b, c 壓入棧，這個(gè)時(shí)候，兩個(gè)棧的數(shù)據(jù)就是這個(gè)樣子：

image.jpeg

當(dāng)通過(guò)瀏覽器的后退按鈕，從頁(yè)面 c 后退到頁(yè)面 a 之后，就依次把 c 和 b 從棧 X 中彈出，并且依次放入到棧 Y。 這個(gè)時(shí)候，兩個(gè)棧的數(shù)據(jù)就是這個(gè)樣子：

image.jpeg

這個(gè)時(shí)候，如果又想看頁(yè)面b，于是又點(diǎn)擊前進(jìn)按鈕回到b頁(yè)面，就把b從棧Y中出棧，放入棧X中，此時(shí)，兩個(gè)棧的數(shù)據(jù)就是這個(gè)樣子：

image.jpeg

這個(gè)時(shí)候，通過(guò)頁(yè)面b又跳轉(zhuǎn)到新的頁(yè)面d了，頁(yè)面 c 就無(wú)法再通過(guò) 前進(jìn)、后退按鈕重復(fù)查看了，所以需要清空棧 Y。此時(shí)兩個(gè)棧的數(shù)據(jù)是這個(gè)樣子：

image.jpeg

總的來(lái)說(shuō)，棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，只支持入棧和出棧操作，后進(jìn)先出是它最大的特點(diǎn)。棧既可以通過(guò)數(shù)組實(shí)現(xiàn)，也可以通過(guò)鏈表來(lái)實(shí)現(xiàn)。不管是基于數(shù)組還是鏈表，入棧、出棧的時(shí)間復(fù)雜度都為 O(1)。

總結(jié)

以上是生活随笔為你收集整理的python数据结构与算法第六讲_Python 学习 -- 数据结构与算法 （六）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。