第3章 棧和隊列

1、第第三三章章 棧和隊列棧和隊列第第3章章 棧和隊列棧和隊列3.1 棧棧3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 隊列隊列3.4 隊列的應(yīng)用舉例隊列的應(yīng)用舉例第第三三章章 棧和隊列棧和隊列第第3章章 棧和隊列棧和隊列 棧和隊列是兩類特殊的線性表，其邏輯結(jié)構(gòu)仍然是線性棧和隊列是兩類特殊的線性表，其邏輯結(jié)構(gòu)仍然是線性結(jié)構(gòu)，但棧和隊列是運(yùn)算受限的線性表。棧和隊列結(jié)構(gòu)被廣結(jié)構(gòu)，但棧和隊列是運(yùn)算受限的線性表。棧和隊列結(jié)構(gòu)被廣泛應(yīng)用于各種程序設(shè)計中。泛應(yīng)用于各種程序設(shè)計中。 本章討論棧和隊列的定義、運(yùn)算及其實(shí)現(xiàn)等。本章討論棧和隊列的定義、運(yùn)算及其實(shí)現(xiàn)等。第第三三章章 棧和隊列棧和隊列 3.1.1 抽象數(shù)據(jù)類型

2、的定義抽象數(shù)據(jù)類型的定義 數(shù)據(jù)元素的插入和刪除運(yùn)算數(shù)據(jù)元素的插入和刪除運(yùn)算通常將進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。將元素的插通常將進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。將元素的插入稱為入?；蜻M(jìn)棧，元素的刪除稱為出棧或退棧。入稱為入棧或進(jìn)棧，元素的刪除稱為出?；蛲藯?。 棧也稱為后進(jìn)先出的線性表（簡稱棧也稱為后進(jìn)先出的線性表（簡稱LIFO表）如圖表）如圖3.1(a)所示。所示。 在日常生活中，棧的形式經(jīng)常出現(xiàn)。例如，一疊盤子或一疊書的取放、在日常生活中，棧的形式經(jīng)常出現(xiàn)。例如，一疊盤子或一疊書的取放、鐵路調(diào)度站，如圖鐵路調(diào)度站，如圖3.1(b)所示。所示。 棧的基本運(yùn)算：棧的基

3、本運(yùn)算： （1）置空棧）置空棧setnull(s)：將棧：將棧s置成空棧，建立起棧頂指針。置成空棧，建立起棧頂指針。 （2）判?？眨┡袟？誩mpty(s)：若：若s為空棧，則返回為空棧，則返回TRUE值，否則返回值，否則返回FALSE值。值。 （3）入棧）入棧push(s,x)：若：若s未滿，將未滿，將x插入插入s棧棧頂，并使棧頂指針指向棧棧頂，并使棧頂指針指向x。 （4）出棧）出棧pop(s)：若：若s棧非空，則從棧中刪去棧頂元素，返回原棧頂元素。棧非空，則從棧中刪去棧頂元素，返回原棧頂元素。 （5）取棧頂元素）取棧頂元素gettop(s)：若：若s棧非空，則返回當(dāng)前棧頂元素。棧非空，則返回

4、當(dāng)前棧頂元素。3.1 棧棧第第三三章章 棧和隊列棧和隊列3.1 棧 示 例棧 頂棧 底a1a2an（ a） 棧 的 示 意 圖出 棧進(jìn) 棧（ b） 鐵 路 調(diào) 度 站 示 意 圖進(jìn) 棧出 棧第第三三章章 棧和隊列棧和隊列3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 1.順序棧：順序棧：棧的順序存儲結(jié)構(gòu)又稱為順序棧，順序棧也可用向量來實(shí)現(xiàn)。順序棧的棧的順序存儲結(jié)構(gòu)又稱為順序棧，順序棧也可用向量來實(shí)現(xiàn)。順序棧的類型定義如下：類型定義如下：#define MAXSIZE 100 /*棧的最大容量，這里設(shè)為棧的最大容量，這里設(shè)為100*/typedef int elemtype;typedef struc

