第三章 棧與隊(duì)列.

1、學(xué)習(xí)目的要求: 棧的基本概念和棧的基本運(yùn)算。 棧在計(jì)算機(jī)中的應(yīng)用。 隊(duì)列的基本概念和隊(duì)列的基本運(yùn)算。 隊(duì)列在計(jì)算機(jī)中的應(yīng)用。 棧（Stack）又稱堆棧，是一種特殊的線性表，它限定線性表中元素的插入和刪除操作只能在線性表的一端進(jìn)行。 允許插入和刪除的一端為變化的一端，稱為棧頂（top），棧頂?shù)牡谝粋€(gè)元素稱為棧頂元素，棧的另一端稱為棧底（bottom）。 向一個(gè)棧插入新元素又稱為進(jìn)棧或入棧，它是把該元素放到棧頂元素的上面，使之成為新的棧頂元素。 從一個(gè)棧刪除一個(gè)元素又稱為出?；蛲藯＃前褩ｍ斣貏h除掉，使其下面的相鄰元素成為新的棧頂元素。 所以又把棧稱為后進(jìn)先出表（Last In First O

2、ut），簡(jiǎn)稱為L(zhǎng)IFO表。（1）InitStack（）初始化操作，建立一個(gè)空棧S。（2）GetTop（&S，& x ）取棧頂元素操作，若棧S不空，則取棧頂元素，用 x 返回棧頂元素。（3）Push（&S， x ）進(jìn)棧操作，在S棧的棧頂壓入一個(gè)元素 x 。（4）Pop（&S，& x ）出棧操作，刪除已存在且非空的棧S的棧頂元素，用 x 返回棧頂元素。（5）Empty（&S）判斷一個(gè)棧是否為空，若S為空棧，返回一個(gè)真值。棧常用的基本操作:棧的順序存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)稱順序棧，它是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。#define MAX

3、LEN 10typedef int elementtype;typedef struct/*棧的順序存儲(chǔ)結(jié)構(gòu)定義*/ elementtype elementMAXLEN;/*存放棧元素的數(shù)組*/ int top; /*棧指針*/SqStack; 當(dāng)有新元素進(jìn)棧時(shí)，棧頂指針向上移動(dòng)，top加1。當(dāng)有元素出棧時(shí)，棧頂指針向下移動(dòng)，top減1。 用數(shù)組elementMAXLEN作為棧的存儲(chǔ)空間，elementtop為棧頂元素，當(dāng)top= -1時(shí)棧為空;當(dāng)top=0時(shí)，棧中有一個(gè)元素;當(dāng)top=MAXLEN-1時(shí)，表示棧滿。 當(dāng)top=-1，即棧為空時(shí)，從空棧中再刪除一個(gè)元素，棧將溢出，稱為“下溢”。

4、當(dāng)top =MAXLEN-1，即棧滿時(shí)，向棧中再插入一個(gè)元素，棧也將溢出，稱為“上溢”。1.初始化順序棧SqStack InitStack_sq()/*建立一個(gè)空棧s*/ SqStack s; s.top=-1; return(s);2.取棧頂元素int GetTop_sq(SqStack *s,elementtype *x) if(s-top=-1) return(0);/*?？辗祷?*/ else *x=s-elements-top; return(1); 3.進(jìn)棧操作int Push_sq(SqStack *s,elementtype x) if(s-top=MAXLEN-1) retu

5、rn(0); /*棧滿返回0*/ s-top+; s-elements-top=x; return(1);4.出棧操作int Pop_sq(SqStack *s,elementtype *x) if(s-top=-1) return(0); /*?？辗祷?*/ *x=s-elements-top; s-top-; return(1);5.判空棧操作int Empty_sq(SqStack *s) return(s-top=-1);棧是動(dòng)態(tài)變化的數(shù)據(jù)結(jié)構(gòu)，順序棧在某種程度上可以滿足這種動(dòng)態(tài)結(jié)構(gòu)所對(duì)應(yīng)動(dòng)態(tài)操作，但是一般數(shù)組長(zhǎng)度的定義有一定局限性。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈棧，它是一種特殊的單鏈表，也

