栈（Stack），轻松解决数制转换和括号匹配问题！
生活随笔
收集整理的這篇文章主要介紹了
栈（Stack），轻松解决数制转换和括号匹配问题！
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
http://data.biancheng.net/view/9.html
棧，線性表的一種特殊的存儲(chǔ)結(jié)構(gòu)。與學(xué)習(xí)過(guò)的線性表的不同之處在于棧只能從表的固定一端對(duì)數(shù)據(jù)進(jìn)行插入和刪除操作，另一端是封死的。
圖1 棧結(jié)構(gòu)示意圖 由于棧只有一邊開(kāi)口存取數(shù)據(jù)，稱開(kāi)口的那一端為“棧頂”，封死的那一端為“棧底”（類似于盛水的木桶，從哪進(jìn)去的最后還得從哪出來(lái)）。棧的“先進(jìn)后出”原則
使用棧存儲(chǔ)數(shù)據(jù)元素，對(duì)數(shù)據(jù)元素的 “存” 和 “取” 有嚴(yán)格的規(guī)定：數(shù)據(jù)按一定的順序存儲(chǔ)到棧中，當(dāng)需要調(diào)取棧中某數(shù)據(jù)元素時(shí)，需要將在該數(shù)據(jù)元素之后進(jìn)棧的先出棧，該數(shù)據(jù)元素才能從棧中提取出來(lái)。如圖 1 ，棧中存放了 4 個(gè)數(shù)據(jù)元素，進(jìn)棧的順序是 A 先進(jìn)棧，然后 B 進(jìn)，然后 C 進(jìn)，最后 D 進(jìn)棧；當(dāng)需要調(diào)取 A 時(shí)，首先 D 出棧，然后 C 出棧，然后 B 出棧，最后 A 才能出棧被調(diào)用。
就好比只有一個(gè)門(mén)的車(chē)庫(kù)（每次僅允許一輛車(chē)通過(guò)），每輛車(chē)好比一個(gè)數(shù)據(jù)元素，只有離門(mén)最近的車(chē)先開(kāi)出來(lái)，里邊的車(chē)才能出來(lái)；最里邊的車(chē)是最先開(kāi)進(jìn)去的，注定要最后出來(lái)。
棧操作數(shù)據(jù)元素的方法
棧操作數(shù)據(jù)元素只有兩種動(dòng)作：棧的兩種表示方式
既然棧也是線性表，那么它就同樣有線性表的兩種表示形式： 順序棧 ?和? 鏈?zhǔn)綏?/span> （簡(jiǎn)稱 “鏈棧” ）。兩者的區(qū)別在于存儲(chǔ)的數(shù)據(jù)元素在物理結(jié)構(gòu)上是否是相互緊挨著的。順序棧存儲(chǔ)元素預(yù)先申請(qǐng)連續(xù)的存儲(chǔ)單元；鏈棧需要即申請(qǐng)，數(shù)據(jù)元素不緊挨著。
棧的“上溢”和“下溢”
棧存儲(chǔ)結(jié)構(gòu)調(diào)取棧中數(shù)據(jù)元素時(shí)，要避免出現(xiàn)“上溢”和“下溢”的情況：
“上溢”：在棧已經(jīng)存滿數(shù)據(jù)元素的情況下，如果繼續(xù)向棧內(nèi)存入數(shù)據(jù)，棧存儲(chǔ)就會(huì)出錯(cuò)。
“下溢”：在棧內(nèi)為空的狀態(tài)下，如果對(duì)棧繼續(xù)進(jìn)行取數(shù)據(jù)的操作，就會(huì)出錯(cuò)。
棧的“上溢”和“下溢”，可以總結(jié)為：棧滿還存會(huì)“上溢”，棧空再取會(huì)“下溢”。
對(duì)于棧的兩種表示方式來(lái)說(shuō)，順序棧兩種情況都有可能發(fā)生；而鏈棧由于“隨時(shí)需要，隨時(shí)申請(qǐng)空間”的存儲(chǔ)結(jié)構(gòu)，不會(huì)出現(xiàn)“上溢”的情況。
順序棧
順序棧的實(shí)現(xiàn)采用的是數(shù)組。在順序棧中設(shè)定一個(gè)隨時(shí)指向棧頂元素的變量（一般命名為 top ），當(dāng) top 的值為 -1 時(shí)，說(shuō)明數(shù)組中沒(méi)有數(shù)據(jù)，即棧中沒(méi)有數(shù)據(jù)元素，為 “空棧” ；只要數(shù)據(jù)元素進(jìn)棧，top 就加 1 ；數(shù)據(jù)元素出棧， top 就減 1 。
例如，使用順序棧的存儲(chǔ)結(jié)構(gòu)將（’a’,’b’,’c’,’d’）四個(gè)元素逐個(gè)壓棧并輸出棧頂元素。
實(shí)現(xiàn)代碼：
彈棧元素：c
彈棧元素：b
彈棧元素：a
空棧
鏈棧
鏈棧，用線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)。鏈棧一般不需要?jiǎng)?chuàng)建頭結(jié)點(diǎn)，頭結(jié)點(diǎn)會(huì)增加程序的復(fù)雜性，只需要?jiǎng)?chuàng)建一個(gè)頭指針就可以了。
用鏈表表示棧時(shí)，用鏈表頭結(jié)點(diǎn)的一端作為棧的棧頂端，這樣做的好處是當(dāng)數(shù)據(jù)元素壓棧或者彈棧時(shí)，直接使用頭指針就可以完成，不需要增設(shè)額外的指針。例如，用鏈棧實(shí)現(xiàn)將（’a’,’b’,’c’,’d’）四個(gè)數(shù)據(jù)元素壓棧，再依次彈棧：
彈棧元素：c 棧頂元素：b
彈棧元素：b 棧頂元素：a
彈棧元素：a 棧已空
棧內(nèi)沒(méi)有元素
棧的實(shí)際應(yīng)用
實(shí)際生活中，使用手機(jī)（無(wú)論是 iPhone 還是安卓）時(shí)，屏幕頁(yè)面的跳轉(zhuǎn)使用的就是棧。當(dāng)你選擇換一個(gè)頁(yè)面瀏覽時(shí)，之前的頁(yè)面被存儲(chǔ)到棧中；每次做回退操作時(shí)，會(huì)回到上一個(gè)頁(yè)面，這是進(jìn)棧的頁(yè)面逐個(gè)出棧的效果。另外，在求 n！ 時(shí)，有一種算法會(huì)涉及到函數(shù)的遞歸（函數(shù)自己調(diào)用自己的過(guò)程），這個(gè)過(guò)程的底層實(shí)現(xiàn)就用到了棧。
除此之外，數(shù)制轉(zhuǎn)換和括號(hào)匹配問(wèn)題，也可以用棧來(lái)解決。
數(shù)制轉(zhuǎn)換
實(shí)際生活中主要使用 10 進(jìn)制，而計(jì)算機(jī)只認(rèn)識(shí) 2 進(jìn)制，在解決數(shù)制轉(zhuǎn)換的問(wèn)題上使用棧結(jié)構(gòu)會(huì)事半功倍。例如，將十進(jìn)制轉(zhuǎn)化成二進(jìn)制，代碼實(shí)現(xiàn)：
15
1111 2 進(jìn)制和 10 進(jìn)制之間的轉(zhuǎn)換方法為：15 = 1*20?+ 1*21?+ 1*22?+ 1*23
括號(hào)匹配的檢查
在編寫(xiě)代碼的時(shí)候，經(jīng)常會(huì)用到兩種括號(hào)：圓括號(hào) “()” 和大括號(hào) “{}” 。不管使用哪種括號(hào)，程序編譯沒(méi)有問(wèn)題的一個(gè)考慮因素就是所使用的括號(hào)是否能夠匹配上，在編寫(xiě)程序時(shí)，括號(hào)可以嵌套，即： “({()})” 這種形式，但 “({)” 或者 “({}” 都不符合要求。編寫(xiě)程序判斷括號(hào)匹配問(wèn)題的時(shí)候，使用棧結(jié)構(gòu)會(huì)很容易：
- 如果碰到的是左圓括號(hào)或者左大括號(hào)，直接壓棧；
- 如果碰到的是右圓括號(hào)或者右大括號(hào)，就直接和棧頂元素配對(duì)：如果匹配，棧頂元素彈棧；反之，括號(hào)不匹配；
括號(hào)匹配
總結(jié)
以上是生活随笔為你收集整理的栈（Stack），轻松解决数制转换和括号匹配问题！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 哈利波特魔法觉醒卡牌皮肤怎么换
- 下一篇： 当贝投影D3X和极米Z6X哪个好?