5、t elemtype stackMAXSIZE;int top;seqstack; /*順序棧類型定義順序棧類型定義*/ seqstack *s; /*定義定義s為指向順序棧的指針變量為指向順序棧的指針變量*/ 在順序棧中進(jìn)棧或在順序棧中進(jìn)?；虺鰲＿\(yùn)算時要注意空間的出棧運(yùn)算時要注意空間的“溢出溢出”。當(dāng)棧滿時，若再進(jìn)行入棧運(yùn)算，會產(chǎn)。當(dāng)棧滿時，若再進(jìn)行入棧運(yùn)算，會產(chǎn)生空間生空間“上溢上溢” ；而當(dāng)棧空時，再進(jìn)行出棧運(yùn)算，會產(chǎn)生空間；而當(dāng)?？諘r，再進(jìn)行出棧運(yùn)算，會產(chǎn)生空間“下溢下溢” 。圖圖3.2說明了棧中元素與棧頂指針的關(guān)系。說明了棧中元素與棧頂指針的關(guān)系。第第三三章章 棧和隊列棧和隊列543

6、102top-1（a）空棧（b）A進(jìn)棧top543102A（c）B、C、D進(jìn)棧top543102ABCD圖3.2 棧中元素變化情況（d）D、C出棧top543102AB第第三三章章 棧和隊列棧和隊列 在順序棧上實(shí)現(xiàn)的棧的基本運(yùn)算。在順序棧上實(shí)現(xiàn)的棧的基本運(yùn)算。 （1）置空棧）置空棧void setnull(seqstack *s)/置空棧置空棧 s-top=-1; （2）判?？账惴ǎ┡袟？账惴╥nt empty(seqstack *s)/判空棧判空棧 if(s-toptop=MAXSIZE-1)printf(stack overflow！n);return 0;elses-stack+s-to

7、p=x;return 1; 第第三三章章 棧和隊列棧和隊列（4）出棧）出棧 elemtype pop(seqstack *s)/出棧出棧 if(s-topstacks-top-); （5）取棧頂元素算法）取棧頂元素算法 datatype gettop(seqstack *s) if(s-topstacks-top); 第第三三章章 棧和隊列棧和隊列（5）取棧頂元素算法）取棧頂元素算法 elemtype gettop(seqstack *s)/取棧頂元素取棧頂元素 if(s-topstacks-top); 第第三三章章 棧和隊列棧和隊列 有時可以將多個棧安排在同一個順序存儲空間中，實(shí)現(xiàn)多個棧共有

8、時可以將多個棧安排在同一個順序存儲空間中，實(shí)現(xiàn)多個棧共享存儲空間。享存儲空間。 假定兩個棧共享空間，可以給它們分配一個長度為假定兩個棧共享空間，可以給它們分配一個長度為m的數(shù)組空間的數(shù)組空間如圖如圖3.3所示。所示。m -13102棧 1 底棧 1 頂棧 2 底棧 2 頂圖3 .3兩 個 棧 共 享 空 間 示 意 圖棧 1棧 2 兩個棧共享的數(shù)據(jù)類型定義如下：兩個棧共享的數(shù)據(jù)類型定義如下： typedef struct datatype stackm; int top2; /* top0和和top1分別為兩棧的棧頂指針分別為兩棧的棧頂指針*/ sharedstack;第第三三章章 棧和隊列棧

9、和隊列兩個棧兩個棧的部分運(yùn)算算法如下：的部分運(yùn)算算法如下： （1）置空棧）置空棧 void setnull(sharedstack *s) s-top0=-1; s-top1=m; /*setnull*/（2）入棧）入棧 int push(sharedstack *s，int i，datatype x) if(i1|s-top0+1= =s-top1) return FALSE; else if(i=0) s-stack+s-top0=x; else s-stack-s-top1=x; return TRUE; /*push*/第第三三章章 棧和隊列棧和隊列（3）出棧）出棧 datatype

10、pop(sharedstack *s，int i) if(i1) return NULL; else if(i= =0) if (s-top0=-1) return NULL; else return（s-stacks-top0-）; else if(s-top1= =m) return NULL; else return（s-stacks-top1+）; /*pop*/第第三三章章 棧和隊列棧和隊列圖3.5 鏈棧示意圖棧頂棧底anan1a1top2.鏈棧鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧。鏈棧是運(yùn)算受限的單鏈表，其運(yùn)算只棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧。鏈棧是運(yùn)算受限的單鏈表，其運(yùn)算只能在鏈表頭部進(jìn)行，

