什么是堆棧

同順序表和鏈表一樣，棧也是用來存儲邏輯關系為 "一對一" 數據的線性存儲結構，如圖 1 所示。

圖 1 棧存儲結構示意圖

從圖 1 我們看到，棧存儲結構與之前所學的線性存儲結構有所差異，這緣于棧對數據 "存" 和 "取" 的過程有特殊的要求：

① 棧只能從表的一端存取數據，另一端是封閉的，如圖 1 所示;

② 在棧中，無論是存數據還是取數據，都必須遵循"先進后出"的原則，即最先進棧的元素最后出棧。拿圖 1 的棧來說，從圖中數據的存儲狀態(tài)可判斷出，元素 1 是最先進的棧。因此，當需要從棧中取出元素 1 時，根據"先進后出"的原則，需提前將元素 3 和元素 2 從棧中取出，然后才能成功取出元素 1。

因此，我們可以給棧下一個定義，即棧是一種只能從表的一端存取數據且遵循 "先進后出" 原則的線性存儲結構。

通常，棧的開口端被稱為棧頂;相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素，拿圖 2 來說，棧頂元素為元素 4;同理，棧底元素指的是位于棧最底部的元素，圖 2 中的棧底元素為元素 1。

圖 2 棧頂和棧底

進棧和出棧

基于棧結構的特點，在實際應用中，通常只會對棧執(zhí)行以下兩種操作：

• 向棧中添加元素，此過程被稱為"進棧"(入棧或壓棧);

• 從棧中提取出指定元素，此過程被稱為"出棧"(或彈棧);

棧的具體實現

棧是一種 "特殊" 的線性存儲結構，因此棧的具體實現有以下兩種方式：

① 順序棧：采用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構;

② 鏈棧：采用鏈式存儲結構實現棧結構;

兩種實現方式的區(qū)別，僅限于數據元素在實際物理空間上存放的相對位置，順序棧底層采用的是數組，鏈棧底層采用的是鏈表。有關順序棧和鏈棧的具體實現會在后續(xù)章節(jié)中作詳細講解。

棧的應用

基于棧結構對數據存取采用 "先進后出" 原則的特點，它可以用于實現很多功能。

例如，我們經常使用瀏覽器在各種網站上查找信息。假設先瀏覽的頁面 A，然后關閉了頁面 A 跳轉到頁面 B，隨后又關閉頁面 B 跳轉到了頁面 C。而此時，我們如果想重新回到頁面 A，有兩個選擇：

• 重新搜索找到頁面 A;

• 使用瀏覽器的"回退"功能。瀏覽器會先回退到頁面 B，而后再回退到頁面 A。

瀏覽器 "回退" 功能的實現，底層使用的就是棧存儲結構。當你關閉頁面 A 時，瀏覽器會將頁面 A 入棧;同樣，當你關閉頁面 B 時，瀏覽器也會將 B入棧。因此，當你執(zhí)行回退操作時，才會首先看到的是頁面 B，然后是頁面 A，這是棧中數據依次出棧的效果。

不僅如此，棧存儲結構還可以幫我們檢測代碼中的括號匹配問題。多數編程語言都會用到括號(小括號、中括號和大括號)，括號的錯誤使用(通常是丟右括號)會導致程序編譯錯誤，而很多開發(fā)工具中都有檢測代碼是否有編輯錯誤的功能，其中就包含檢測代碼中的括號匹配問題，此功能的底層實現使用的就是棧結構。

同時，棧結構還可以實現數值的進制轉換功能。例如，編寫程序實現從十進制數自動轉換成二進制數，就可以使用棧存儲結構來實現。

以上也僅是棧應用領域的冰山一角，這里不再過多舉例。在后續(xù)章節(jié)的學習中，我們會大量使用到棧結構。

接下來，我們學習如何實現順序棧和鏈棧，以及對棧中元素進行入棧和出棧的操作。