棧的應用研究

魏少涵

（1.福建工程學院國脈信息學院計算機與信息科學系，福州　350014；2.福州理工學院信息工程系，福州　350506）

棧的應用研究

魏少涵1，2

（1.福建工程學院國脈信息學院計算機與信息科學系，福州350014；2.福州理工學院信息工程系，福州350506）

0　引言

數據的表示和存儲是計算機領域的基礎且重要的研究內容，而數據結構就是研究彼此有聯系的數據的存儲和操作的學科。數據結構主要有線性和非線性兩種結構，其中線性結構有線性表、棧、隊列、數組、廣義表、串等，線性表是最基礎的線性結構，棧和隊列是操作受限的線性表，數組和廣義表是拓展的線性表，串是一種特殊的線性表。其中，棧的應用相當廣泛，有進一步研究的意義。

1　棧的定義與基本操作

棧是一種后進先出的線性結構，只允許在一端進行插入和刪除元素的操作，其基本操作有初始化、入棧、出棧、判斷棧空、取棧頂元素等。在計算機內存儲棧這種結構時，可以用順序存儲和鏈式存儲兩種。其中，順序存儲主要用定長數組來存儲元素的值，元素之間的相鄰關系用物理相鄰來表示。鏈式存儲用結點表示，結點的數據域存儲元素的值，結點的指針域存儲元素之間的相鄰關系。

順序棧的定義：

2　棧的應用

棧的應用很廣泛，例如進制轉換、表達式求值、括號匹配、消除遞歸、排序等。

2.1進制轉換

進制之間的轉換可以用棧來模擬。例如一個十進制數n轉換成二進制數，求解過程是：對十進制數n除以2，得到商m和余數，將商m作為下一步的n，除以2，得到新的商m和余數，依此計算步驟，直到最終商為0，在計算過程中，先后得到一些余數r1，r2，…，rt，但最終的轉換成的二進制數與計算過程產生的余數是相反的，即rt…r2r1，由此，計算順序與最終結果是“互逆”順序，滿足棧的先進后出性質，可以利用棧來存儲計算過程產生的數據，執行入棧操作，計算結束后，執行出棧操作，輸出結果。

2.2表達式求值

表達式是由操作數和運算符組成的式子。有前綴表達式、中綴表達式、后綴表達式三種。把表達式的符號畫成二叉樹來表示，先序、中序、后序遍歷得到的式子就是前綴、中綴、后綴表達式。

中綴表達式就是表達式本身，如a+b*（c-d）/e，可以用算符優先算法來實現，設置兩個棧，一個棧用于存儲操作數，另一個棧用于操作符。在輸入表達式時，如果是操作數，直接入棧，如果是操作符，與棧頂進行優先級比較，如果棧頂算符優先級高，彈出一個算符，彈出兩個操作數。先彈出的操作數，放在操作符的右側，后彈出的操作數，放在操作符的左側。運算中間結果入操作數棧，最終操作數棧里只有一個元素時，該元素即棧頂元素，就是計算結果。

后綴表達式計算較為簡單，如上述中綴表達式對應的后綴表達式是abcd-*e/+，在計算時，只要設置一個棧，是操作數，直接入棧，是操作符，彈出兩個操作數，按照先進后出性質，先彈出的操作數位于操作符右側，后彈出的操作數位于操作符左側，計算中間結果入棧。最終棧里只有一個數值，該數值即整個表達式的值。

2.3括號匹配

括號匹配問題是檢測小括號、中括號、大括號的嵌套。例如（｛［（）］｝）是括號匹配的，而（［］｛｝是不匹配的。利用棧來存儲輸入的括號，如果是左括號，直接入棧，如果是右括號，與當前棧頂的括號進行“比對”，如果“成對”，棧頂的左括號出棧，繼續接收下一個括號，直到棧空或者括號不匹配。

算法可采用程序語言描述如下：

2.4消除遞歸

棧是函數嵌套調用時采用的機制。遞歸是特殊的函數嵌套調用。遞歸雖然簡潔，結構清晰，但是調用時反復耗用空間，執行時間較慢。

