同順序表和鏈表一樣,棧也是用來存儲(chǔ)邏輯關(guān)系為 "一對(duì)一" 數(shù)據(jù)的線性存儲(chǔ)結(jié)構(gòu),如圖 1 所示。

圖 1 棧存儲(chǔ)結(jié)構(gòu)示意圖
從圖 1 我們看到,棧存儲(chǔ)結(jié)構(gòu)與之前所學(xué)的線性存儲(chǔ)結(jié)構(gòu)有所差異,這緣于棧對(duì)數(shù)據(jù) "存" 和 "取" 的過程有特殊的要求:
① 棧只能從表的一端存取數(shù)據(jù),另一端是封閉的,如圖 1 所示;
② 在棧中,無論是存數(shù)據(jù)還是取數(shù)據(jù),都必須遵循"先進(jìn)后出"的原則,即最先進(jìn)棧的元素最后出棧。拿圖 1 的棧來說,從圖中數(shù)據(jù)的存儲(chǔ)狀態(tài)可判斷出,元素 1 是最先進(jìn)的棧。因此,當(dāng)需要從棧中取出元素 1 時(shí),根據(jù)"先進(jìn)后出"的原則,需提前將元素 3 和元素 2 從棧中取出,然后才能成功取出元素 1。
因此,我們可以給棧下一個(gè)定義,即棧是一種只能從表的一端存取數(shù)據(jù)且遵循 "先進(jìn)后出" 原則的線性存儲(chǔ)結(jié)構(gòu)。
通常,棧的開口端被稱為棧頂;相應(yīng)地,封口端被稱為棧底。因此,棧頂元素指的就是距離棧頂最近的元素,拿圖 2 來說,棧頂元素為元素 4;同理,棧底元素指的是位于棧最底部的元素,圖 2 中的棧底元素為元素 1。

圖 2 棧頂和棧底
基于棧結(jié)構(gòu)的特點(diǎn),在實(shí)際應(yīng)用中,通常只會(huì)對(duì)棧執(zhí)行以下兩種操作:
• 向棧中添加元素,此過程被稱為"進(jìn)棧"(入?;驂簵?;
• 從棧中提取出指定元素,此過程被稱為"出棧"(或彈棧);
棧是一種 "特殊" 的線性存儲(chǔ)結(jié)構(gòu),因此棧的具體實(shí)現(xiàn)有以下兩種方式:
① 順序棧:采用順序存儲(chǔ)結(jié)構(gòu)可以模擬棧存儲(chǔ)數(shù)據(jù)的特點(diǎn),從而實(shí)現(xiàn)棧存儲(chǔ)結(jié)構(gòu);
② 鏈棧:采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu);
兩種實(shí)現(xiàn)方式的區(qū)別,僅限于數(shù)據(jù)元素在實(shí)際物理空間上存放的相對(duì)位置,順序棧底層采用的是數(shù)組,鏈棧底層采用的是鏈表。有關(guān)順序棧和鏈棧的具體實(shí)現(xiàn)會(huì)在后續(xù)章節(jié)中作詳細(xì)講解。
基于棧結(jié)構(gòu)對(duì)數(shù)據(jù)存取采用 "先進(jìn)后出" 原則的特點(diǎn),它可以用于實(shí)現(xiàn)很多功能。
例如,我們經(jīng)常使用瀏覽器在各種網(wǎng)站上查找信息。假設(shè)先瀏覽的頁面 A,然后關(guān)閉了頁面 A 跳轉(zhuǎn)到頁面 B,隨后又關(guān)閉頁面 B 跳轉(zhuǎn)到了頁面 C。而此時(shí),我們?nèi)绻胫匦禄氐巾撁?A,有兩個(gè)選擇:
• 重新搜索找到頁面 A;
• 使用瀏覽器的"回退"功能。瀏覽器會(huì)先回退到頁面 B,而后再回退到頁面 A。
瀏覽器 "回退" 功能的實(shí)現(xiàn),底層使用的就是棧存儲(chǔ)結(jié)構(gòu)。當(dāng)你關(guān)閉頁面 A 時(shí),瀏覽器會(huì)將頁面 A 入棧;同樣,當(dāng)你關(guān)閉頁面 B 時(shí),瀏覽器也會(huì)將 B入棧。因此,當(dāng)你執(zhí)行回退操作時(shí),才會(huì)首先看到的是頁面 B,然后是頁面 A,這是棧中數(shù)據(jù)依次出棧的效果。
不僅如此,棧存儲(chǔ)結(jié)構(gòu)還可以幫我們檢測(cè)代碼中的括號(hào)匹配問題。多數(shù)編程語言都會(huì)用到括號(hào)(小括號(hào)、中括號(hào)和大括號(hào)),括號(hào)的錯(cuò)誤使用(通常是丟右括號(hào))會(huì)導(dǎo)致程序編譯錯(cuò)誤,而很多開發(fā)工具中都有檢測(cè)代碼是否有編輯錯(cuò)誤的功能,其中就包含檢測(cè)代碼中的括號(hào)匹配問題,此功能的底層實(shí)現(xiàn)使用的就是棧結(jié)構(gòu)。
同時(shí),棧結(jié)構(gòu)還可以實(shí)現(xiàn)數(shù)值的進(jìn)制轉(zhuǎn)換功能。例如,編寫程序?qū)崿F(xiàn)從十進(jìn)制數(shù)自動(dòng)轉(zhuǎn)換成二進(jìn)制數(shù),就可以使用棧存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)。
以上也僅是棧應(yīng)用領(lǐng)域的冰山一角,這里不再過多舉例。在后續(xù)章節(jié)的學(xué)習(xí)中,我們會(huì)大量使用到棧結(jié)構(gòu)。
接下來,我們學(xué)習(xí)如何實(shí)現(xiàn)順序棧和鏈棧,以及對(duì)棧中元素進(jìn)行入棧和出棧的操作。