11、其頭指針就是棧頂指針。能在鏈表頭部進(jìn)行，其頭指針就是棧頂指針。 鏈棧的數(shù)據(jù)類型定義：鏈棧的數(shù)據(jù)類型定義：# include# include# includetypedef int datatype; int a;typedef struct nodedatatype data;struct node *next;linkstack;鏈棧如圖鏈棧如圖3.5所示，其中所示，其中top是棧頂指針。當(dāng)是棧頂指針。當(dāng)top=NULL時，時，該鏈棧是空棧。該鏈棧是空棧。第第三三章章 棧和隊列棧和隊列 鏈棧的入棧和出棧運(yùn)算算法。鏈棧的入棧和出棧運(yùn)算算法。（1）置空棧）置空棧 linkstack *kd(l

12、inkstack *top)/置空棧置空棧linkstack *p;p=NULL;return p; （2）建棧）建棧 linkstack *getstack()/建棧建棧char ch;linkstack *p,*top=NULL;int x;printf(還要入棧嗎還要入棧嗎?請輸入非請輸入非n的字符：的字符：);cinch;第第三三章章 棧和隊列棧和隊列while(ch!=N&ch!=n)printf(n請輸入要入棧的值給請輸入要入棧的值給x:);scanf(%d,&x);p=(linkstack *)malloc(sizeof(linkstack);if(top=NUL

13、L)p-data=x;p-next=NULL;top=p;elsep-data=x;p-next=top;top=p;printf(還要入棧嗎還要入棧嗎?請輸入非請輸入非n的字符：的字符：);cinch;/ch=getchar();第第三三章章 棧和隊列棧和隊列 return top;（3）輸出棧）輸出棧void print(linkstack *top)/輸出棧輸出棧linkstack *p;p=top;while(p!=NULL)printf(%4d,p-data);p=p-next;printf(n);第第三三章章 棧和隊列棧和隊列（4）入棧）入棧linkstack *push(link

14、stack *top,datatype x)/入棧入棧 linkstack *p;p=(linkstack *)malloc(sizeof(linkstack); /*生成一個新結(jié)點(diǎn)生成一個新結(jié)點(diǎn)*p*/p-data=x;p-next=top;top=p;return top;第第三三章章 棧和隊列棧和隊列（4）出棧）出棧linkstack *pop(linkstack *top)/出棧出棧 linkstack *p;int x;if(top=NULL)printf(stack empty！n);return NULL;elsep=top;top=top-next;a=p-data;free(

15、p); /*釋放釋放p所指的結(jié)點(diǎn)所指的結(jié)點(diǎn)*/return top;第第三三章章 棧和隊列棧和隊列（5）判空棧）判空棧int stacknull(linkstack *top)/判空棧判空棧if(top=NULL)return 0;elsereturn 1;void main()linkstack *top;top=kd(top);datatype y; top=getstack();print(top);第第三三章章 棧和隊列棧和隊列printf(請輸入要入棧的請輸入要入棧的y的值的值:);scanf(%d,&y); top=push(top,y);print(top); top=p

16、op(top);printf(n%4dn,a);print(top); 第第三三章章 棧和隊列棧和隊列3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.2.1 表達(dá)式求值表達(dá)式求值 一般的，一個表達(dá)式由操作數(shù)、運(yùn)算符和分界符組成。一般的，一個表達(dá)式由操作數(shù)、運(yùn)算符和分界符組成。若運(yùn)算符出若運(yùn)算符出現(xiàn)在兩個運(yùn)算數(shù)或操作數(shù)之間（單目運(yùn)算符除外），稱為中綴表達(dá)式。現(xiàn)在兩個運(yùn)算數(shù)或操作數(shù)之間（單目運(yùn)算符除外），稱為中綴表達(dá)式。中綴表達(dá)式有利于人的理解，但不適合機(jī)器的實(shí)現(xiàn)。中綴表達(dá)式有利于人的理解，但不適合機(jī)器的實(shí)現(xiàn)。因此，因此，在編譯系統(tǒng)在編譯系統(tǒng)中，要把中綴表達(dá)式變換成一種后綴表達(dá)式（也稱為逆波蘭式），在后中，

17、要把中綴表達(dá)式變換成一種后綴表達(dá)式（也稱為逆波蘭式），在后綴表達(dá)式中，運(yùn)算符處在兩個操作數(shù)之后。后綴表達(dá)式一不需要使用括綴表達(dá)式中，運(yùn)算符處在兩個操作數(shù)之后。后綴表達(dá)式一不需要使用括號；二不需要考慮運(yùn)算符的優(yōu)先級，只需從左到右掃描后綴表達(dá)式，當(dāng)號；二不需要考慮運(yùn)算符的優(yōu)先級，只需從左到右掃描后綴表達(dá)式，當(dāng)掃描遇到運(yùn)算符時，就把它前面的兩個操作數(shù)取出，然后進(jìn)行運(yùn)算。如掃描遇到運(yùn)算符時，就把它前面的兩個操作數(shù)取出，然后進(jìn)行運(yùn)算。如圖圖3.6所示。所示。 把中綴表達(dá)式變換為相應(yīng)的后綴表達(dá)式，然后根據(jù)后綴表達(dá)式計算把中綴表達(dá)式變換為相應(yīng)的后綴表達(dá)式，然后根據(jù)后綴表達(dá)式計算表達(dá)式的值，這兩個步驟都可以利

18、用棧結(jié)構(gòu)來實(shí)現(xiàn)。表達(dá)式的值，這兩個步驟都可以利用棧結(jié)構(gòu)來實(shí)現(xiàn)。 第第三三章章 棧和隊列棧和隊列運(yùn)算運(yùn)算后綴表達(dá)式后綴表達(dá)式 ABCD/-E*+T1C/DABT1-E*+T2B-T1AT2E*+T3T2*EAT3+T4A+T3T4 圖圖3.6 后綴表達(dá)式的計算過程后綴表達(dá)式的計算過程第第三三章章 棧和隊列棧和隊列 要把中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式可以從左到右依次掃描中綴表達(dá)式，要把中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式可以從左到右依次掃描中綴表達(dá)式，根據(jù)所讀到的是操作數(shù)還是運(yùn)算符，利用棧并結(jié)合各個運(yùn)算符之間的優(yōu)先根據(jù)所讀到的是操作數(shù)還是運(yùn)算符，利用棧并結(jié)合各個運(yùn)算符之間的優(yōu)先級關(guān)系（表級關(guān)系（表3-1 ）來進(jìn)

19、行運(yùn)算。其）來進(jìn)行運(yùn)算。其算法思想是：設(shè)置一個棧并初始化，然后算法思想是：設(shè)置一個棧并初始化，然后從左到右順序讀入中綴表達(dá)式。當(dāng)讀到的是操作數(shù)時就直接將其輸出，并從左到右順序讀入中綴表達(dá)式。當(dāng)讀到的是操作數(shù)時就直接將其輸出，并接著讀下一個。當(dāng)讀到的是運(yùn)算符時，就將它賦給接著讀下一個。當(dāng)讀到的是運(yùn)算符時，就將它賦給 2，并根據(jù)運(yùn)算符的優(yōu)，并根據(jù)運(yùn)算符的優(yōu)先級關(guān)系表先級關(guān)系表3-1，比較，比較 2與當(dāng)前棧頂運(yùn)算符與當(dāng)前棧頂運(yùn)算符 1的優(yōu)先級。若的優(yōu)先級。若 2的優(yōu)先級比的優(yōu)先級比 1的高，則將的高，則將 2進(jìn)棧，繼續(xù)讀下一個；若進(jìn)棧，繼續(xù)讀下一個；若 2的優(yōu)先級比的優(yōu)先級比 1的低，則將的低，則將

20、 1出棧出棧并作為后綴表達(dá)式的一部分輸出，然后繼續(xù)比較并作為后綴表達(dá)式的一部分輸出，然后繼續(xù)比較 2與新的當(dāng)前棧頂運(yùn)算符與新的當(dāng)前棧頂運(yùn)算符 1的優(yōu)先級；若的優(yōu)先級；若 2的優(yōu)先級與的優(yōu)先級與 1的相同，且的相同，且 1為為(， 2為為)，則將，則將 1出出棧，并丟棄棧，并丟棄 1和和 2，再繼續(xù)讀下一個；若，再繼續(xù)讀下一個；若 2的優(yōu)先級與的優(yōu)先級與 1的相同，且的相同，且 1和和 2都是都是#，則表示表達(dá)式處理完畢，算法結(jié)束。，則表示表達(dá)式處理完畢，算法結(jié)束。 例如，圖例如，圖3.7表示對中綴表達(dá)式表示對中綴表達(dá)式A*(B+C)*D變換為后綴表達(dá)式，最后結(jié)變換為后綴表達(dá)式，最后結(jié)果為果為A

21、BC+*D*。第第三三章章 棧和隊列棧和隊列表表3-1 運(yùn)算符優(yōu)先級關(guān)系表運(yùn)算符優(yōu)先級關(guān)系表 2 1+ ()#+ ( #stack0=#; s-top=0; ch2=Rj; while (!(ch2= = # ) & (gettop(s)= =#) /*當(dāng)不是結(jié)束符當(dāng)不是結(jié)束符#時循環(huán)時循環(huán)*/ if(ch2!=+ ) & (ch2!=- ) & (ch2!=* ) & (ch2!=/)& (ch2!=( ) & (ch2!=) & (ch2!=#) printf(%c，ch2); ch2=R+j; else if(proceed(get

22、top(s)，ch2)= =) ch1=pop(s); printf(%c，ch1); else if(proceed(gettop(s),ch2)= = )&（gettop(s)= =(&ch2=)） ch1=pop(s); ch2=R+j; else printf(輸入表達(dá)式有語法錯誤輸入表達(dá)式有語法錯誤); /* postfix*/其中其中proceed( )函數(shù)實(shí)現(xiàn)表函數(shù)實(shí)現(xiàn)表3-1的運(yùn)算符優(yōu)先級關(guān)系比較功能，其函的運(yùn)算符優(yōu)先級關(guān)系比較功能，其函數(shù)返回值為對應(yīng)的字符，取值為數(shù)返回值為對應(yīng)的字符，取值為，front=-1; sq-rear=-1; （2）入隊）入隊 int

