李春葆數(shù)據(jù)結構_第3章__棧和隊列

1、第第3 3章章 棧和隊列棧和隊列 3.1 3.1 棧棧 3.2 3.2 隊列隊列 本章小結本章小結 3.1.1 3.1.1 棧的定義棧的定義 3.1.2 3.1.2 棧的順序存儲結構及棧的順序存儲結構及其基本運算實現(xiàn)其基本運算實現(xiàn) 3.1.3 3.1.3 棧的鏈式存儲結構及棧的鏈式存儲結構及其基本運算的實現(xiàn)其基本運算的實現(xiàn)3.1.4 3.1.4 棧的應用例子棧的應用例子3.1 3.1 棧棧 棧是一種只能在一端進行插入或刪除操作的線棧是一種只能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為性表。表中允許進行插入、刪除操作的一端稱為棧頂棧頂。 棧頂?shù)漠斍拔恢檬莿討B(tài)的棧頂?shù)漠?/p>

2、前位置是動態(tài)的,棧頂?shù)漠斍拔恢糜梢粭ｍ數(shù)漠斍拔恢糜梢粋€稱為棧頂指針的位置指示器指示。表的另一端個稱為棧頂指針的位置指示器指示。表的另一端稱為棧底。稱為棧底。 當棧中沒有數(shù)據(jù)元素時當棧中沒有數(shù)據(jù)元素時,稱為稱為空?？諚?。 棧的插入操作通常稱為棧的插入操作通常稱為進棧進?；蚧蛉霔Ｈ霔?棧的刪除操棧的刪除操作通常稱為作通常稱為退棧退棧或或出棧出棧。3.1.1 3.1.1 棧的定義棧的定義 棧頂棧頂棧底棧底出棧出棧進棧進棧棧示意圖棧示意圖 例例3.1 設有設有4個元素個元素a、b、c、d進棧進棧,給出它給出它們所有可能的出棧次序。們所有可能的出棧次序。 答答:所有可能的出棧次序如下所有可能的出棧次序如

3、下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba 例例3.2 設一個棧的輸入序列為設一個棧的輸入序列為A,B,C,D,則借助則借助一個棧所得到的輸出序列不可能是一個棧所得到的輸出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答答:可以簡單地推算可以簡單地推算,得容易得出得容易得出D,A,B,C是是不可能的不可能的,因為因為D先出來先出來,說明說明A,B,C,D均在棧中均在棧中,按照入棧順序按照入棧順序,在棧中順序應為在棧中順序應為D,C,

4、B,A,出棧的出棧的順序只能是順序只能是D,C,B,A。所以本題答案為。所以本題答案為D。 例例3.3 已知一個棧的進棧序列是已知一個棧的進棧序列是1,2,3,n,其輸出其輸出序列是序列是p1,p2,pn,若若p1=n,則則pi的值的值 。(A) i (B) n-i (C) n-i+1 (D) 不確定不確定 答答:當當p1=n時時,輸出序列必是輸出序列必是n,n-1,3,2,1,則有則有: p2=n-1, p3=n-2, , pn=1推斷出推斷出pi=n-i+1,所以本題答案為所以本題答案為C。 例例3.4 設設n個元素進棧序列是個元素進棧序列是1,2,3,n,其輸出序其輸出序列是列是p1,p

5、2,pn,若若p1=3,則則p2的值的值 。(A) 一定是一定是2(B) 一定是一定是1(C) 不可能是不可能是1 (D) 以上都不對以上都不對 答答:當當p1=3時時,說明說明1,2,3先進棧先進棧,立即出棧立即出棧3,然后可然后可能出棧能出棧,即為即為2,也可能也可能4或后面的元素進?；蚝竺娴脑剡M棧,再出棧。再出棧。因此因此,p2可能是可能是2,也可能是也可能是4,n,但一定不能是但一定不能是1。所。所以本題答案為以本題答案為C。棧的幾種基本運算如下棧的幾種基本運算如下: (1) 初始化棧初始化棧InitStack(&s):構造一個空棧構造一個空棧s。 (2) 銷毀棧銷毀棧Cle

