數據結構中棧的應用

摘要：介紹了棧在數據結構中的應用。

關鍵詞：棧 進棧 出棧 數組

中圖分類號：TP311.12 文獻標識碼：A 文章編號：1002-2422(2008)01-0061-02

棧是數據結構中重要的線性結構，是一種特殊的線性表，只允許在表的一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂，另一端稱為棧底。棧項的當前位置是動態的，對棧頂當前位置的標記稱為棧項指針。當棧中沒有數據元素時，稱為空棧。棧的插入操作稱為進棧或入棧，棧的刪除操作稱為退棧或出棧。

棧的應用非常廣泛，在日常生活中，有許多類似棧的例子，如刷洗盤子時，依次把每個洗凈的盤子放到洗好的盤子上。相當于進棧；取用盤子時，從一摞盤子上一個接一個地向下拿，相當于出棧。在計算機中進行算術表達式的計算是通過棧來實現的。算術表達式的兩種表示方法，即中綴表示法和后綴表示法。日常算術表達式是將操作符(+，-，*，／)放在兩個操作數(數字，或代表數字的字母)之問的。假定操作數為單個英文字母，運算符只有+、-、*√(均為雙目運算符，相結合)，因為操作符寫在操作數的中間，所以把這種寫法稱為中綴表達法。

例如：(A-(B*C+D)*E)／(F+G)

這是一個中綴表達式，中綴表達式的計算比較復雜，必須遵守以下三條規則：(1)先計算括號內，后計算括號外；(2)在無括號或同層括號內，先進行乘除運算，后進行加減運算，即乘除運算的優先級高于加減運算的優先級；(3)同一優先級運算，從左向右依次進行。

從這三條規則可以看出，在中綴表達式的計算過程中，既要考慮括號的作用，又要考慮運算符的優先級，還要考慮運算符出現的先后次序。因此，各運算符實際的運算次序往往同在表達式中出現的先后次序是不一致的，是不可預測的。那么，能否把中綴算術表達式轉換成另一種形式的算術表達式，使計算簡單化呢?波蘭科學家盧卡謝維奇(Lukasiewicz)很早就提出了算術表達式的另一種表示，即后綴表示，也稱逆波蘭式。在后綴表達法中，操作符跟在兩個操作數的后面，這樣，A+B就成為AB+，AA3成為AB／。采用后綴表示的算術表達式被稱為后綴算術表達式或后綴表達式。在后綴表達式中，不存在括號，也不存在優先級的差別，計算過程完全按照運算符出現的先后次序進行，整個計算過程僅需一遍掃描便可完成，顯然比中綴表達式的計算要簡單得多。

例如：上面中綴表達式轉換為后綴表達式為ABC*D+E*-FG+／

中綴算術表達式轉換成對應的后綴算術表達式是：把每個運算符都移到兩個操作數的后面，然后刪除掉所有的括號即可。中綴表達式轉換成后綴表達式的過程是假定中綴表達式中無空格符，但整個算術表達式以空格符結束，并假定所提供的算術表達式非空且語法是正確的。(1)數組IN口存儲中綴表達式；(2)數組POLISH[]存儲其后綴表達式；(3)數組S口是一個后進先出的棧；(4)函數PRIOR(CHAR)返回符號CHAR的優先級，各符號的優先級如表1所示。

轉換規則：

(1)從頭到尾掃描中綴表達式，對不同類型的字符按不同情況處理：①如果是數字則直接放入后綴表達式數組；②如果是左括號則直接進棧；③如果是右括號，則把從棧項直到對應左括號之間的運算符依次出棧，并清除對應的左括號；④對于運算符，如果該運算符的優先級大于棧頂優先級，則直接進棧，若該運算符的優先級小于等于棧頂優先級，則先把棧頂運算符出棧，寫入后綴表達式數組，然后再進棧.(2)掃描完成后，取出棧中所有運算符，寫入后綴表達式數組。

中綴表達式(A+B-C*D)*(E-F)／G轉換成后綴表達式為AB+CD*-EF-*G／。利用數據結構中的棧，就很方便地把中綴表達式轉換成后綴表達式。