第三章 棧與隊列.

1、學習目的要求: 棧的基本概念和棧的基本運算。 棧在計算機中的應用。 隊列的基本概念和隊列的基本運算。 隊列在計算機中的應用。 棧（Stack）又稱堆棧，是一種特殊的線性表，它限定線性表中元素的插入和刪除操作只能在線性表的一端進行。 允許插入和刪除的一端為變化的一端，稱為棧頂（top），棧頂?shù)牡谝粋€元素稱為棧頂元素，棧的另一端稱為棧底（bottom）。 向一個棧插入新元素又稱為進?；蛉霔＃前言撛胤诺綏ｍ斣氐纳厦?，使之成為新的棧頂元素。 從一個棧刪除一個元素又稱為出棧或退棧，它是把棧頂元素刪除掉，使其下面的相鄰元素成為新的棧頂元素。 所以又把棧稱為后進先出表（Last In First O

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

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

4、當top =MAXLEN-1，即棧滿時，向棧中再插入一個元素，棧也將溢出，稱為“上溢”。1.初始化順序棧SqStack InitStack_sq()/*建立一個空棧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.進棧操作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);棧是動態(tài)變化的數(shù)據(jù)結構，順序棧在某種程度上可以滿足這種動態(tài)結構所對應動態(tài)操作，但是一般數(shù)組長度的定義有一定局限性。棧的鏈式存儲結構簡稱為鏈棧，它是一種特殊的單鏈表，也

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

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

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

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

10、空時，輸出的結果即為后綴表達式。例3.2 將中綴表達式2*（3+5）/（6-4）轉換成等價的后綴表達式。步驟運算符棧輸出結果開始122*23* （24* （2 3步驟運算符棧輸出結果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ù)遞歸的實現(xiàn)函數(shù)直接或間接地調(diào)用自己的算法，叫做遞歸算法。例3.3 用遞歸的方法求 n!。 遞歸函數(shù)的執(zhí)行過程如下: （1

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

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

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

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

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

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

17、rear+1)%MAXLEN=cq-front) return(0); /*循環(huán)隊列滿返回0*/ else cq-rear=(cq-rear+1)%MAXLEN; cq-elementcq-rear=x; return(1); （2） 出隊int DelCqueue(CQueue *cq,elementtype *x) if(cq-rear=cq-front) return(0); /*循環(huán)隊列空返回0*/ else cq-front=(cq-front+1)%MAXLEN; *x=cq-elementcq-front; return(1); 隊列的鏈式存儲結構稱為鏈隊列（linked que

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

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