23、 enqueue(sequeue *sq，datatype x) if (sq-rear= =MAXSIZE-1) return(FALSE); else sq-queue+sq-rear=x; return(TRUE); 第第三三章章 棧和隊列棧和隊列 （3）出隊）出隊 datatype delqueue(sequeue *sq) if(sq-front= =sq-rear) return(NULL); else return(sq-queue+sq-front); 第第三三章章 棧和隊列棧和隊列 以上算法在入隊運(yùn)算中，由于隊滿條件的限制會產(chǎn)生以上算法在入隊運(yùn)算中，由于隊滿條件的限制會產(chǎn)生

24、“假上溢假上溢”現(xiàn)象，現(xiàn)象，即當(dāng)前隊列并沒有滿但會產(chǎn)生即當(dāng)前隊列并沒有滿但會產(chǎn)生“上溢上溢”。如圖。如圖3.13所示。所示。 為了更好地解決為了更好地解決“假上溢假上溢” 問題，可以將順序隊列設(shè)想為一個首尾相問題，可以將順序隊列設(shè)想為一個首尾相接的圓環(huán)，稱為循環(huán)向量，隊列稱為循環(huán)隊列，如圖接的圓環(huán)，稱為循環(huán)向量，隊列稱為循環(huán)隊列，如圖3.14所示。此時，可所示。此時，可以克服以克服“假溢出假溢出”現(xiàn)象。現(xiàn)象。 隊尾指針加隊尾指針加1的運(yùn)算在循環(huán)意義下可描述為：的運(yùn)算在循環(huán)意義下可描述為： if(sq-rear+1= =MAXSIZE) sq-rear=0; else sq-rear+; 也可以