6、arStack(&s):釋放棧釋放棧s占用的存儲空占用的存儲空間。間。 (3) 求棧的長度求棧的長度StackLength(s):返回棧返回棧s中的元素中的元素個數(shù)。個數(shù)。 (4) 判斷棧是否為空判斷棧是否為空StackEmpty(s):若棧若棧s為空為空,則則返回真；否則返回假。返回真；否則返回假。 (5) 進棧進棧Push(&S,e):將元素將元素e插入到棧插入到棧s中作為棧中作為棧頂元素。頂元素。 (6) 出棧出棧Pop(&s,&e):從棧從棧s中退出棧頂元素中退出棧頂元素,并將并將其值賦給其值賦給e。 (7) 取棧頂元素取棧頂元素GetTop(s,&am

7、p;e):返回當前的棧頂元返回當前的棧頂元素素,并將其值賦給并將其值賦給e。 (8) 顯示棧中元素顯示棧中元素DispStack(s):從棧頂?shù)綏５醉槒臈ｍ數(shù)綏５醉樞蝻@示棧中所有元素。序顯示棧中所有元素。3.1.2 3.1.2 棧的順序存儲結構及其基本運算實現(xiàn)棧的順序存儲結構及其基本運算實現(xiàn) 假設棧的元素個數(shù)最大不超過正整數(shù)假設棧的元素個數(shù)最大不超過正整數(shù)MaxSize,所有的元素都具有同一數(shù)據(jù)類型所有的元素都具有同一數(shù)據(jù)類型ElemType,則可用則可用下列方式來定義棧類型下列方式來定義棧類型SqStack: typedef struct ElemType dataMaxSize； int

8、top；/*棧指針棧指針*/ SqStack；順序棧進棧和出棧示意圖順序棧進棧和出棧示意圖在順序棧中實現(xiàn)棧的基本運算算法在順序棧中實現(xiàn)棧的基本運算算法: (1) 初始化棧初始化棧initStack(&s) 建立一個新的空棧建立一個新的空棧s,s,實際上是將棧頂指針指向實際上是將棧頂指針指向-1-1即可。對應算法如下即可。對應算法如下: : void InitStack(SqStack *&s) s=(SqStack *)malloc(sizeof(SqStack); s-top=-1; (2) 銷毀棧銷毀棧ClearStack(&s) 釋放棧釋放棧s占用的存儲空間。對應

9、算法如下占用的存儲空間。對應算法如下: void ClearStack(SqStack *&s) free(s); (3) 求棧的長度求棧的長度StackLength(s) 返回棧返回棧s中的元素個數(shù)中的元素個數(shù),即棧指針加即棧指針加1的結果。對應的結果。對應算法如下算法如下: int StackLength(SqStack *s) return(s-top+1); (4) 判斷棧是否為空判斷棧是否為空StackEmpty(s) 棧棧S為空的條件是為空的條件是s-top=-1。對應算法如下。對應算法如下: int StackEmpty(SqStack *s) return(s-top=

10、-1); (5) 進棧進棧Push(&s,e) 在棧不滿的條件下在棧不滿的條件下,先將棧指針增先將棧指針增1,然后在該位置然后在該位置上插入元素上插入元素e。對應算法如下。對應算法如下: int Push(SqStack *&s,ElemType e) if (s-top=MaxSize-1) return 0;/*棧滿的情況棧滿的情況,即棧上溢出即棧上溢出*/s-top+; s-datas-top=e;return 1; (6) 出棧出棧Pop(&s,&e) 在棧不為空的條件下在棧不為空的條件下,先將棧頂元素賦給先將棧頂元素賦給e,然后將然后將棧指針減棧指針減

11、1。對應算法如下。對應算法如下: int Pop(SqStack *&s,ElemType &e) if (s-top=-1) return 0; /*棧為空的情況棧為空的情況,即棧下溢出即棧下溢出*/e=s-datas-top;s-top-;return 1; (7) 取棧頂元素取棧頂元素GetTop(s) 在棧不為空的條件下在棧不為空的條件下,將棧頂元素賦給將棧頂元素賦給e。對應算。對應算法如下法如下: int GetTop(SqStack *s,ElemType &e) if (s-top=-1) return 0; /*棧為空的情況棧為空的情況,即棧下溢出即棧下

12、溢出*/e=s-datas-top;return 1; (8) 顯示棧中元素顯示棧中元素DispStack(s) 從棧頂?shù)綏５醉樞蝻@示棧中所有元素。對應算從棧頂?shù)綏５醉樞蝻@示棧中所有元素。對應算法如下法如下: void DispStack(SqStack *s) int i;for (i=s-top;i=0;i-) printf(%c ,s-datai);printf(n); 3.1.3 3.1.3 棧的鏈式存儲結構及其基本運算的實現(xiàn)棧的鏈式存儲結構及其基本運算的實現(xiàn) 采用鏈式存儲的棧稱為鏈棧采用鏈式存儲的棧稱為鏈棧,這里采用單鏈表實現(xiàn)。這里采用單鏈表實現(xiàn)。 鏈棧的優(yōu)點是不存在棧滿上溢的情況。