6、是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，不用預(yù)先分配存儲(chǔ)空間。typedef struct node /*定義鏈棧結(jié)點(diǎn)*/ int data; /*這里以整型數(shù)據(jù)為例*/ struct node*next; /*指針類型,存放下一個(gè)結(jié)點(diǎn)地址*/NODE;1. 進(jìn)棧當(dāng)向鏈棧插入一個(gè)新元素時(shí)，首先要向系統(tǒng)申請(qǐng)一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間，將新元素的值寫入新結(jié)點(diǎn)的數(shù)據(jù)域中，然后修改棧頂指針。NODE *pushstack(NODE *top,int x) /*進(jìn)棧操作*/ NODE *p; p=(NODE*)malloc(sizeof(NODE); p-data=x;/*將要插入的數(shù)據(jù)x存儲(chǔ)到結(jié)點(diǎn)p的數(shù)據(jù)域中*/ p-next=

7、top; /*將p插入鏈表頭部,即鏈棧頂部*/ top=p; return(top);2. 出棧出棧時(shí)，先取出棧頂元素的值，再修改棧頂指針，釋放原棧頂結(jié)點(diǎn)。NODE *popstack(NODE *top,int *p) NODE *q; /*定義q結(jié)點(diǎn)*/ if(top!=NULL) /*如果棧不空*/ q=top; *p=top-data; /*將棧頂元素放入*p中*/ top=top-next; /*修改top指針*/ free(q); /*釋放原棧頂空間*/ return(top); /*返回棧頂指針*/棧是計(jì)算機(jī)軟件中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。1. 算術(shù)表達(dá)式的計(jì)算例3.1 用棧求表

8、達(dá)式6-8/4+3*5的值。步驟操作數(shù)棧運(yùn)算符棧說明開始開始時(shí)兩個(gè)棧為空16掃描到“6”，進(jìn)入操作數(shù)棧26-掃描到“-”，進(jìn)入運(yùn)算符棧36 8-掃描到“8”，進(jìn)入操作數(shù)棧步驟操作數(shù)棧運(yùn)算符棧說明46 8- /掃描到“/”，進(jìn)入運(yùn)算符棧56 8 4- /掃描到“4”，進(jìn)入操作數(shù)棧66-掃描到“+”，“/”、“8”、“4”退棧76 2-8/4=2進(jìn)操作數(shù)棧8繼續(xù)，“-”、“6”、“2”退棧946-2=4進(jìn)操作數(shù)棧104+“+”進(jìn)入運(yùn)算符棧114 3+掃描到“3”，進(jìn)入操作數(shù)棧124 3+ *掃描到“*”，進(jìn)入到運(yùn)算符棧步驟操作數(shù)棧運(yùn)算符棧說明134 3 5+ *掃描到“5”，進(jìn)入操作數(shù)棧144+掃

9、描完，“*”、“3”、“5”退棧154 15+3*5=15進(jìn)操作數(shù)棧16“+”、“4”、“15”退棧17194+15=19進(jìn)操作數(shù)棧1819表達(dá)式的值為192. 中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式是利用棧來完成的。轉(zhuǎn)換規(guī)則是，設(shè)立一個(gè)棧，存放運(yùn)算符，首先為空棧，編譯程序從左到右掃描中綴表達(dá)式:（1） 若遇到操作數(shù)，直接輸出，并輸出一個(gè)空格作為兩個(gè)操作數(shù)的分隔符;（2） 若遇到運(yùn)算符，則必須與棧頂比較，運(yùn)算符級(jí)別比棧頂級(jí)別高則進(jìn)棧，否則退出棧頂元素并輸出，然后輸出一個(gè)空格作為分隔符;（3） 若遇到左括號(hào)，進(jìn)棧，若遇到右括號(hào)，則一直退棧輸出，直到退到左括號(hào)為止;（4） 當(dāng)棧

10、空時(shí)，輸出的結(jié)果即為后綴表達(dá)式。例3.2 將中綴表達(dá)式2*（3+5）/（6-4）轉(zhuǎn)換成等價(jià)的后綴表達(dá)式。步驟運(yùn)算符棧輸出結(jié)果開始122*23* （24* （2 3步驟運(yùn)算符棧輸出結(jié)果5* （ +2 36* （ +2 3 57*2 3 5 +8/2 3 5 + *9/ （2 3 5 + *10/ （2 3 5 + * 611/ （ -2 3 5 + * 612/ （ -2 3 5 + * 6 413/2 3 5 + * 6 4 -142 3 5 + * 6 4 - /3. 函數(shù)遞歸的實(shí)現(xiàn)函數(shù)直接或間接地調(diào)用自己的算法，叫做遞歸算法。例3.3 用遞歸的方法求 n!。 遞歸函數(shù)的執(zhí)行過程如下: （1

11、） 系統(tǒng)首先為遞歸調(diào)用建立一個(gè)工作棧，在該工作棧中存放參數(shù)、局部變量和調(diào)用后的返回地址等信息; （2） 在每次遞歸調(diào)用之前，把本次算法中所使用的參數(shù)、局部變量的當(dāng)前值和調(diào)用后的返回地址等壓入棧頂; （3） 在每次執(zhí)行遞歸調(diào)用結(jié)束之后，又把棧頂元素彈出，分別賦給相應(yīng)的參數(shù)和局部變量，以便使它們恢復(fù)到調(diào)用前的狀態(tài)，然后返回由返回地址所指定的位置; （4） 繼續(xù)執(zhí)行后續(xù)指令。例3.4 設(shè) n=4， 計(jì)算4!。用一個(gè)棧來描述其遞歸的求解過程。 假設(shè)有3個(gè)分別命名為A、B和C的塔座，在塔座A上插有n個(gè)直徑大小各不相同、依小到大的編號(hào)為1，2，n的圓盤，如圖3.6所示。現(xiàn)要求將A座上的n個(gè)圓盤移至C座上并

12、仍按同樣順序疊排，圓盤移動(dòng)時(shí)必須遵循下列規(guī)則: （1）每次只能移動(dòng)一個(gè)圓盤; （2）圓盤可以插在A、B和C中的任一塔座上; （3）任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小圓盤之上。 如何實(shí)現(xiàn)移動(dòng)圓盤的操作呢?例3.5 Hanoi塔問題隊(duì)列（queue）也是一種特殊的線性表，它僅允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除。允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)首（front）。隊(duì)列又稱為先進(jìn)先出表（First In First Out，簡(jiǎn)稱FIFO）。隊(duì)列的基本操作可以歸納為以下幾種: （1）InitQueue（）; 初始化一個(gè)空隊(duì)列Q； （2）GetFront（&Q，