25、利用利用數(shù)學(xué)上的求模運(yùn)算描述為：也可以利用利用數(shù)學(xué)上的求模運(yùn)算描述為： sq-rear=(sq-rear+1) % MAXSIZE 同樣，出隊運(yùn)算時，在循環(huán)意義下的隊頭指針加同樣，出隊運(yùn)算時，在循環(huán)意義下的隊頭指針加1運(yùn)算可描述為：運(yùn)算可描述為： sq-front=(sq-front+1) % MAXSIZE 但在利用但在利用循環(huán)隊列時會出現(xiàn)循環(huán)隊列時會出現(xiàn)隊空和隊滿兩種不同的狀態(tài)無法區(qū)別的情隊空和隊滿兩種不同的狀態(tài)無法區(qū)別的情形，如圖形，如圖3.14（b）和（）和（c），利用等式），利用等式sq-front=sq-rear都可以表示隊空都可以表示隊空和隊滿兩種不同的狀態(tài)。和隊滿兩種不同的狀態(tài)

26、。第第三三章章 棧和隊列棧和隊列(a) 空隊012345-1sq-rearsq-front-1(b) a1，a2，a3相繼入隊012345a1a2a3-1sq-rearsq-front(c) a1，a2相繼出隊012345a3sq-rearsq-front(d) a4，a5，a6相繼入隊012345a5a4a3sq-rearsq-fronta6圖3.13 順序隊列的頭、尾指針變化情況第第三三章章 棧和隊列棧和隊列圖3.14 循環(huán)隊列示意圖sq-rearsq-front01654327a1a2 (a)一般 情況sq-rearsq-front01654327（ c）隊列空時sq-rearsq-fr

