1、堆棧及其應用數 據 結 構數組與線性表1.1 堆棧(Stack) 堆棧也簡稱為棧，是限定在表的一端進行插入或刪除操作的線性表。 進行插入或刪除操作的一段稱為棧頂（top），另一端稱為棧底（bottom）。 插入元素又稱為入棧（push），刪除元素操作稱為出棧（pop）。 不含元素的棧稱為空棧。 堆棧元素的插入和刪除只在棧頂進行，總是后進去的元素先出來，所以堆棧又稱為后進先出線性表或LIFO（Last-In-First-Out）表。 數組與線性表堆棧的表示堆棧的最簡單的表示方法是采用一維數組，為形象起見，一般在圖中將堆棧畫成豎直的 。設數組名為STACK，其下標的下界為1，上界為n。一般需用一個

2、變量top記錄當前棧頂的下標值，top也叫做棧指針。數組與線性表本例中top=4 topADCB4753216STACK數組與線性表1. 入棧（push） 入棧的主要操作是先將棧頂指針加1；然后將入棧元素放到棧頂指針所指示下標值的位置上。設用下標從1到n的數組ST表示堆棧，入棧的元素值為G，則可得到入棧函數如下：數組與線性表入棧函數 void push (ST, int n, top, G) if (top=n) printf(“棧溢出!n”); /*顯示棧滿信息*/ else top=top+1; STtop=G; 數組與線性表2. 出棧（Pop） 出棧運算時，先將棧頂的元素值賦給某個變量，

3、以備后面的運算應用；然后棧頂指針減1，將棧頂位置下移。假設已指定的變量為x，則出棧的函數如下： 數組與線性表出棧函數void pop (ST, int top, x) if (top=0) printf(“空棧!n”); /*棧為空顯示相應的信息*/ else x=STtop; top=top-1; /*棧頂位置下移*/ 數組與線性表1.2 堆棧的應用 1. 堆棧在函數調用中的應用: 設有三個函數A1，A2，A3，這三個函數有如下的調用關系：函數A1在其函數體的某處r調用函數A2，函數A2又在其函數體某處t調用函數A3，函數A3不調用其他函數。 rtA1A2A3數組與線性表函數嵌套調用A1調用

4、A2，A2調用A3時的返回地址在堆棧中的情況如右圖所示。 toprtSTACK數組與線性表2. 堆棧在表達式計算中的應用 一個算術表達式，例如A+B，其中加號“+”稱作運算符，而A，B稱為運算數。 對于由兩個運算數和一個運算符組成的表達式，習慣上是將運算符寫在兩個運算數中間，這叫做中綴形式。 計算機處理表達式時，常把運算符放在兩個運算數的后面或前面。1. 把運算符放在兩個運算數的后面，例如 AB+ ，稱為后綴形式，也叫做波蘭式 。2. 把運算符放在兩個運算數的前面，例如 +AB，則稱做前綴形式，也叫做逆波蘭表達式。 數組與線性表算術表達式的不同運算符有不同的運算優先順序，如，在沒有括號時，乘除

5、運算（*或/）要比加減運算（+或-）優先進行。下面用一個簡單的例子說明編譯系統在處理算術表達式時，是如何應用堆棧這種數據結構的。 假定表達式的運算數都是使用單個字母表示的，式中無括號且只有加、減、乘、除4種運算，而沒有更復雜的運算，例如表達式 X+Y*Z。 數組與線性表使用S1和S2兩個堆棧，S1用于存儲運算數，S2用于存儲運算符。編譯系統處理時，將表達式從左向右逐個掃視一遍，并根據不同情況按以下原則處理: 1) 若是運算數，則將其壓入S1棧； 2) 若是運算符且S2棧是空棧則將其壓入 S2棧； 3) 若是運算符且S2棧為非空棧，且此運算符的級別高于S2棧頂運算符的級別，則將此運算符壓入S2棧； 4) 凡不屬于上面三條的情況，則將S2的棧頂運算符與S