【正文】 167。 4 棧和隊(duì)列 167。 棧 167。 棧的定義 棧（ stack）又稱堆棧，它是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。 人們把對(duì)棧進(jìn)行運(yùn)算的一端稱為棧頂，棧頂?shù)牡谝粋€(gè)元素被稱為棧頂元素，相對(duì)地，把另一端稱為棧底。 ? 向一個(gè)棧插入新元素又稱為進(jìn)棧或入棧，它是把該元素放到棧頂元素的上面，使之成為新的棧頂元素； ? 從一個(gè)棧刪除元素又稱為出?；蛲藯＃前褩ｍ斣貏h除掉，使其下面的相鄰元素成為新的棧頂元素。 ? 由于棧的插入和刪除運(yùn)算僅在棧頂一端進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為后進(jìn)先出表 (Last In First Out, 簡(jiǎn)稱 LIFO)。 ? 棧的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 棧中沒(méi)有任何元素稱為空棧。 假定一個(gè)棧 S為 (a,b,c)，其中表尾的一端為棧頂，字符 c為棧頂元素。若向 S壓入一個(gè)元素 d，則 S變?yōu)?(a,b,c,d)，此時(shí)字符 d為棧頂元素；若接著從棧 S中依次刪除兩個(gè)元素，則首先刪除的是元素 d，接著刪除的是元素 c，棧 S變?yōu)?(a,b)，棧頂元素為 b。 棧的數(shù)據(jù)類型和運(yùn)算 ?棧的抽象數(shù)據(jù)類型中的數(shù)據(jù)部分為具有ElemType元素類型的一個(gè)棧，它可以采用任一種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)； ?棧的操作部分應(yīng)包括元素進(jìn)棧、元素出棧、讀取棧頂元素、檢查棧是否為空等。 棧的主要操作及程序： (1) 初始化棧 S，即把它置為空 void InitStack(S)。 (2) 新元素 x進(jìn)棧，即把 x值插入到棧頂 void Push(S, ElemType x)。 (3) 刪除棧頂元素并返回之 ElemType Pop(S)。 (4) 返回棧頂元素的值，不會(huì)改變棧的狀態(tài) ElemType Peek(S)。 (5) 判斷棧 S是否為空，若是則返回 1表示真，否則返回 0表示假 int EmptyStack(S)。 (6) 清除棧 S中的所有元素，使之成為一個(gè)空棧 void ClearStack(S)。 假定棧 a的元素類型為 int，下面為調(diào)用棧操作的一些例子。 (1) InitStack(a)。 //表示把棧 a置空 (2) Push(a,18)。 //表示元素 18進(jìn)棧 (3) int x=46。 Push(a,x)。 //表示 x的值 46進(jìn)棧 (4) Push(a,x/3)。 //表示 x除以 3的整數(shù)值 15進(jìn)棧 (5) x=Pop(a)。 //表示棧頂元素 15退棧并賦給 x (6) printf(“%d”,Peek(a))。 //表示讀取當(dāng)前棧頂元素 46并輸出 (7) Pop(a)。 //棧頂元素 46出棧，返回值 46自動(dòng)丟失 (8) EmptyStack(a)。 //因此時(shí)棧 a非空，所以返回的值 false (9) printf(“%d\n”,Pop(a))。 //棧頂元素 18退棧并輸出，此時(shí)棧已空 (10) x=EmptyStack(a)。 //因棧為空，返回 true，接著把對(duì)應(yīng)的整數(shù)值 1賦給 x 167。 棧的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn) ?棧的順序存儲(chǔ)結(jié)構(gòu)也稱為順序棧，它是一種運(yùn)算受限的順序表。 ?順序棧具有棧的一切特點(diǎn) 167。 順序棧的定義 棧的順序存儲(chǔ)結(jié)構(gòu)需要使用一個(gè)數(shù)組和一個(gè)整型變量來(lái)實(shí)現(xiàn)，利用數(shù)組來(lái)順序存儲(chǔ)棧中的所有元素，利用整型變量來(lái)存儲(chǔ)棧頂元素的下標(biāo) 位置。假定棧數(shù)組用 stack[MaxSize]表示，指示棧頂位置的整型變量用top表示，則元素類型為 ElemType的棧的順序存儲(chǔ)結(jié)構(gòu)可定義為： ElemType stack[MaxSize]。 int top。 其中， MaxSize為一個(gè)整型全局常量，需事先定義，由它確定順序棧（即順序存儲(chǔ)的棧）的最大長(zhǎng)度，又稱為深度，即?？臻g最多能夠存儲(chǔ) 的元素個(gè)數(shù)；由于 top用來(lái)指示棧頂元素的位置，所以把它稱為 棧頂指針 。 2. 利用記錄來(lái)實(shí)現(xiàn)棧的定義 假定該記錄類型用 StackSq表示，則定義為： struct StackSq { ElemType stack[MaxSize]。 int top。 }。 3. 采用動(dòng)態(tài)分配存儲(chǔ)空間的方法來(lái)實(shí)現(xiàn)棧的定義 struct StackSq { ElemType* stack。 /*存棧元素的數(shù)組指針 */ int top。 /*存棧頂元素的下標(biāo)位置 */ int MaxSize。 /*存 stack數(shù)組長(zhǎng)度 */ }。 ?在順序存儲(chǔ)的棧中， top的值為 1表示?？?， ?每次向棧中壓入一個(gè)元素時(shí)，首先使 top增 1，用以指示新的棧頂位置，然后再把元素賦值到這個(gè)空位置上，每次從棧中彈出一個(gè)元素時(shí)，首先取出棧頂元素，然后使 top減 1，指示出前一個(gè)元素成為新的棧頂元素。 ?在一個(gè)順序棧中，若 top已經(jīng)指向了 MaxSize1 的位置，則表示棧滿，若再向其插入新元素時(shí)就需要進(jìn)行棧滿處理， ?由于順序棧的插入和刪除運(yùn)算相當(dāng)于是在順序表的表尾進(jìn)行的，其時(shí)間復(fù)雜度為 O(1)。 設(shè)一個(gè)棧 S為 (a,b,c,d,e)，對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)如下圖 (a)所示。若向 S中插入一個(gè)元素 f，則對(duì)應(yīng)如下圖 (b)所示。若接著執(zhí)行兩次出棧操作后，則棧 S對(duì)應(yīng)如下圖 (c)所示。若依次使棧 S中的所有元素出棧，則 s變?yōu)榭眨缦聢D (d)所示。 MaxSize 1……………………0 a 0 a1 b0 a1 b 1 b2 c 2 c 2 c3 d 3 d 3 d4 e 4 e5 f401234toptoptop(a) top =4 (b) top =5 (c) top =3 (d) top =1MaxSize 1 MaxSize 1 MaxSize 1棧在順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)： 1. 初始化棧 S為空 此操作可以包括兩種情況，一種是置空并隱含分配固定大小的動(dòng)態(tài)存儲(chǔ)空間，另一種是置空并分配由參數(shù)指定大小的動(dòng)態(tài)存儲(chǔ)空間。首先給出第一種置空的算法。 void InitStack(struct StackSq* S) { /*置棧空間初始最大長(zhǎng)度為 10*/ SMaxSize=10。 /*動(dòng)態(tài)存儲(chǔ)空間分配 */ Sstack=malloc(10*sizeof(ElemType))。 /*置棧為空 */ Stop=1。 } 第二種置空棧的算法： void InitStack(struct StackSq* S, int ms) { /*檢查 ms是否有效，若無(wú)效則退出運(yùn)行 */ if(ms=0) {printf(ms的值非法 !\n)。 exit(1)。} /*置?？臻g大小為 ms*/ SMaxSize=ms。 /*動(dòng)態(tài)存儲(chǔ)空間分配，若分配失敗則退出運(yùn)行 */ Sstack=malloc(ms*sizeof(ElemType))。 if(!Sstack) { printf(動(dòng)態(tài)存儲(chǔ)分配失敗 !\n)。 exit(1)。 } /*初始置棧為空 */ Stop=1。 } 2. 新元素進(jìn)棧，即把它插入到棧頂 在這個(gè)算法中，對(duì)棧滿的處理方法是調(diào)用一個(gè)函數(shù)，使之得到大一倍的棧數(shù)組空間，接著進(jìn)行新元素的插入操作。 void Push(struct StackSq* S, ElemType x) { /*若?？臻g用完則重新分配更大的存儲(chǔ)空間 */ if(Stop==SMaxSize1) againMalloc(S)。 /*棧頂指針后移一個(gè)位置 */ Stop++。 /*將新元素插入到棧頂 */ Sstack[Stop]=x。 } void againMalloc(struct StackSq* S) { /*空間擴(kuò)展為原來(lái)的 2倍，原內(nèi)容被自動(dòng) 拷貝到 p所指向的存儲(chǔ)空間中 */ ElemType *p。 p=realloc(Sstack, 2*SMaxSize*sizeof(ElemType))。 if(!p) { /*分配失敗退出運(yùn)行 */ printf(存儲(chǔ)空間用完 !\n)。 exit(1)。 } /*使 stack指向新的棧空間 */ Sstack=p。 /*把?？臻g大小修改為新的長(zhǎng)度 */ SMaxSize=2*SMaxSize。 } 3. 刪除棧頂元素并返回值 ElemType Pop(struct StackSq* S) { /*若?？談t退出運(yùn)行 */ if(Stop==1) { printf(?？?，無(wú)元素出棧 !\n)。 exit(1)。 } /*棧頂指針減 1表示退棧 */ Stop。 /*返回原棧頂元素的值 */ return Sstack[Stop+1]。 } 棧的鏈接存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn) 棧的鏈接存儲(chǔ)結(jié)構(gòu)是通過(guò)由結(jié)點(diǎn)構(gòu)成的單鏈表實(shí)現(xiàn)的，此時(shí)表頭指針被稱為 棧頂指針 ，由棧頂指針指向的表頭結(jié)點(diǎn)被稱為 棧頂結(jié)點(diǎn) ，整個(gè)單鏈表被稱為 鏈棧 ，即鏈接存儲(chǔ)的棧。 ?當(dāng)向一個(gè)鏈棧插入元素時(shí)，是把該元素插入到棧頂，即使該元素結(jié)點(diǎn)的指針域指向原來(lái)的棧頂結(jié)點(diǎn)，而棧頂指針則修改為指向該元素結(jié)點(diǎn)，使該結(jié)點(diǎn)成為新的棧頂結(jié)點(diǎn)。 ?當(dāng)從一個(gè)鏈棧中刪除元素時(shí)，是把棧頂元素結(jié)點(diǎn)刪除掉，即取出棧頂元素后，使棧頂指針指向原棧頂結(jié)點(diǎn)的指針域所指向的結(jié)點(diǎn)。 ?對(duì)鏈棧的插入和刪除操作均是在單鏈表的表頭進(jìn)行的，其時(shí)間復(fù)雜度為 O(1)。 設(shè)一個(gè)棧為 (a,b,c)，當(dāng)采用鏈接存儲(chǔ)時(shí)，對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)如下圖 (a)所示，其中 HS表示棧頂指針，其值為存儲(chǔ)元素 c結(jié)點(diǎn)的地址。 其插入和刪除操作如圖所示： data nextc(a) (b) (c)a ab bdabcHSHSHS167。 鏈棧中數(shù)據(jù)結(jié)點(diǎn)的定義 ?鏈棧中的結(jié)點(diǎn)仍采用以前已經(jīng)定義的 sNode結(jié)點(diǎn)類型， 即： struct sNode { ElemType data。 // 數(shù)據(jù)域 struct sNode *next。 // 指針域 } … … Struct sNode *L； 167。 鏈棧的主要操作 假定鏈棧中的結(jié)點(diǎn)采用已經(jīng)定義的 sNode結(jié)點(diǎn)類型，并假定棧頂指針用 HS表示，鏈棧操作的算法有： 1. 初始化鏈棧為空 Void In