2.5　棧

圖2-22　棧的結構示意圖

棧是一種只允許在一端進行插入或刪除的線性表，即棧只允許先進后出（First In Last Out，FILO）或者后進先出（Last In First Out，LIFO）。棧的操作端通常被稱為棧頂，另一端被稱為棧底，棧的插入操作稱為壓棧（Push），棧的刪除操作稱為出棧（Pop）。壓棧是把新元素放到當前棧頂元素的上面，并使之成為新的棧頂元素；出棧則是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。棧的結構如圖2-22所示。

棧的實現方式主要分為兩種：一種是基于順序結構實現的；另一種是基于鏈式結構實現的。基于順序結構存儲的棧稱為順序棧，基于鏈式結構存儲的棧稱為鏈式棧。無論是基于何種形式實現的棧，一般都要實現這幾個方法，分別是判斷棧是否為空、判斷棧是否已滿、壓棧操作和出棧操作。值得說明的是，由于鏈表離散存儲的特性，在鏈式棧中無須檢測棧是否已滿，只要內存足夠大，理論上鏈式棧是不會滿的。

將棧的相關操作定義成Stack接口，代碼如下：

下面分別介紹棧的兩種實現方式。

2.5.1　順序棧

基于數組的順序棧存儲模型如圖2-23所示。

圖2-23　基于數組的順序棧結構示意圖

順序棧是基于順序結構實現的，順序結構添加元素、查找元素和刪除元素等操作可參考2.2節順序表相關實現。順序棧的實現如下：

創建順序棧測試類，驗證順序棧的功能。測試代碼如下：

執行順序棧測試類，測試結果如下：

    ----------順序棧是否為空----------
    false
    ----------順序棧是否已滿----------
    true
    ----------打印順序棧的元素----------
    9 8 7 6 5 4 3 2 1 0

2.5.2　鏈式棧

基于鏈表的鏈式棧存儲模型如圖2-24所示。

圖2-24　基于鏈表的鏈式棧結構示意圖

鏈式棧是基于鏈式結構實現的，鏈式存儲結構添加元素、查找元素和刪除元素等操作可參考2.3節單鏈表相關實現。鏈式棧的實現如下：

創建鏈式棧測試類，驗證鏈式棧的功能。測試代碼如下：

執行鏈式棧測試類，測試結果如下：

    ----------鏈式棧是否為空----------
    false
    ----------鏈式棧元素個數----------
    10
    ----------打印鏈式棧元素----------
    9 8 7 6 5 4 3 2 1 0

2.5.3　棧常見面試考點

（1）棧的概念：棧是只允許在一端進行操作的線性表。

（2）棧的特點：先進后出／后進先出。

（3）棧的存儲：

·　順序棧：順序存儲結構。

·　鏈式棧：鏈式存儲結構。

·　棧的相關算法：如軟件開發人員使用的編輯器中的括號匹配問題。

（4）JDK中的實現：JDK中的Stack類實現了棧，并實現了線程安全的API供開發人員使用。