2.5　棧結構

在程序設計中，讀者一定接觸過“堆?！钡母拍睢Ｆ鋵?，“棧”和“堆”是兩個不同的概念。棧是一種特殊的數據結構，在中斷處理特別是重要數據的現場保護有著重要意義。

2.5.1　什么是棧結構

棧結構是從數據的運算來分類的，也就是說棧結構具有特殊的運算規則。而從數據的邏輯結構來看，棧結構其實就是一種線性結構。如果從數據的存儲結構來進一步劃分，棧結構包括兩類。

?順序棧結構：即使用一組地址連續的內存單元依次保存棧中的數據。在程序中，可以定義一個指定大小的結構數組來作為棧，序號為0的元素就是棧底，再定義一個變量top保存棧頂的序號即可。

?鏈式棧結構：即使用鏈表形式保存棧中各元素的值。鏈表首部（head引用所指向元素）為棧頂，鏈表尾部（指向地址為null）為棧底。

典型的棧結構，如圖2-9所示。從圖中可以看出，在棧結構中只能在一端進行操作，該操作端稱為棧頂，另一端稱為棧底。也就是說，保存和取出數據都只能從棧結構的一端進行。從數據的運算角度來分析，棧結構是按照“后進先出”（Last In Firt Out，LIFO）的原則處理結點數據的。

其實，棧結構在日常生活中有很多生動的例子。例如，當倉庫中堆放貨物時，先來的貨物放在里面，后來的貨物碼放在外面；而要取出貨物時，總是先取外面的，最后才能取到里面放的貨物。也就是說，后放入貨物先取出。

在計算機程序設計中，特別是匯編程序中，棧通常用于中斷或者子程序調用過程。此時，首先將重要的寄存器或變量壓入棧，然后進入中斷例程或者子程序，處理完后，通過出棧操作恢復寄存器和變量的值。

在棧結構中，只有棧頂元素是可以訪問的。這樣，棧結構的數據運算非常簡單。一般棧結構的基本操作有兩個。

?入棧（Push）：將數據保存到棧頂的操作。進行入棧操作前，先修改棧頂引用，使其向上移一個元素位置，然后將數據保存到棧頂引用所指的位置。

?出棧（Pop）：將棧頂的數據彈出的操作。通過修改棧頂引用，使其指向棧中的下一個元素。

接下來，了解如何在Java語言中建立順序棧，并完成順序棧結構的基本運算。

2.5.2　準備數據

有了前面的理論知識后，下面就開始棧結構的程序設計。首先需要準備數據，即準備在棧操作中需要用到的變量及類等。示例代碼如下：

在上述代碼中，定義了棧結構的最大長度MAXLEN，棧結構數據元素的類DATA及棧結構的類StackType。在類StackType中，data為數據元素，top為棧頂的序號。當top=0時表示棧為空，當top=SIZE時表示棧滿。

Java語言中數組都是從下標0開始的。在這里，為了講述和理解的方便，從下標1開始記錄數據結點，下標0的位置不使用。

2.5.3　初始化棧結構

在使用順序棧之前，首先要創建一個空的順序棧，即初始化順序棧。順序棧的初始化操作步驟如下：

（1）按符號常量SIZE指定的大小申請一片內存空間，用來保存棧中的數據。

（2）設置棧頂引用的值為0，表示一個空棧。

初始化順序棧的代碼示例如下；

在上述代碼中，首先使用new關鍵字申請內存，申請成功后設置棧頂為0，然后返回申請內存的首地址。如果申請內存失敗，將返回null。

2.5.4　判斷空棧

判斷空棧即判斷一個棧結構是否為空。如果是空棧，則表示該棧結構中沒有數據。此時可以進行入棧操作，但不可以進行出棧操作。

判斷空棧的代碼示例如下：

在上述代碼中，輸入參數s為一個指向操作的棧的引用。程序中，根據棧頂引用top是否為0，判斷棧是否為空。

2.5.5　判斷滿棧

判斷滿棧即判斷一個棧結構是否為滿。如果是滿棧，則表示該棧結構中沒有多余的空間來保存額外數據。此時不可以進行入棧操作，但是可以進行出棧操作。

判斷滿棧的代碼示例如下：

在上述代碼中，輸入參數s為一個指向操作的棧的引用。程序中，判斷棧頂引用top是否等于符號常量MAXLEN，從而判斷棧是否已滿。

2.5.6　清空棧

清空棧即清除棧中的所有數據。清空棧的代碼示例如下：

在上述代碼中，輸入參數s是一個指向操作的棧的引用。在程序中，簡單地將棧頂引用top設置為0，表示執行清空棧操作。

2.5.7　釋放空間

釋放空間即釋放棧結構所占用的內存單元。由前面知道，在初始化棧結構時，使用了malloc函數分配內存空間。雖然可以使用清空棧操作，但是清空棧操作并沒有釋放內存空間，這就需要使用free函數釋放所分配的內存。

釋放空間的代碼示例如下：

在上述代碼中，輸入參數s是一個指向操作的棧的引用。程序中，直接賦值null操作釋放所分配的內存。一般在不需要使用棧結構的時候使用，特別是程序結束時。

2.5.8　入棧

入棧（Push）是棧結構的基本操作，主要操作是將數據元素保存到棧結構。入棧操作的具體步驟如下：

（1）首先判斷棧頂top，如果top大于等于SIZE，則表示溢出，進行出錯處理；否則執行以下操作。

（2）設置top=top+1（棧頂引用加1，指向入棧地址）。

（3）將入棧元素保存到top指向的位置。

入棧操作的代碼示例如下：

在上述代碼中，輸入參數s是一個指向操作的棧的引用，輸入參數data是需要入棧的數據元素。程序中首先判斷棧是否溢出，如果溢出則不進行入棧操作；否則修改棧頂引用的值，再將元素入棧。

2.5.9　出棧

出棧（Pop）是棧結構的基本操作，主要操作與入棧相反，其操作是從棧頂彈出一個數據元素。出棧操作的具體步驟如下：

（1）判斷棧頂top，如果top等于0，則表示為空棧，進行出錯處理；否則，執行下面的步驟。

（2）將棧頂引用top所指位置的元素返回。

（3）設置top=top-1，也就是使棧頂引用減1，指向棧的下一個元素，原來棧頂元素被彈出。

在上述代碼中，輸入參數s是一個指向操作的棧的引用。該函數返回值是一個DATA3類型的數據，返回值是棧頂的數據元素。

2.5.10　讀結點數據

讀結點數據即讀取棧結構中結點的數據。由于棧結構只能在一端進行操作，因此這里的讀操作其實就是讀取棧頂的數據。

需要注意的是，讀結點數據的操作和出棧操作不同。讀結點數據的操作僅顯示棧頂結點數據的內容，而出棧操作則將棧頂數據彈出，該數據不再存在了。

讀結點數據的代碼示例如下：

在上述代碼中，輸入參數s是一個指向操作的棧的引用。該方法返回值同樣是一個DATA3類型的數據，返回值是棧頂的數據元素。

2.5.11　棧結構操作實例

學習了前面的棧結構的基本運算，便可以輕松地完成對棧結構的各種操作。下面給出一個完整的例子，來演示棧結構的創建、入棧和出棧等操作。代碼示例如下：

【程序2-3】

在上述代碼中，main（）主方法首先初始化棧結構，然后循環進行入棧操作，添加數據結點，當輸入全部為0時則退出結點添加的進程。接下來，用戶每按一次按鍵，就進行一次出棧操作，顯示結點數據。當為空棧時，退出程序。該程序執行結果，如圖2-10所示。