13、&y）; 取隊(duì)列Q的隊(duì)頭元素，y返回其值，但隊(duì)列Q狀態(tài)不變； （3）EnQuene（&Q，x）; 若隊(duì)列Q還有空間，將元素x插入到隊(duì)尾； （4）DelQueue（&Q，&y）;若隊(duì)列Q不為空，刪除隊(duì)列Q的隊(duì)頭元素，y返回其值； （5）Empty（&Q）; 判斷隊(duì)列Q是否為空，若為空返回一個(gè)真值，否則返回一個(gè)假值。1. 順序隊(duì)列隊(duì)列順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列（sequential queue）。順序隊(duì)列與順序表一樣，用一個(gè)一維數(shù)組來存放數(shù)據(jù)元素。在內(nèi)存中，用一組連續(xù)的存儲(chǔ)單元順序存放隊(duì)列中各元素。#define MAXLEN 10typedef int el

14、ementtype;typedef struct /*隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)定義*/ elementtype elementMAXLEN; /*存放隊(duì)列元素的數(shù)組*/ int front,rear; /*隊(duì)列頭、尾指針*/SeQueue;在隊(duì)列為空的初始狀態(tài)時(shí)，front=rear=-1。每當(dāng)向隊(duì)列中插入一個(gè)元素，尾指針rear向后移動(dòng)一位，rear=rear+1。當(dāng)rear= MAXLEN-1 時(shí)，表示隊(duì)滿;每當(dāng)從隊(duì)列中刪除一個(gè)元素時(shí)，隊(duì)首指針也向后移動(dòng)一位，front=front+1。（1） 入隊(duì)int Enqueue_sq(SeQueue *q,elementtype x) if(q-rea

15、r=MAXLEN-1) return(0); /*隊(duì)列滿返回0*/ q-rear+; q-elementq-rear=x; return(1);（2） 出隊(duì)int Delqueue_sq(SeQueue *q,elementtype *x) if(q-front=q-rear) return(0); /*隊(duì)列空返回0*/ else q-front+; *x=q-elementq-front; return(1); 可能會(huì)出現(xiàn)這樣情況，尾指針指向一維數(shù)組最后，但前面有元素已經(jīng)出隊(duì)，這時(shí)要插入元素，仍然發(fā)生溢出，而實(shí)際上隊(duì)列并未滿。這種溢出稱為“假溢出”。為了解決這個(gè)問題，下面討論循環(huán)隊(duì)列。2.