27、ont01654327a8a1a2a3a4a5a6a7 (b)隊列滿時第第三三章章 棧和隊列棧和隊列 一般的，可利用以下兩種方法解決這個問題：一般的，可利用以下兩種方法解決這個問題： （1）設(shè)置一個區(qū)別隊列滿與隊列空的標(biāo)志，該標(biāo)志用于標(biāo)記在隊）設(shè)置一個區(qū)別隊列滿與隊列空的標(biāo)志，該標(biāo)志用于標(biāo)記在隊列中執(zhí)行的最后一次運(yùn)算。不過，使用標(biāo)志會減慢隊列入隊和出隊的列中執(zhí)行的最后一次運(yùn)算。不過，使用標(biāo)志會減慢隊列入隊和出隊的速度。速度。 （2）第二種方法是在入隊運(yùn)算之前，先判斷）第二種方法是在入隊運(yùn)算之前，先判斷(sq-rear+1)%MAXSIZE與與sq-front是否相等，若相等，則認(rèn)為隊列滿。是否

28、相等，若相等，則認(rèn)為隊列滿。但這樣會使得在循環(huán)隊列中隊頭指針?biāo)傅奈恢檬冀K是空的，有但這樣會使得在循環(huán)隊列中隊頭指針?biāo)傅奈恢檬冀K是空的，有MAXSIZE個分量的循環(huán)空間只能表示長度不超過個分量的循環(huán)空間只能表示長度不超過MAXSIZE-1的隊列。的隊列。但通過少利用一個元素空間而解決了隊滿與隊空條件相同的矛盾，總但通過少利用一個元素空間而解決了隊滿與隊空條件相同的矛盾，總的來說是可行的。的來說是可行的。 循環(huán)隊列的入隊和出隊運(yùn)算算法描述如下：循環(huán)隊列的入隊和出隊運(yùn)算算法描述如下：第第三三章章 棧和隊列棧和隊列（1）入隊列算法）入隊列算法 int encyque(sequeue *sq，dat

29、atype x) if(sq-rear+1)%MAXSIZE=sq-front) return(FALSE); else sqrear=(sq-rear+1)%MAXSIZE; sq-queuesq-rear=x; return(TRUE); （2）出隊列算法）出隊列算法 datatype delcyque(sequeue *sq) if(sq-front= =sq-rear) return(NULL); else sq-front=(sq-front+1)%MAXSIZE; return(sq-queuesq-front); 第第三三章章 棧和隊列棧和隊列3.3.3 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的

