3.1 棧

本節將介紹棧這種操作受限的線性表的抽象定義、存儲方式以及相應基本操作的實現；用棧完成對導學問題1的實現；對棧的其他應用進行拓展討論。

3.1.1 知識學習

1. 棧的基本概念

棧是只能在一端進行插入和刪除的線性表。允許插入、刪除的一端稱為棧頂，另一端稱為棧底。當棧中沒有元素時稱為空棧。

棧有兩個主要的操作：插入和刪除。棧的插入操作常稱為入棧（壓棧），棧的刪除操作常稱為出棧（彈棧）。棧的主要特點是“后進先出（Last In First Out，LIFO）”，即出棧元素只能是位于棧頂的元素，而入棧元素也只能放在棧頂位置。因此，棧是一種操作受限的線性表。

圖3-1所示的棧中有3個元素，進棧的順序是a、b、c，出棧時其順序為c、b、a。

在日常生活中，有很多后進先出的例子，如圖3-2所示的硬幣收納筒，要放入一枚硬幣或是從中取出一枚硬幣只有從頂部操作。在程序設計中，也常常需要棧這樣的數據結構，如編譯程序中判斷表達式括號匹配、算術表達式求值等問題。

【例3-1】假定有4個元素A、B、C、D，按所列次序進棧，試寫出所有可能的出棧序列。注意，每一個元素進棧后都允許出棧，如ACDB就是一種出棧序列。

解：可能的出棧序列有：ABCD、ABDC、ACBD、ACDB、ADCB、BACD、BADC、BCAD、BCDA、BDCA、CBAD、CBDA、CDBA、DCBA。

當有n個元素按照某種順序壓入棧中，且可在任意時刻彈出時，所獲得可能的出棧序列個數可用Catalan列計算，即。

由于棧是操作受限的線性表，因此線性表的存儲結構對棧也是適用的，只是操作不同而已。下面分別給出棧的順序存儲及基本操作和鏈式存儲及基本操作。

2. 棧的順序存儲及基本操作

（1）棧的順序存儲結構

利用順序存儲方式實現的棧又稱為順序棧。類似于順序表的定義，棧中的數據元素用一個預設足夠長度的一維數組來存儲；棧底位置可以設置在數組的任一個端點，本書將棧底位置設在低下標0處。由于棧頂位置會隨著入棧和出棧而變化，因此可用一個整型變量來表示當前棧頂的位置，通常稱該整型變量為棧頂指針。

順序棧的類型定義如下：

?？諘r，棧頂指針top= -1；棧滿時，棧頂指針top=MaxSize-1。入棧前，棧頂指針加1；出棧后，棧頂指針減1。順序棧的棧操作示意圖如圖3-3所示。

（2）順序棧的操作

由于棧是操作受限的線性表，因此順序棧的基本操作是順序表的簡化。順序棧的基本操作算法介紹如下。

1）初始化。初始化棧就是要構造一個空棧，如算法3-1所示。

算法3-1 順序棧的初始化

2）入棧操作。順序棧的入棧操作類似于順序表的插入操作。在棧頂插入一個新元素x，使x成為新的棧頂元素，同時棧頂指針需要發生變化，如算法3-2所示。

算法3-2 順序棧的入棧操作

3）出棧操作。出棧操作類似于順序表的刪除操作。將棧頂元素從棧中刪除，同時棧頂指針需要發生變化，如算法3-3所示。

算法3-3 順序棧的出棧操作

4）取棧頂元素。將棧頂元素作為結果返回，棧頂指針不變化，如算法3-4所示。

算法3-4 順序棧的取棧頂元素操作

5）判斷棧是否為空，具體實現如算法3-5所示。

算法3-5 判斷順序棧是否為空

6）判斷棧是否為滿，具體實現如算法3-6所示。

算法3-6 判斷順序棧是否為滿

3. 棧的鏈式存儲及基本操作

（1）棧的鏈式存儲結構

利用鏈式存儲方式實現的棧又稱為鏈棧。鏈棧中的結點仍可采用在第2章中已經定義的Node結點類型。由于棧是操作受限的線性表，對棧中元素的插入和刪除只能在棧頂進行，因此實現鏈棧的單鏈表不需要帶頭結點。鏈棧通常可表示為如圖3-4的形式，棧頂指針top就是單鏈表的頭指針。

鏈棧的類型定義如下：

可以用LinkStack定義指針，該指針就代表了一個鏈棧，如：

（2）鏈棧的操作

鏈棧的基本操作是單鏈表基本操作的簡化。

1）初始化。初始化函數用于建立一個無頭結點的單鏈表，如算法3-7所示。

算法3-7 鏈棧初始化