消除遞歸可以用循環，如計算階乘，Fibonacci數列。消除遞歸可以用棧來模擬。例如二叉樹的先序、中序、后序的遞歸遍歷，可以轉化成非遞歸遍歷。二叉樹用樹形來表示。沿著二叉樹的根的左分支開始，繞著二叉樹外圍走一條閉合的路徑，每個結點都被經過三次。第一次經過的結點按先后次序排列，得到二叉樹的先序遍歷序列，第二次經過的結點按照經過的先后次序，組成了二叉樹的中序遍歷序列，第三次經過，得到后序遍歷序列。在此過程中，利用棧來記錄經過的次數。第一次經過時，將結點入棧，同時可以直接訪問，例如輸出結點的值，或者統計其他信息；結點第一次出棧時，即第二次經過，此時在出棧時可以訪問；為了記錄結點第三次經過，即結點的左右子樹都訪問完，才訪問該結點，當結點第一次出棧時，立刻第二次入棧，等第二次出棧時，可以訪問。此外，還有經典的遞歸問題漢諾塔等。

下面僅列出二叉樹先序遍歷的算法。

二叉樹采用二叉鏈表存儲，其定義如下：

對二叉樹的先序遍歷非遞歸算法的描述：

上述算法采用數組存儲棧來實現入棧和出棧操作，可以看作用順序存儲的方式來保存棧中元素。當然具體實現時也可調用棧的基本操作來實現。但上述用數組更直接。

用棧消除遞歸可以用機械的方法，按照特定的步驟進行轉化。可以設棧記錄當前工作情況，設置語句標號和非遞歸入口，在遞歸出口處增加goto語句。這類機械轉換一般采用程序變換的遞歸消除技術。在消除遞歸方面，還有形式推導支持的遞歸程序向非遞歸程序的轉換［1］；多函數間的遞歸消除，可以設置人工棧，拆除函數調用，將遞歸限定在單個函數內［2］。

3　結語

棧是常用的數據結構，應用領域廣泛。除了上述這些應用，還有迷宮求解問題、回溯等。利用棧的相關算法也可以實現數據共享問題［3］。今后將進一步研究棧的相關應用。

［1］化志章，揭安全等.形式推導支持的遞歸程序向非遞歸程序的轉換［J］.計算機工程與科學，2007（10）：145.

［2］潘欣，石川.一種多函數間的遞歸消除方法［J］.計算機工程，2012（3）：37.

［3］張連法，楊東升，秦承剛.一種采用消隱技術的鎖無關棧算法［J］.小型微型計算機系統，2013（6）：1349.

［4］何振峰.遞歸調用的內聯策略分析［J］.小型微型計算機系統，2009（9）：1787.

［5］陳燕暉，邢晶，羅宇.一種消除遞歸的新方法［J］.計算機工程與應用，2006（04）：73.

Stack；Evaluation of Expression；Recursion

Application and Research on Stack

WEI Shao-han1，2
（1.Fujian University of Technology，Guomai Information College，Computer and Information Science Department，Fuzhou 350014；2.Information Engineering Department，Fuzhou Institute of Technology，Fuzhou 350506）

1007-1423（2015）36-0017-04

10.3969/j.issn.1007-1423.2015.36.004

魏少涵（1983－），女，福建人，講師，碩士，研究方向為算法、軟件測試

2015-11-17

2015-12-10

棧是一種重要的操作受限的線性表，在計算機內可以用順序存儲或鏈式存儲來實現。基于其后進先出特性，應用非常廣泛，例如進制轉換、表達式求值，括號匹配，消除遞歸等。在總結其應用的同時，對于一些棧的應用給出算法描述。其中，表達式求值問題給出了針對不同表達式的兩種不同算法。

棧；表達式求值；遞歸

Stack is one of the important linear lists which is limited in operations.It can be realized by sequential storage and dynamic storage by link.It is used in many problems based on its last in first out property.For example，conversion of number system，evaluation of expression，brace match，recursion elimination and so on.Some algorithms are listed.Based on different kinds of expression，two algorithms have been given out.