30、鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制在表頭刪除即出隊隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制在表頭刪除即出隊和表尾插入即入隊的單鏈表。和表尾插入即入隊的單鏈表。隊隊隊隊一個一個鏈隊列可由一個隊頭指針和一個隊尾指針唯一地確定，如圖鏈隊列可由一個隊頭指針和一個隊尾指針唯一地確定，如圖3.15。 鏈隊列定義如下：鏈隊列定義如下：typedef struct nodedatatype data; struct node *next; queuenode; /*定義鏈隊列中的一個結(jié)點(diǎn)結(jié)構(gòu)定義鏈隊列中的一個結(jié)點(diǎn)結(jié)構(gòu)*/typedef structqueuenode *front，*rear

31、; linkqueue; /*定義鏈隊列結(jié)構(gòu)定義鏈隊列結(jié)構(gòu)*/linkqueue *lq；第第三三章章 棧和隊列棧和隊列l(wèi)q-frontlq-rear頭 結(jié) 點(diǎn)lq (a) 空 鏈 隊 列l(wèi)q-frontlq-rear頭 結(jié) 點(diǎn)lq (b) 非 空 鏈 隊a1a1隊 頭 結(jié) 點(diǎn)圖 3.15 鏈 隊 列 示 意 圖第第三三章章 棧和隊列棧和隊列 鏈隊列上的幾種基本運(yùn)算描述：鏈隊列上的幾種基本運(yùn)算描述： （1）置空隊）置空隊 void inilinkque(linkqueue *lq) lq-front=(queuenode *)malloc(sizeof(queuenode); lq-rear=

32、lq-front; lq-front-next=NULL; （2）入隊）入隊 void enlinkque(linkqueue *lq，datatype x) queuenode *p; p=(queuenode *)malloc(sizeof(queuenode); p-data=x; p-next=NULL; lq-rear-next=p; lq-rear=p; 第第三三章章 棧和隊列棧和隊列（3）出隊）出隊 出隊列運(yùn)算必須考慮鏈隊列的長度大于出隊列運(yùn)算必須考慮鏈隊列的長度大于1和等于和等于1的情形。若當(dāng)前鏈隊的情形。若當(dāng)前鏈隊列的長度等于列的長度等于1即隊列中只有一個結(jié)點(diǎn)時，執(zhí)行出隊運(yùn)算

33、除了修改頭結(jié)點(diǎn)即隊列中只有一個結(jié)點(diǎn)時，執(zhí)行出隊運(yùn)算除了修改頭結(jié)點(diǎn)的指針域外，還需要修改隊尾指針，其指針變化如圖的指針域外，還需要修改隊尾指針，其指針變化如圖3.16所示。為了避免所示。為了避免在鏈隊列的長度等于在鏈隊列的長度等于1與大于與大于1時操作不一致，可采用一種改進(jìn)的出隊算法時操作不一致，可采用一種改進(jìn)的出隊算法如下：如下：第第三三章章 棧和隊列棧和隊列（3）出隊）出隊 出隊列運(yùn)算必須考慮鏈隊列的長度大于出隊列運(yùn)算必須考慮鏈隊列的長度大于1和等于和等于1的情形。若當(dāng)前鏈隊的情形。若當(dāng)前鏈隊列的長度等于列的長度等于1即隊列中只有一個結(jié)點(diǎn)時，執(zhí)行出隊運(yùn)算除了修改頭結(jié)點(diǎn)即隊列中只有一個結(jié)點(diǎn)時，執(zhí)行出隊運(yùn)算除了修改頭結(jié)點(diǎn)的指針域外，還需要修改隊尾指針，其指針變化如圖的指針域外，還需要修改隊尾指針，其指針變化如圖3.16所示。為了避免所示。為了避免在鏈隊列的長度等于在鏈隊列的長度等于1與大于與大于1時操作不一致，可采用一種改進(jìn)的出隊算法，時操作不一致，可采用一種改進(jìn)的出隊算法，描述如下：描述如下： datatype dellinkque(linkqueue *lq) queuenode *p; if