2）入棧操作。入棧類似于在無頭結點的單鏈表中進行表頭插入，如算法3-8所示。

算法3-8 鏈棧入棧操作

3）出棧操作。出棧類似于在單鏈表中進行表頭結點的刪除，如算法3-9所示。

算法3-9 鏈棧出棧操作

4）取棧頂元素。返回棧頂指針所指向結點的數據域即可，如算法3-10所示。

算法3-10 鏈棧中取棧頂元素操作

5）判斷棧是否為空，具體實現如算法3-11所示。

算法3-11 判斷鏈棧是否為空

6）鏈棧的銷毀。類似于單鏈表的銷毀函數，需要釋放鏈棧所占用的空間，如算法3-12所示。

算法3-12 鏈棧的銷毀

請讀者自行比較該算法與算法2-15，哪個算法的描述更為簡潔？

3.1.2 知識應用：導學問題1的實現

利用棧結構實現數制轉換時，主要涉及棧的兩個主要操作：入棧和出棧。輾轉相除時，將每次所得余數入棧；輸出結果時，依次出棧即可。轉換函數的代碼如下：

如果需要增強以上函數的通用性，使其可以將十進制數n轉換成r進制數（r為二進制至十六進制間任意值）。上述函數該如何修改？請讀者在上面conversion函數右邊的空白框中嘗試寫出改進后的函數，如有困難，請用手機掃描右側的二維碼查看參考代碼。

3.1.3 知識拓展：棧的其他應用

棧的應用非常廣泛，只要問題滿足“后進先出”原則，均可使用棧作為其數據結構。計算機中表達式的求值問題、遞歸程序等均與棧相關。本節將介紹這些實際問題如何使用棧來解決。

1. 算術表達式求值

算術表達式求值問題：輸入包含+、-、*、/、圓括號和正整數組成的中綴算術表達式，以′@′作為表達式結束符，計算該表達式的運算結果。

（1）利用中綴表達式直接求值

在程序設計語言中，操作符（運算符）位于兩個操作數中間的表達式稱為中綴表達式。

中綴表達式的計算比較復雜，在計算過程中，既要考慮括號的作用，又要考慮操作符的優先級，還要考慮操作符出現的先后次序。由于各操作符實際的運算次序往往與它們在表達式中出現的先后次序是不一致的。因此在求值時不能簡單地進行從左到右運算，必須先算運算級別高的，再算運算級別低的，同一級別的運算才從左到右，這種方法稱為“算符優先法”。算符間的優先關系見表3-1。

要實現中綴表達式直接求值，必須設置兩個棧：一個棧存放操作符，記做OPTR；另一個棧存放操作數，記做OPND。

中綴表達式求值算法的步驟如下。

1）初始時，操作數棧為空，操作符棧中放置一個元素′@′。

2）依次讀入表達式中的每個字符，直至表達式結束。

①若讀到的是操作數，則進入操作數棧，并讀入下一個字符。

②若讀到的是操作符c，則將操作符棧的棧頂元素pre_op與之進行比較，會出現以下3種情況：

● 若pre_op＜c，則將c入棧，并讀入下一個字符。

● 若pre_op=c，則pre_op出棧，并讀入下一個字符。

● 若pre_op＞c，則pre_op出棧，并在操作數棧中退棧兩次，依次得到操作數b和a，然后進行a pre_op b運算，并將運算的結果壓入操作數棧中。

3）掃描完畢時操作數棧中只有一個元素，即為運算的結果。

【例3-2】利用算符優先法，對輸入的算術表達式“8/（5-3）@”求值。

解：操作過程見表3-2。

算法3-13 算符優先法求算術表達式的值

注意：算法3-13只能對10以內的算術表達式求值，其中完成計算的函數Operate（），以及進行算符優先級比較的函數Precede（）等請讀者自行完成。還需要注意的是，算法中用到了兩個數據元素類型不同的棧，需要分別進行定義。參考程序可登錄www.cmpedu.com進行下載。

由于C語言功能的限制，本程序中對于操作符棧和操作數棧需要分別定義一套處理代碼，而這兩段代碼中的處理功能是一致的，只是處理的數據類型不同。C++語言提供的類模板可以很好地解決這個問題，用類模板實現算法3-13的代碼請參考 《數據結構（C++語言描述）》（吉根林、陳波編著，高等教育出版社，2014）一書。

（2）利用后綴表達式求值

波蘭科學家盧卡謝維奇很早就提出了算術表達式的另一種表示，即后綴表示，又稱逆波蘭式。后綴是指把操作符放在兩個操作數的后面。采用后綴表示的算術表達式被稱為后綴算術表達式或后綴表達式。在后綴表達式中，不存在括號，也不存在優先級的差別，計算過程完全按照運算符出現的先后次序進行。