16、循環(huán)隊(duì)列循環(huán)隊(duì)列是將存儲(chǔ)隊(duì)列的存儲(chǔ)區(qū)看成是一個(gè)首尾相連的環(huán)，即將表示隊(duì)列的數(shù)組元素 element0與elementMAXLEN-1連接起來，形成一個(gè)環(huán)形表。在循環(huán)隊(duì)列中，容量設(shè)為MAXLEN，隊(duì)首指針為 front，隊(duì)尾指針為rear。當(dāng)rear=front時(shí)，不能判定循環(huán) 隊(duì)列是空隊(duì)還是滿隊(duì)。對(duì)此作出規(guī)定，front=rear是循環(huán)隊(duì)列空的標(biāo)志。（rear+1）%MAXLEN=front是循環(huán)隊(duì)列滿的標(biāo)志。因此，在循環(huán)隊(duì)列滿時(shí)，隊(duì)列中實(shí)際上還有一個(gè)空閑單元，以防止空隊(duì)與滿隊(duì)的標(biāo)志發(fā)生沖突。（1） 入隊(duì)int EnCqueue(CQueue *cq,elementtype x) if(cq-

17、rear+1)%MAXLEN=cq-front) return(0); /*循環(huán)隊(duì)列滿返回0*/ else cq-rear=(cq-rear+1)%MAXLEN; cq-elementcq-rear=x; return(1); （2） 出隊(duì)int DelCqueue(CQueue *cq,elementtype *x) if(cq-rear=cq-front) return(0); /*循環(huán)隊(duì)列空返回0*/ else cq-front=(cq-front+1)%MAXLEN; *x=cq-elementcq-front; return(1); 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列（linked que

18、ue）。typedef struct node /*定義鏈隊(duì)列結(jié)點(diǎn)*/ int data;/*以整型數(shù)據(jù)為例*/ struct node*next;/*存放下一個(gè)結(jié)點(diǎn)地址*/NODE;（1）入隊(duì)NODE *pushqueue(NODE *rear,int x) /*入隊(duì)操作*/ NODE *p; p=(NODE*)malloc(sizeof(NODE); p-data=x;/*將要插入的數(shù)據(jù)x存儲(chǔ)到結(jié)點(diǎn)p的數(shù)據(jù)域中*/ p-next=NULL; rear-next=p; /*將p插入鏈隊(duì)列尾部*/ rear=p; return(rear);（2） 出隊(duì)NODE *popqueue(NODE *

19、front,NODE *rear,int *x) /*出隊(duì)操作*/ NODE *p; if(front!=rear) /*判斷鏈隊(duì)列空,若鏈隊(duì)列不空*/ p=front-next;/*p指向鏈隊(duì)列第一個(gè)元素*/ front-next=p-next;/*將p元素出隊(duì)*/ if(p-next=NULL)/*表示原鏈隊(duì)列中只有一個(gè)元素*/ rear=front; /*出隊(duì)后,隊(duì)空,修改rear指針*/ *x=p-data;/*保存出隊(duì)后的元素值*/ free(p); return(rear); /*返回rear*/ 例3.6 打印數(shù)據(jù)緩沖區(qū)問題。在打印機(jī)打印的時(shí)候，主機(jī)輸出數(shù)據(jù)的速度比打印機(jī)打印的速度要快得多。由于速度不匹配，大大影響了主機(jī)的工作效率。為了解決這個(gè)問題，