13、我們規(guī)定鏈棧的優(yōu)點是不存在棧滿上溢的情況。我們規(guī)定棧的所有操作都是在單鏈表的表頭進行的棧的所有操作都是在單鏈表的表頭進行的,下圖是頭結下圖是頭結點為點為*lhead的鏈棧的鏈棧,第一個數(shù)據(jù)結點是棧頂結點第一個數(shù)據(jù)結點是棧頂結點,最后一最后一個結點是棧底結點。棧中元素自棧頂?shù)綏５滓来问莻€結點是棧底結點。棧中元素自棧頂?shù)綏５滓来问莂1、a2、an。鏈棧示意圖鏈棧示意圖 鏈棧中數(shù)據(jù)結點的類型鏈棧中數(shù)據(jù)結點的類型LiStack定義如下定義如下: typedef struct linknode ElemType data;/*數(shù)據(jù)域數(shù)據(jù)域*/ struct linknode *next;/*指針域指針域

14、*/ LiStack;在鏈棧中在鏈棧中,棧的基本運算算法如下棧的基本運算算法如下: (1) 初始化棧初始化棧initStack(&s) 建立一個空棧建立一個空棧s。實際上是創(chuàng)建鏈棧的頭結點。實際上是創(chuàng)建鏈棧的頭結點,并將其并將其next域置為域置為NULL。對應算法如下。對應算法如下: void InitStack(LiStack *&s) s=(LiStack *)malloc(sizeof(LiStack);s-next=NULL; s (2) 銷毀棧銷毀棧ClearStack(&s) 釋放棧釋放棧s s占用的全部存儲空間。對應算法如下占用的全部存儲空間。對應算法如

15、下: : void ClearStack(LiStack *&s) LiStack *p=s-next; while (p!=NULL) free(s);s=p;p=p-next; ( (3) 求棧的長度求棧的長度StackLength(s) 從第一個數(shù)據(jù)結點開始掃描單鏈表從第一個數(shù)據(jù)結點開始掃描單鏈表,用用i記錄訪問的記錄訪問的數(shù)據(jù)結點個數(shù)數(shù)據(jù)結點個數(shù),最后返回最后返回i值。對應算法如下值。對應算法如下: int StackLength(LiStack *s) int i=0;LiStack *p;p=s-next;while (p!=NULL) i+;p=p-next; retur

16、n(i); (4) 判斷棧是否為空判斷棧是否為空StackEmpty(s) 棧棧S為空的條件是為空的條件是s-next=NULL,即單鏈表中沒即單鏈表中沒有數(shù)據(jù)結點。對應算法如下有數(shù)據(jù)結點。對應算法如下: int StackEmpty(LiStack *s) return(s-next=NULL); s (5) 進棧進棧Push(&s,e) 將新數(shù)據(jù)結點插入到頭結點之后。對應算法如下將新數(shù)據(jù)結點插入到頭結點之后。對應算法如下: void Push(LiStack *&s,ElemType e) LiStack *p;p=(LiStack *)malloc(sizeof(LiSt

17、ack);p-data=e;p-next=s-next; /*插入插入*p結點作為第一個數(shù)據(jù)結點結點作為第一個數(shù)據(jù)結點*/ s-next=p; (6) 出棧出棧Pop(&s,&e) 在棧不為空的條件下在棧不為空的條件下,將頭結點后繼數(shù)據(jù)結點的數(shù)據(jù)域將頭結點后繼數(shù)據(jù)結點的數(shù)據(jù)域賦給賦給e,然后將其刪除。對應算法如下然后將其刪除。對應算法如下: int Pop(LiStack *&s,ElemType &e) LiStack *p;if (s-next=NULL) return 0; /*?？盏那闆r棧空的情況*/p=s-next;/*p指向第一個數(shù)據(jù)結點指向第一個數(shù)

18、據(jù)結點*/e=p-data;s-next=p-next;free(p);return 1; (7) 取棧頂元素取棧頂元素GetTop(s) 在棧不為空的條件下在棧不為空的條件下,將頭結點后繼數(shù)據(jù)結點的數(shù)據(jù)將頭結點后繼數(shù)據(jù)結點的數(shù)據(jù)域賦給域賦給e。對應算法如下。對應算法如下: int GetTop(LiStack *s,ElemType &e) if (s-next=NULL) return 0; /*?？盏那闆r棧空的情況*/e=s-next-data;return 1; (8) 顯示棧中元素顯示棧中元素DispStack(s) 從第一個數(shù)據(jù)結點開始掃描單鏈表從第一個數(shù)據(jù)結點開始掃描單鏈

19、表,并輸出當前訪并輸出當前訪問結點的數(shù)據(jù)域值。對應算法如下問結點的數(shù)據(jù)域值。對應算法如下: void DispStack(LiStack *s) LiStack *p=s-next; while (p!=NULL) printf(%c ,p-data);p=p-next; printf(n); 例例3.5 假設表達式中允許包含三種括號假設表達式中允許包含三種括號:圓括圓括號、方括號和大括號。編寫一個算法判斷表達式號、方括號和大括號。編寫一個算法判斷表達式中的括號是否正確配對。中的括號是否正確配對。 解解: 設置一個括號棧設置一個括號棧,掃描表達式：遇到左括掃描表達式：遇到左括號號(包括包括(、

20、和和)時進棧時進棧,遇到右括號時遇到右括號時,若棧是相若棧是相匹配的左括號匹配的左括號,則出棧則出棧,否則否則,返回返回0。 若表達式掃描結束若表達式掃描結束,棧為空棧為空,返回返回1表示括號正表示括號正確匹配確匹配,否則返回否則返回0。 int correct(char exp,int n) char stMaxSize; int top=-1,i=0,tag=1; while (i-1) tag=0; /*若棧不空若棧不空,則不配對則不配對*/ return(tag); 3.1.4 3.1.4 棧的應用例子棧的應用例子 1. 表達式求值表達式求值 這里限定的表達式求值問題是這里限定的表達式

21、求值問題是:用戶輸入一個包含用戶輸入一個包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號的合法數(shù)、正整數(shù)和圓括號的合法數(shù)學表達式學表達式,計算該表達式的運算結果。計算該表達式的運算結果。 在程序語言中在程序語言中,運算符位于兩個操作數(shù)中間的表運算符位于兩個操作數(shù)中間的表達式稱為達式稱為中綴表達式。中綴表達式。例如：例如： 1+2*3 就是一個中綴表達式就是一個中綴表達式,中綴表達式是最常用的一中綴表達式是最常用的一種表達式方式。對中綴表達式的運算一般遵循種表達式方式。對中綴表達式的運算一般遵循“先先乘除乘除,后加減后加減,從左到右計算從左到右計算,先括號內先括號內,后括號外后括號外”的的規(guī)則

22、。因此規(guī)則。因此,中綴表達式不僅要依賴運算符優(yōu)先級中綴表達式不僅要依賴運算符優(yōu)先級,而而且還要處理括號。且還要處理括號。 所謂所謂后綴表達式后綴表達式,就是運算符在操作數(shù)的后面就是運算符在操作數(shù)的后面,如如1+2*3的后綴表達式為的后綴表達式為123*+。在后綴表達式中已考慮。在后綴表達式中已考慮了運算符的優(yōu)先級了運算符的優(yōu)先級,沒有括號沒有括號,只有操作數(shù)和運算符。只有操作數(shù)和運算符。 對后綴表達式求值過程是對后綴表達式求值過程是:從左到右讀入后綴表達從左到右讀入后綴表達式式,若讀入的是一個操作數(shù)若讀入的是一個操作數(shù),就將它入數(shù)值棧就將它入數(shù)值棧,若讀入的若讀入的是一個運算符是一個運算符op

23、,就從數(shù)值棧中連續(xù)出棧兩個元素就從數(shù)值棧中連續(xù)出棧兩個元素(兩兩個操作數(shù)個操作數(shù)),假設為假設為x和和y,計算計算x op y之值之值,并將計算結果并將計算結果入數(shù)值棧；對整個后綴表達式讀入結束時入數(shù)值棧；對整個后綴表達式讀入結束時,棧頂元素棧頂元素就是計算結果。就是計算結果。 算術表達式求值過程是算術表達式求值過程是:先將算術表達式轉換成后先將算術表達式轉換成后綴表達式綴表達式,然后對該后綴表達式求值。然后對該后綴表達式求值。 假設算術表達式中的符號以字符形式由鍵盤輸入假設算術表達式中的符號以字符形式由鍵盤輸入,并存放在字符型數(shù)組并存放在字符型數(shù)組str中中,其后綴表達式存放在字符其后綴表達

24、式存放在字符型數(shù)組型數(shù)組exp中中,在將算術表達式轉換成后綴表達式的過在將算術表達式轉換成后綴表達式的過程中用一個字符型數(shù)組程中用一個字符型數(shù)組op作為棧。將算術表達式轉換作為棧。將算術表達式轉換成后綴表示的方法如下成后綴表示的方法如下: while (從從exp讀取字符讀取字符ch,ch!=0) 若若ch為數(shù)字為數(shù)字,將后續(xù)的所有數(shù)字均依次存放到將后續(xù)的所有數(shù)字均依次存放到postexp中中,并以并以字符字符“#”標志數(shù)值串結束。標志數(shù)值串結束。 若若ch為左括號為左括號“(”,則將此括號進棧到運算符棧則將此括號進棧到運算符棧op中。中。 若若ch為右括號為右括號“)”,則將運算符棧則將運算

25、符棧op中左括號中左括號“(”以前的運以前的運算符依次出棧并存放到算符依次出棧并存放到postexp中中,然后將左括號然后將左括號“(”刪除。刪除。 若若ch運算符優(yōu)先級小于或等于運算符優(yōu)先級小于或等于op棧頂運算符的優(yōu)先級棧頂運算符的優(yōu)先級 (除棧除棧頂運算符為頂運算符為“(”外外)的優(yōu)先級的優(yōu)先級,則依次出棧并存入到則依次出棧并存入到postexp中中,然然后將后將ch進棧。進棧。若字符串若字符串exp掃描完畢掃描完畢,則將運算棧則將運算棧op中的所有運算符依次出棧中的所有運算符依次出棧并存放到并存放到postexp中。最后得到后綴表達式中。最后得到后綴表達式postexp。中綴表達式后綴

26、表達式 對于表達式對于表達式“(56-20)/(4+2)”,其轉換成后綴表達其轉換成后綴表達式的過程式的過程 如下：如下：exp操作過程操作過程oppostexp(56-20)/(4+2)遇到遇到ch為為“(”,將此括號進棧將此括號進棧op。( 56-20)/(4+2)遇 到遇 到 c h 為 數(shù) 字為 數(shù) 字 , 將將 5 6 存 入存 入postexp中中,并插入一個字符并插入一個字符“#”。(56#-20)/(4+2)遇到遇到ch為為“-”,由于由于op中中“(”以前沒有字符以前沒有字符,則直接將則直接將ch進進棧棧op中。中。(-56#20)/(4+2)遇到遇到ch為數(shù)字為數(shù)字,將將2

27、0#存入數(shù)組存入數(shù)組exp中。中。(-56#20#exp操作過程操作過程oppostexp)/(4+2)遇到遇到ch為為“)”,則將棧則將棧op中中“(”以以前 的 字 符 依 次 出 棧 并 存 入前 的 字 符 依 次 出 棧 并 存 入postexp中中,然后將然后將“(”刪除。刪除。 56#20#-/(4+2)遇到遇到ch為為“/”,將將將將ch進棧進棧op中。中。 /56#20#-(4+2)遇到遇到ch為為“(”,將此括號進棧將此括號進棧op中。中。/(56#20#-4+2)遇到遇到ch為數(shù)字為數(shù)字,將將4#存入數(shù)組存入數(shù)組postexp中。中。/(56#20#-4#exp操作過程操

28、作過程oppostexp+2)遇到遇到ch為為“+”,由于由于op棧頂運算符棧頂運算符為為“(”,則直接將則直接將ch進棧進棧op中。中。/(+56#20#-4#2)遇到遇到ch為數(shù)字為數(shù)字,將將2#存入存入postexp中。中。 /(+56#20#-4#2#)遇到遇到ch為為“)”,則將棧則將棧op中中“(”以前以前的字符依次出棧并存放到的字符依次出棧并存放到postexp中中,然后將然后將“(”出棧。出棧。/56#20#-4#2#+ str掃描完畢掃描完畢,則將棧則將棧op中的所有運中的所有運算符依次彈出并存放到算符依次彈出并存放到postexp中中,得到后綴表達式。得到后綴表達式。 56

29、#20#-4#2#+/將算術表達式將算術表達式str轉換成后綴表達式轉換成后綴表達式expvoid trans(char str,char exp) structchar dataMaxSize;/*存放運算符存放運算符*/int top;/*棧指針棧指針*/ op;/*定義運算符棧定義運算符棧*/char ch;int i=0,t=0;/*t作為作為exp的下標的下標,i作為作為str的下標的下標*/op.top=-1;ch=stri;i+; while (ch!=0)/*str表達式未掃描完時循環(huán)表達式未掃描完時循環(huán)*/ switch(ch) case (:/*判定為左括號判定為左括號*/

30、op.top+;op.dataop.top=ch; break; case ): /*判定為右括號判定為右括號*/while (op.dataop.top!=() expt=op.dataop.top; op.top-; t+; op.top-; break; case +: case -: /*判定為加或減號判定為加或減號*/ while (op.top!=-1 & op.dataop.top!=() expt=op.dataop.top; op.top-; t+; op.top+;op.dataop.top=ch; break; case *: case /: /*判定為判定為*或

31、或/號號*/ while (op.dataop.top=* | op.dataop.top=/) expt=op.dataop.top; op.top-; t+; op.top+;op.dataop.top=ch; break; case :break;/*過濾掉空格過濾掉空格*/ default: while (ch=0 & ch=0 & ch(M-2,N-2)*/ int i,j,di,find,k; top+; /*初始方塊進棧初始方塊進棧*/ Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1; while (top-1)

32、/*棧不空時循環(huán)棧不空時循環(huán)*/ i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; if (i=M-2 & j=N-2)/*找到了出口找到了出口,輸出路徑輸出路徑*/ printf(迷宮路徑如下迷宮路徑如下:n); for (k=0;k=top;k+) printf(t(%d,%d),Stackk.i,Stackk.j); if (k+1)%5=0) printf(n); printf(n); return; find=0; while (direar+1) % MaxSize=q-front隊空條件仍為隊空條件仍為: q-rear=q-front r

33、ear rear 0 1 2 3 4 front (a)空隊空隊 (b)a,b,c 入隊入隊 rear 0 1 2 3 4 front a b c 0 1 2 3 4 a b c d front (c)d 入隊入隊,隊滿隊滿 rear 0 1 2 3 4 c d front (d)出隊出隊 2 次次 rear 0 1 2 3 4 front (e)出隊出隊 2 次次,隊空隊空 循環(huán)隊的入隊和出隊操作示意圖循環(huán)隊的入隊和出隊操作示意圖 在循環(huán)隊列中在循環(huán)隊列中,實現(xiàn)隊列的基本運算算法如下實現(xiàn)隊列的基本運算算法如下: (1) 初始化隊列初始化隊列InitQueue(&q) 構造一個空隊列構

34、造一個空隊列q。將。將front和和rear指針均設置成初指針均設置成初始狀態(tài)即始狀態(tài)即0值。對應算法如下值。對應算法如下: void InitQueue(SqQueue *&q) q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0; (2) 銷毀隊列銷毀隊列ClearQueue(&q) 釋放隊列釋放隊列q占用的存儲空間。對應算法如下占用的存儲空間。對應算法如下: void ClearQueue(SqQueue *&q) free(q); (3) 判斷隊列是否為空判斷隊列是否為空QueueEmpty(q) 若隊列若

35、隊列q滿足滿足q-front=q-rear條件條件,則返回則返回1；否則返回否則返回0。對應算法如下。對應算法如下: int QueueEmpty(SqQueue *q) return(q-front=q-rear); (4) 入隊列入隊列enQueue(q,e) 在隊列不滿的條件下在隊列不滿的條件下,先將隊尾指針先將隊尾指針rear循環(huán)增循環(huán)增1,然后將元素添加到該位置。對應算法如下然后將元素添加到該位置。對應算法如下: int enQueue(SqQueue *&q,ElemType e) if (q-rear+1)%MaxSize=q-front) /*隊滿隊滿*/return

36、0;q-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;return 1; (5) 出隊列出隊列deQueue(q,e) 在隊列在隊列q不為空的條件下不為空的條件下,將隊首指針將隊首指針front循環(huán)增循環(huán)增1,并并將該位置的元素值賦給將該位置的元素值賦給e。對應算法如下。對應算法如下: int deQueue(SqQueue *&q,ElemType &e) if (q-front=q-rear) /*隊空隊空*/return 0;q-front=(q-front+1)%MaxSize;e=q-dataq-front;return 1; 例例3.

37、6 什么是隊列的上溢現(xiàn)象和假溢出現(xiàn)象？解決什么是隊列的上溢現(xiàn)象和假溢出現(xiàn)象？解決它們有哪些方法？它們有哪些方法？ 答答: 在隊列的順序存儲結構中在隊列的順序存儲結構中,設頭指針為設頭指針為front,隊隊尾指針尾指針rear,隊的容量隊的容量(存儲空間的大小存儲空間的大小)為為MaxSize。當有元素加入到隊列時當有元素加入到隊列時,若若 rear=MaxSize(初始時初始時rear=0)則發(fā)生隊列的上溢現(xiàn)象則發(fā)生隊列的上溢現(xiàn)象,該元素不能加入隊列。該元素不能加入隊列。 特別要注意的是隊列的假溢出現(xiàn)象特別要注意的是隊列的假溢出現(xiàn)象:隊列中還有剩隊列中還有剩余空間但元素卻不能進入隊列余空間但元

38、素卻不能進入隊列,造成這種現(xiàn)象的原因造成這種現(xiàn)象的原因是由于隊列的操作方法所致。是由于隊列的操作方法所致。 解決隊列上溢的方法有以下幾種解決隊列上溢的方法有以下幾種: (1) 建立一個足夠大的存儲空間建立一個足夠大的存儲空間,但這樣做會造成空但這樣做會造成空間的使用效率降低。間的使用效率降低。 (2) 當出現(xiàn)假溢出時可采用以下幾種方法當出現(xiàn)假溢出時可采用以下幾種方法: 采用平移元素的方法采用平移元素的方法:每當隊列中加入一個元素時每當隊列中加入一個元素時,隊列中已有的元素向隊頭移動一個位置隊列中已有的元素向隊頭移動一個位置(當然要有空閑當然要有空閑的空間可供移動的空間可供移動)； 每當刪除一個

39、隊頭元素時每當刪除一個隊頭元素時,則依次移動隊中的則依次移動隊中的元素元素,始終使始終使front指針指向隊列中的第一個位置；指針指向隊列中的第一個位置； 采用循環(huán)隊列方式采用循環(huán)隊列方式:把隊列看成一個首尾相接把隊列看成一個首尾相接的循環(huán)隊列的循環(huán)隊列,在循環(huán)隊列上進行插入或刪除運算時仍在循環(huán)隊列上進行插入或刪除運算時仍然遵循然遵循“先進先出先進先出”的原則的原則。 例例3.7 對于順序隊列來說對于順序隊列來說,如果知道隊首元素的位如果知道隊首元素的位置和隊列中元素個數(shù)置和隊列中元素個數(shù),則隊尾元素所在位置顯然是可則隊尾元素所在位置顯然是可以計算的。也就是說以計算的。也就是說,可以用隊列中元

40、素個數(shù)代替隊可以用隊列中元素個數(shù)代替隊尾指針。編寫出這種循環(huán)順序隊列的初始化、入隊、尾指針。編寫出這種循環(huán)順序隊列的初始化、入隊、出隊和判空算法。出隊和判空算法。 解解: 當已知隊首元素的位置當已知隊首元素的位置front和隊列中元素個數(shù)和隊列中元素個數(shù)count后后:隊空的條件為隊空的條件為:count=0隊滿的條件為隊滿的條件為:count=MaxSize計算隊尾位置計算隊尾位置rear: rear=(front+count)%MaxSize 對應的算法如下對應的算法如下: typedef struct ElemType dataMaxSize;int front;/*隊首指針隊首指針*/

41、int count;/*隊列中元素個數(shù)隊列中元素個數(shù)*/ QuType;/*隊列類型隊列類型*/ void InitQu(QuType *&q) /*隊列隊列q初始化初始化*/ q=(QuType *)malloc(sizeof(QuType);q-front=0;q-count=0; int EnQu(QuType *&q,ElemType x)/*進隊進隊*/ int rear;if (q-count=MaxSize) return 0; /*隊滿上溢出隊滿上溢出*/else rear=(q-front+q-count+MaxSize)%MaxSize; /*求隊尾位置求隊

42、尾位置*/ rear=(rear+1)%MaxSize; /*隊尾位置進隊尾位置進1*/ q-datarear=x; q-count+; return 1; int DeQu(QuType *&q,ElemType &x)/*出隊出隊*/if (q-count=0)/*隊空下溢出隊空下溢出*/ return 0;else q-front=(q-front+1)%MaxSize; x=q-dataq-front; q-count-; return 1;int QuEmpty(QuType *q)/*判空判空*/ return(q-count=0); 鏈隊組成鏈隊組成: (1) 存

43、儲隊列元素的單鏈表存儲隊列元素的單鏈表 (2) 指向隊頭和隊尾指針的鏈隊頭結點指向隊頭和隊尾指針的鏈隊頭結點 3.2.3 3.2.3 隊列的鏈式存儲結構及其基本運算的實現(xiàn)隊列的鏈式存儲結構及其基本運算的實現(xiàn) front rear q (a)(a)鏈隊初態(tài)鏈隊初態(tài) front rear q (b)(b)入隊入隊 3 3 個元素個元素 a b c front rear q (c)(c)出隊出隊 1 1 個元素個元素 b c 鏈列的入隊和出隊操作示意圖鏈列的入隊和出隊操作示意圖單鏈表中數(shù)據(jù)結點類型單鏈表中數(shù)據(jù)結點類型QNode定義如下定義如下: typedef struct qnode ElemTy

44、pe data;/*數(shù)據(jù)元素數(shù)據(jù)元素*/struct qnode *next; QNode;鏈隊中頭結點類型鏈隊中頭結點類型LiQueue定義如下定義如下:typedef struct QNode *front;/*指向單鏈表隊頭結點指向單鏈表隊頭結點*/ QNode *rear; /*指向單鏈表隊尾結點指向單鏈表隊尾結點*/ LiQueue; 在鏈隊存儲中在鏈隊存儲中,隊列的基本運算算法如下隊列的基本運算算法如下: (1) 初始化隊列初始化隊列InitQueue(q) 構造一個空隊列構造一個空隊列,即只創(chuàng)建一個鏈隊頭結點即只創(chuàng)建一個鏈隊頭結點,其其front和和rear域均置為域均置為NUL

45、L,不創(chuàng)建數(shù)據(jù)元素結點。不創(chuàng)建數(shù)據(jù)元素結點。對應算法如下對應算法如下: void InitQueue(LiQueue *&q) q=(LiQueue *)malloc(sizeof(LiQueue); q-front=q-rear=NULL; (2) 銷毀隊列銷毀隊列ClearQueue(q) 釋放隊列占用的存儲空間釋放隊列占用的存儲空間,包括包括鏈隊頭結點鏈隊頭結點和和所有所有數(shù)據(jù)結點數(shù)據(jù)結點的存儲空間。對應算法如下的存儲空間。對應算法如下: void ClearQueue(LiQueue *&q) QNode *p=q-front,*r;if (p!=NULL) /*釋放數(shù)

46、據(jù)結點占用空間釋放數(shù)據(jù)結點占用空間*/ r=p-next; while (r!=NULL) free(p); p=r;r=p-next; /*p和和r指針同步后移指針同步后移*/ free(q);/*釋放鏈隊結點占用空間釋放鏈隊結點占用空間*/ (3) 判斷隊列是否為空判斷隊列是否為空QueueEmpty(q) 若鏈隊結點的若鏈隊結點的rear域值為域值為NULL,表示隊列為空表示隊列為空,返回返回1；否則返回；否則返回0。對應算法如下。對應算法如下: int QueueEmpty(LiQueue *q) if (q-rear=NULL) return 1;else return 0; (4)

47、 入隊列入隊列enQueue(q,e) 創(chuàng)建創(chuàng)建data域為域為e的數(shù)據(jù)結點的數(shù)據(jù)結點*s。若原隊列為空。若原隊列為空,則將鏈隊結點的兩個域均指向則將鏈隊結點的兩個域均指向*s結點結點,否則否則,將將*s鏈鏈到單鏈表的末尾到單鏈表的末尾,并讓鏈隊結點的并讓鏈隊結點的rear域指向它。域指向它。對應算法如下對應算法如下: void enQueue(LiQueue *&q,ElemType e) QNode *s; s=(QNode *)malloc(sizeof(QNode);s-data=e;s-next=NULL; if (q-rear=NULL) /*若原鏈隊為空若原鏈隊為空,新結

48、點是隊首結點又是隊尾結點新結點是隊首結點又是隊尾結點*/ q-front=q-rear=s;else q-rear-next=s; /*將將*s結點鏈到隊尾結點鏈到隊尾,rear指向它指向它*/ q-rear=s; (5) 出隊列出隊列deQueue(q,e) 若原隊列不為空若原隊列不為空,則將第一個數(shù)據(jù)結點的則將第一個數(shù)據(jù)結點的data域域值賦給值賦給e,并刪除之。若出隊之前隊列中只有一個結并刪除之。若出隊之前隊列中只有一個結點點,則需將鏈隊結點的兩個域均置為則需將鏈隊結點的兩個域均置為NULL,表示隊表示隊列已為空。對應的算法如下列已為空。對應的算法如下: int deQueue(LiQu

49、eue *&q,ElemType &e) QNode *t;if (q-rear=NULL) return 0; /*隊列為空隊列為空*/t=q-front;/*t指向第一個數(shù)據(jù)結點指向第一個數(shù)據(jù)結點*/if (q-front=q-rear) /*原鏈隊中只有一個結點時原鏈隊中只有一個結點時*/ q-front=q-rear=NULL;else/*原鏈隊中有多個結點時原鏈隊中有多個結點時*/ q-front=q-front-next;e=t-data; free(t);return 1; 3.2.4 3.2.4 隊列的應用例子隊列的應用例子采用隊列求解迷宮問題采用隊列求解迷宮問

50、題 使用一個隊列使用一個隊列Qu記錄走過的方塊記錄走過的方塊,該隊列的結構如該隊列的結構如下下: struct int i,j; /*方塊的位置方塊的位置*/ int pre; /*本路徑中上一方塊在本路徑中上一方塊在Qu中的下標中的下標*/ QuMaxSize; int front=-1,rear=-1;/*隊首指針和隊尾指針隊首指針和隊尾指針*/ 這里使用的隊列這里使用的隊列Qu不是循環(huán)隊列不是循環(huán)隊列(因為要利用出隊因為要利用出隊的元素找路徑的元素找路徑),因此在出隊時因此在出隊時,不會將出隊元素真正從不會將出隊元素真正從隊列中刪除隊列中刪除,因為要利用它輸出路徑。因為要利用它輸出路徑。 (1) 首先將首先將(1,1)入隊入隊; (2) 在隊列在隊列Qu不為空時循環(huán)不為空時循環(huán):出隊一次出隊一次(由于不是循由于不是循環(huán)隊列環(huán)隊列,該出隊元素仍在隊列中該出隊元素仍在隊列中),稱該出隊的方塊為當稱該出隊的方