【例3-3】將下列各中綴表達式轉換為后綴表達式。

（1）3/5+6

（2）16-9*（4+3）

（3）2*（x+y）/（1-x）

（4）（25+x）*（a*（a+b）+b）

解：相應的后綴表達式如下：

（1）3 5/ 6 +

（2）16 9 4 3 + * -

（3）2 x y + *1 x - /

（4）25 x + a a b + * b + *

將中綴表達式變成等價的后綴表達式時，表達式中操作數的次序不變，而操作符的次序會發生變化，同時需要去掉圓括號。因此設置一個棧OPTR用以存放操作符。

把中綴表達式轉換為后綴表達式算法的基本思路如下。

1）初始時，操作符棧中放置一個元素′@′。

2）依次讀入中綴表達式中的每個字符，對于不同類型的字符按不同情況進行處理。

①若讀到的是操作數，則輸出該操作數，并讀入下一個字符。

②若讀到的是左括號，則把它壓入到OPTR棧中，并讀入下一個字符。

③若讀到的是右括號，則表明括號內的中綴表達式已經掃描完畢，將OPTR棧從棧頂直到左括號之前的操作符依次出棧并輸出，然后將左括號也出棧，并讀入下一個字符。

④若讀到的是操作符c，則將操作符棧的棧頂元素pre_op與之進行比較：

● 若pre_op ＜c，則將c入棧，并讀入下一個字符。

● 若pre_op＞=c，則將pre_op出棧并輸出。

⑤若讀到的是結束符@，則將棧中剩余的操作符依次出棧并輸出，即可得到轉換成的后綴表達式。

請讀者根據以上算法步驟完成程序。

【例3-4】用一個操作符棧來模擬將輸入的中綴算術表達式“8/（5-3）@”轉換成后綴表達式的過程。

解：操作過程見表3-3。

將中綴表達式轉換成等價的后綴表達式求值時，不需要再考慮操作符的優先級，只需從左到右掃描一遍后綴表達式即可。可設置一個棧OPND用以存放操作數。

后綴表達式求值算法的基本思路如下：

1）依次讀入后綴表達式中的每個字符，直至表達式結束。

● 若讀到的是操作數，則入棧OPND。

● 若讀到的是操作符，則在OPND棧中退出兩個元素（先退出的在操作符右，后退出的在操作符左），然后用該操作符進行運算，并將運算的結果壓入OPND棧中。

2）后綴表達式掃描完畢時，若OPND棧中僅有一個元素，即為運算的結果。

請讀者根據以上算法步驟完成應用實戰第1題。

【例3-5】用一個操作數棧來模擬【例3-4】所得的后綴算術表達式“853 - / @”的求值過程。

解：操作過程見表3-4。

2. 棧與遞歸

（1）遞歸的含義

遞歸是指函數直接調用自己或通過一系列調用語句間接調用自己，該函數稱為遞歸函數。遞歸是程序設計的有效方法之一，可用遞歸方法求解的問題必須同時具備以下兩個條件：

1）一個問題可以化解為若干個性質相同、解法相同的小問題，而小問題還可分解為更小的問題……上述轉化具有相同的規律，并使問題逐步簡化。

2）存在明確的遞歸出口（終止條件），即當問題規模降低到一定程度時可以直接求解。

實際上以上兩點也是遞歸算法設計的基本框架。

根據上述條件，適合用遞歸方法求解的問題有以下3種情況：

1）數學上定義為遞歸的函數。例如，求整型數n的階乘的定義為

還有很多遞歸性質的函數，如Fibonacci級數、Ackerman函數等。

2）數據的結構是遞歸的。例如，本書第5章介紹的廣義表，其元素也可以是一個子表，而子表也是表；第6章介紹的樹形結構，每個結點可以有0至多個子樹，而子樹又是一棵樹。

3）解題的方式用遞歸解法比用遞推解法更為簡單。例如，漢諾塔問題、八皇后問題等。

（2）棧和遞歸

在用高級語言編寫的程序中，對于函數的調用，系統是通過棧來實現的。一個遞歸函數的執行過程類似于多個函數的嵌套調用，因此在執行遞歸函數的過程中也需要一個“遞歸工作?！薄Ｋ淖饔萌缦拢?/p>

1）將遞歸調用時的實際參數和函數返回地址傳遞給下一層的遞歸函數。

2）保存本層的參數和局部變量，以便從下一層返回時重新使用它們。

算法3-14給出了求整型數n的階乘的遞歸設計。

算法3-14 求階乘的遞歸算法

圖3-5給出了n=3時求階乘遞歸算法的運行軌跡。

圖3-6給出了n=3時求階乘遞歸算法運行時的工作棧中的狀況。