《數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）》課件第03章

2023年11月28日1第3章棧和隊(duì)列

本章學(xué)習(xí)內(nèi)容3.1棧

3.2隊(duì)列

2023年11月28日23.1棧

3.1.1棧的定義

棧（stack）是限制線性表中元素的插入和刪除只能在線性表的同一端進(jìn)行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂（Top），另一端為固定的一端，稱為棧底（Bottom）。根據(jù)棧的定義可知，最先放入棧中的元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。在如圖3-1所示的棧中，元素以a1，a2，a3，…，an的順序進(jìn)入棧中，而出來則以an，an-1，…，a2，a1的順序。也就是說，棧是一種后進(jìn)先出（LastInFirstOut）的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。棧在日常生活中隨處可見，如倉(cāng)庫(kù)貨物的存放，先從底層往上面堆，再?gòu)纳贤履茫且坏湫偷臈?。而乘客乘車（假設(shè)只有一個(gè)車門在前面），上車的人按從后往前的順序坐，下車時(shí)則按從前往后的順序下來，也是一種典型的棧。2023年11月28日33.1.2棧的運(yùn)算1．初始化棧：inistack(&s)將棧s置為一個(gè)空棧（不含任何元素）。2．進(jìn)棧：push(&s,x)將元素x插入到棧s中，也稱為“入?！?、“插入”、“壓入”。3．出棧：pop(&s)刪除棧s中的棧頂元素，也稱為“退棧”、“刪除”、“彈出”。4．取棧頂元素：gettop(s)取棧s中的棧頂元素。5．判?？眨篹mpty(s)判斷棧s是否為空，若為空，返回值為true或1，否則返回值為false或0。2023年11月28日43.1.3棧的抽象數(shù)據(jù)類型描述棧的抽象數(shù)據(jù)類型可描述為：ADTStackisData：含有n個(gè)元素a1,a2,a3,…,an，按LIFO規(guī)則存放，每個(gè)元素的類型都為elemtype。operation：voidinistack(&s) //將棧s置為一個(gè)空棧（不含任何元素）voidpush(&s,x) //將元素x插入到棧s中，也稱為“入?！薄ⅰ安迦搿?、“壓入”voidpop(&s) //刪除棧s中的棧頂元素，也稱為“退棧”、“刪除”、“彈出”elemtypegettop(s) //取棧s中的棧頂元素intempty(s) //判斷棧s是否為空，若為空，返回值為true或1，否則返回值為false或0Endstack2023年11月28日53.1.4順序棧

1．順序棧的數(shù)據(jù)類型棧的順序存儲(chǔ)結(jié)構(gòu)，也稱為順序棧，與順序表的數(shù)據(jù)類型描述類似，描述如下：CONSTintmaxsize=maxlen; //定義棧的最大容量為maxlenclassseqstack{public:elemtypestack[maxsize]; //將棧中元素定義為elemtype類型

inttop; //指向棧頂位置的指針voidinistack(&s); //將棧s置為一個(gè)空棧（不含任何元素）voidpush(&s,elemtypex); //將元素x插入到棧s中，也稱為“入棧”、“插入”、“壓入”voidpop(&s); //刪除棧s中的棧頂元素，也稱為“退?！?、“刪除”、“彈出”elemtypegettop(s); //取棧s中棧的頂元素boolempty(s); //判棧s是否為空};2023年11月28日62．棧的五種運(yùn)算棧的五種運(yùn)算實(shí)現(xiàn)過程如下：（規(guī)定棧中空間為1~maxsize-1，浪費(fèi)存儲(chǔ)位置０，是為了與線性表數(shù)組存儲(chǔ)對(duì)應(yīng)）。（1）初始化棧voidseqstack::inistack(seqstack&s){s.top=0;}（2）進(jìn)棧voidseqstack::push(seqstack&s,elemtypex){if(s.top==maxsize-1)cout<<"overflow";else{s.top++;s.stack[s.top]=x;}}2023年11月28日7（3）退棧voidseqstack::pop(seqstack&s){if(s.top==0)cout<<"underflow";elses.top--;}（4）取棧頂元素elemtypeseqstack::gettop(seqstacks){if(s.top==0){cout<<"underflow";return0;}elsereturns.stack[s.top];}（5）判棧空否

boolseqstack::empty(seqstacks){if(s.top==0)returntrue;elsereturnfalse;}2023年11月28日83．棧的共享存儲(chǔ)單元有時(shí)，一個(gè)程序設(shè)計(jì)中，需要使用多個(gè)同一類型的棧，這時(shí)，可能會(huì)產(chǎn)生一個(gè)棧空間過小，容量發(fā)生溢出，而另一個(gè)?？臻g過大，造成大量存儲(chǔ)單元浪費(fèi)的現(xiàn)象。為了充分利用各個(gè)棧的存儲(chǔ)空間，可以采用多個(gè)棧共享存儲(chǔ)單元，即給多個(gè)棧分配一個(gè)足夠大的存儲(chǔ)空間，讓多個(gè)棧實(shí)現(xiàn)存儲(chǔ)空間優(yōu)勢(shì)互補(bǔ)。下面以兩個(gè)棧為例來說明棧共享存儲(chǔ)空間(見下圖)設(shè)兩個(gè)棧共享一段內(nèi)存單元（一維數(shù)組），兩個(gè)棧的棧底分別設(shè)在一維數(shù)組的兩端，這時(shí)，若第一個(gè)棧發(fā)生溢出，而且第二個(gè)棧中還有多余空間，則可將第一個(gè)棧進(jìn)棧元素放入第二個(gè)棧；反之，若第二個(gè)棧發(fā)生溢出，而第一個(gè)棧中還有多余空間，則可將第二個(gè)棧進(jìn)棧元素放入第一個(gè)棧中。這樣就可以實(shí)現(xiàn)兩個(gè)棧的優(yōu)勢(shì)互補(bǔ)，只有當(dāng)兩個(gè)棧的棧頂相遇時(shí)，這時(shí)進(jìn)棧才會(huì)發(fā)生溢出，比兩個(gè)棧單獨(dú)使用進(jìn)棧發(fā)生溢出的可能性小得多。2023年11月28日9兩個(gè)棧共享存儲(chǔ)單元可用如下C++語句描述：CONSTintmaxsize=maxlen; //maxlen為共享單元的最大長(zhǎng)度classdbseqstack{public:elemtypestack[maxsize];inttop[2]; //兩個(gè)棧的棧頂指針voiddbinistack(dbseqstack&s,intk); //將第k個(gè)棧置為一個(gè)空棧（不含任何元素）voiddbpush(dbseqstack&s,elemtypex,intk); //將元素x插入到第k個(gè)棧中voiddbpop(dbseqstack&s,intk); //刪除第k個(gè)棧中的棧頂元素elemtypedbgettop(dbseqstacks,intk); //取第k個(gè)棧中的棧頂元素booldbempty(dbseqstacks,intk); //判第k個(gè)棧是否為空

};2023年11月28日10對(duì)于上述形式的棧共享存儲(chǔ)單元，棧的五種運(yùn)算可類似描述，現(xiàn)僅描述進(jìn)棧、退棧算法。（1）兩個(gè)棧共享存儲(chǔ)單元的進(jìn)棧算法voiddbseqstack::dbpush(dbseqstack&s,elemtypex,intk)//將元素x壓入到第k個(gè)棧中{if(s.top[0]+1==s.top[1])cout<<"overflow";elseif(k==0){s.top[0]++;s.stack[s.top[0]]=x;}else{s.top[1]--;s.stack[s.top[1]]=x;}}（2）兩個(gè)棧共享存儲(chǔ)單元的退棧算法voiddbseqstack::dbpop(dbseqstack&s,intk) //應(yīng)以s為?？臻g的棧中，對(duì)第k個(gè)棧進(jìn)行退棧{if((k==0)&&(s.top[0]==0))cout<<"underflow";elseif((k==1)&&(s.top[1]==maxsize)cout<<"underflow";elseif(k==0)s.top[0]--;elses.top[1]++;}2023年11月28日113.1.5鏈棧1．鏈棧結(jié)構(gòu)及數(shù)據(jù)類型棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱為鏈棧，它是一種限制運(yùn)算的鏈表，即規(guī)定鏈表中的插入和刪除運(yùn)算只能在鏈表開頭進(jìn)行。鏈棧結(jié)構(gòu)見下圖。鏈棧的數(shù)據(jù)類型描述與第2章介紹的單鏈表數(shù)據(jù)類型描述相同，在此不再重述。2023年11月28日122．鏈棧的五種棧運(yùn)算（1）棧初始化voidlink::inistack(link*top){top->next=NULL;}（2）進(jìn)棧運(yùn)算voidlink::push(link*top,intx){link*s;s=newlink;s->data=x;s->next=top->next;top->next=s;}2023年11月28日13（3）退棧運(yùn)算

voidlink::pop(link*top){link*s;s=top->next;if(s!=NULL){top->next=s->next;delete(s);}}（4）取棧頂元素elemtypelink::gettop(link*top){if(top->next!=NULL)returntop->next->data;elsereturnNULL;}2023年11月28日14（5）判?？誦oollink::empty(link*top){if(top->next==NULL)return(true);elsereturn(false);}從上述算法可知，它們的時(shí)間復(fù)雜度都為O(1)。3.1.6棧的應(yīng)用棧在日常生活中和計(jì)算機(jī)的程序設(shè)計(jì)中，有著許多重要的應(yīng)用。下面僅介紹棧在計(jì)算機(jī)中的一些應(yīng)用。2023年11月28日151．算術(shù)表達(dá)式的求值算術(shù)表達(dá)式中包含了算術(shù)運(yùn)算符和算術(shù)量（常量、變量、函數(shù)），而運(yùn)算符之間又存在著優(yōu)先級(jí)的問題，不能簡(jiǎn)單地進(jìn)行從左到右（C++中，有的運(yùn)算是從右到左的）的運(yùn)算，而必須先計(jì)算優(yōu)先級(jí)高的。編譯程序在求值時(shí)，不能簡(jiǎn)單從左到右運(yùn)算（或從右到左運(yùn)算），必須先算運(yùn)算級(jí)別高的，再算運(yùn)算級(jí)別低的，同一級(jí)運(yùn)算才按從左到右的順序（或從右到左運(yùn)算）。因此，要實(shí)現(xiàn)表達(dá)式求值，必須設(shè)置兩個(gè)棧，一個(gè)棧存放運(yùn)算符，另一個(gè)棧存放操作數(shù)（算術(shù)量），在進(jìn)行表達(dá)式求值時(shí)，編譯程序從左到右掃描，每遇到一個(gè)操作數(shù)，一律進(jìn)入操作數(shù)棧，每遇到一個(gè)運(yùn)算符，則應(yīng)與運(yùn)算符棧的棧頂進(jìn)行比較，若運(yùn)算符優(yōu)先級(jí)高于棧頂?shù)膬?yōu)先級(jí)，則進(jìn)棧，否則在運(yùn)算符棧中退棧，退棧后，在操作數(shù)棧中退出兩個(gè)元素（先退出的數(shù)放在退出運(yùn)算符右邊，后退出的數(shù)放在退出運(yùn)算符左邊），然后用運(yùn)算符棧中退出的棧頂元素進(jìn)行運(yùn)算，運(yùn)算的結(jié)果存入操作數(shù)棧中，直到掃描完畢。這時(shí)運(yùn)算符棧為空，操作數(shù)棧中只有一個(gè)元素，即為運(yùn)算的結(jié)果。2023年11月28日16【例1】用棧求1+2*3-4/2的值，棧的變化見表3-1。從表3-1可知，最后求出的表達(dá)式的值為5。當(dāng)然，算術(shù)表達(dá)式除了簡(jiǎn)單求值外，還會(huì)涉及算術(shù)表達(dá)式的兩種表示方法，即中綴表示法和后綴表示法。剛才的例1中的表達(dá)式就是中綴表達(dá)式，中綴表達(dá)式求值比較麻煩（須考慮運(yùn)算符的優(yōu)先級(jí)，甚至還要考慮圓括號(hào)，需要用到兩個(gè)棧），而后綴表達(dá)式求值比較方便（無須考慮運(yùn)算符的優(yōu)先級(jí)及圓括號(hào)，僅按從左到右的順序進(jìn)行即可，僅用到一個(gè)棧）。2023年11月28日17步驟操作數(shù)棧運(yùn)算符棧說明開始

開始時(shí)，兩個(gè)棧為空11掃描到“1”，進(jìn)入操作數(shù)棧21+掃描到“+”，進(jìn)入運(yùn)算符棧312+掃描到“2”，進(jìn)入操作數(shù)棧412+*掃描到“*”，進(jìn)入運(yùn)算符棧5123+*掃描到“3”，進(jìn)入操作數(shù)棧61+掃描到“-”，退棧716+2*3=6進(jìn)棧8

掃描到“-”，退棧97

1+6=7進(jìn)棧107-掃描到“-”，進(jìn)入運(yùn)算符棧1174-掃描到“4”，進(jìn)入操作數(shù)棧1274-／掃描到“/”，進(jìn)入運(yùn)算符棧13742-／掃描到“2”，進(jìn)入操作數(shù)棧147-掃描完，“/”“4”“2”退棧1572-4/2=2進(jìn)棧16“-”“7”“2”退棧1757-2=5進(jìn)棧表3-1表達(dá)式求值棧演示圖2023年11月28日18從前面的例題可以看出，中綴表達(dá)式求值比較麻煩，需用兩個(gè)棧來實(shí)現(xiàn)，并且如果出現(xiàn)圓括號(hào)時(shí)，運(yùn)算還要復(fù)雜些。那么，能否把中綴表達(dá)式轉(zhuǎn)換成另一種形式的算術(shù)表達(dá)式，使計(jì)算簡(jiǎn)單化呢？回答是肯定的。波蘭科學(xué)家盧卡謝維奇（Lukasiewicz）很早就提出了算術(shù)表達(dá)式的另一種表示，即后綴表達(dá)式，也稱為逆波蘭式，其定義規(guī)則是把運(yùn)算符放在兩個(gè)操作數(shù)后面。在后綴表達(dá)式中，不存在括號(hào)，也不存在運(yùn)算符優(yōu)先級(jí)問題，計(jì)算過程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，比中綴表達(dá)式的求值要簡(jiǎn)單得多。2023年11月28日19例如，對(duì)于下列各中綴表達(dá)式：（1）3/5+8（2）18-9*(4+3)（3）(25+x)*(a*(a+b)+b)上面三個(gè)中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式為：（1）35/8+（2）18943+*-（3）25x+aab+*b+*2023年11月28日202．中綴表達(dá)式變成等價(jià)的后綴表達(dá)式將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式，表達(dá)式中操作數(shù)的相對(duì)次序不發(fā)生變化，運(yùn)算符相對(duì)次序?qū)?huì)發(fā)生變化，同時(shí)去掉了表達(dá)式中的圓括號(hào)。轉(zhuǎn)換規(guī)則是：設(shè)立一個(gè)堆棧，用來存放表達(dá)式中的運(yùn)算符。首先設(shè)棧為空，編譯程序從左到右掃描中綴表達(dá)式，每次遇到操作數(shù)，直接將其輸出，并接著輸出一個(gè)空格作為兩個(gè)操作數(shù)的分隔符；若遇到一個(gè)運(yùn)算符，則必須與棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)比較，若運(yùn)算符級(jí)別比棧頂運(yùn)算符級(jí)別高，則進(jìn)棧，否則退出棧頂元素，并直接輸出，然后輸出一個(gè)空格作為分隔符；若掃描時(shí)遇到左括號(hào)，進(jìn)棧；若掃描時(shí)遇到右括號(hào)，則一直退棧輸出，直到退到左括號(hào)止。當(dāng)棧已經(jīng)變成空時(shí)，輸出的結(jié)果即為所求的后綴表達(dá)式。【例2】將中綴表達(dá)式(1+2)*((8-2)/(7-4))變成等價(jià)的后綴表達(dá)式?，F(xiàn)在用棧來實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果見表3-2。2023年11月28日21步驟棧中元素輸出結(jié)果說明1(（進(jìn)棧2(1輸出13(+1+進(jìn)棧4(+12輸出2512++退棧并輸出，退棧到（止6*12+*進(jìn)棧7*(12+（進(jìn)棧8*((12+（進(jìn)棧9*((12+8輸出810*((-12+8-進(jìn)棧11*((-12+82輸出212*(12+82--退棧并輸出，退棧到（止13*(/12+82-/進(jìn)棧14*(/(12+82-（進(jìn)棧15*(/(12+82-7輸出716*(/(-12+82-7-進(jìn)棧17*(/(-12+82-74輸出418*(/12+82-74--退棧并輸出，退棧到（止19*12+82-74-//退棧并輸出，退棧到（止2012+82-74-/**退棧并輸出表3-2中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式示意圖2023年11月28日22從表3-2可知，中綴表達(dá)式(1+2)*((8-2)/(7-4))變成的后綴表達(dá)式為：12+82-74-/*3．后綴表達(dá)式的求值將中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式后，求值時(shí)，不需要再考慮運(yùn)算符的優(yōu)先級(jí)，只需從左到右掃描一遍后綴表達(dá)式即可。具體求值步驟為：設(shè)置一個(gè)棧，開始時(shí)，棧為空，然后從左到右掃描后綴表達(dá)式，若遇操作數(shù)，則進(jìn)棧；若遇運(yùn)算符，則從棧中退出兩個(gè)元素，先退出的放到運(yùn)算符的右邊，后退出的放到運(yùn)算符的左邊，運(yùn)算后的結(jié)果再進(jìn)棧，直到后綴表達(dá)式掃描完畢。此時(shí)，棧中僅有一個(gè)元素，即為運(yùn)算的結(jié)果?！纠?】求上例中轉(zhuǎn)換得到的后綴表達(dá)式12+82-74-/*之值。該求值過程可用一個(gè)棧來描述，棧中最后的結(jié)果即為后綴表達(dá)式的值（應(yīng)該與用中綴表達(dá)式求出的結(jié)果相同），具體見表3-3。從表3-3可知，最后求得的后綴表達(dá)式之值為6，與用中綴表達(dá)式求得的結(jié)果一致，但后綴表達(dá)式求值要簡(jiǎn)單得多。2023年11月28日23表3-3后綴表達(dá)式求值示意圖步驟棧中元素說明111進(jìn)棧2122進(jìn)棧3遇+號(hào)退棧2和1431+2=3的結(jié)果3進(jìn)棧5388進(jìn)棧63822進(jìn)棧73遇-號(hào)退棧2和88368-2=6的結(jié)果6進(jìn)棧93677進(jìn)棧1036744進(jìn)棧1136遇-號(hào)退棧4和7123637-4=3的結(jié)果3進(jìn)棧133遇/號(hào)退棧3和614326/3=2的結(jié)果2進(jìn)棧15遇*號(hào)退棧2和31663*2=6進(jìn)棧176掃描完畢，運(yùn)算結(jié)束2023年11月28日244．函數(shù)的嵌套調(diào)用在函數(shù)嵌套調(diào)用中，一個(gè)函數(shù)的執(zhí)行沒有結(jié)束，又開始另一個(gè)函數(shù)的執(zhí)行，因此必須用棧來保存函數(shù)中斷的地址，以便調(diào)用返回時(shí)能從斷點(diǎn)繼續(xù)往下執(zhí)行?！纠?】設(shè)有一個(gè)主程序，它調(diào)用函數(shù)a，函數(shù)a又調(diào)用函數(shù)b，函數(shù)b又調(diào)用函數(shù)c，（見下圖），其中r，s，t分別表示中斷地址。2023年11月28日25在上圖中，主程序調(diào)用函數(shù)a，留下一個(gè)斷點(diǎn)地址r進(jìn)棧，然后主函數(shù)處于掛起狀態(tài)，進(jìn)入函數(shù)a中執(zhí)行，函數(shù)a中再調(diào)用函數(shù)b，留下一個(gè)斷點(diǎn)地址s進(jìn)棧，然后函數(shù)a處于掛起狀態(tài)，進(jìn)入函數(shù)b中執(zhí)行，函數(shù)b中調(diào)用函數(shù)c，留下一個(gè)斷點(diǎn)地址t進(jìn)棧，然后函數(shù)b處于掛起狀態(tài)，進(jìn)入函數(shù)c中執(zhí)行，函數(shù)c執(zhí)行完后，要返回?cái)帱c(diǎn)處繼續(xù)執(zhí)行，但返回到哪一個(gè)斷點(diǎn)呢?根據(jù)棧頂元素來決定。返回時(shí)，執(zhí)行退棧操作，先退出t，故返回t斷點(diǎn)繼續(xù)執(zhí)行，接著退棧退出s，故返回s斷點(diǎn)繼續(xù)執(zhí)行，接著退棧退出r，返回r斷點(diǎn)繼續(xù)執(zhí)行，最后棧為空，算法結(jié)束。我們可以用一個(gè)棧來描述調(diào)用情況（見下圖的(a)~(f)）。2023年11月28日26

（a）調(diào)用a函數(shù)，r進(jìn)棧（b）調(diào)用b函數(shù)，s進(jìn)棧（c）調(diào)用c函數(shù)，t進(jìn)棧（d）返回b函數(shù)，t退棧（e）返回a函數(shù)，s退棧（f）返回主程序，r退棧2023年11月28日275．函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用也是一種嵌套，故也必須用棧來保存斷點(diǎn)信息，但遞歸調(diào)用相當(dāng)于同一個(gè)函數(shù)的嵌套調(diào)用，故除了保存斷點(diǎn)信息外，還必須保存每一層的參數(shù)、局部變量等。【例5】求n!可用遞歸函數(shù)描述如下：

1 n=0n!＝

n*(n-1)! n>0可以用一個(gè)棧來描述求解過程（設(shè)n=4，棧變化情形見下圖）。開始時(shí)，棧為空，見下圖（a），接著棧中保存4和3！，見下圖（b），再接著調(diào)用3！，棧中保存3和2！，見下圖（c），接著調(diào)用2！，棧中保存2和1！，見下圖（d），接著調(diào)用1！，棧中保存1和0!，見下圖（e），接著調(diào)用0！，而0！值已知為1，故返回，1和0！退棧，見下圖（f），同時(shí)得到1！（1*0!=1）值為1，然后，2和1！退棧，見下圖（g），同時(shí)得到2?。?*1!=2）值為2，然后，3和2！退棧，見下圖（h），同時(shí)得到3?。?*2!=6）值為6，然后4和3！退棧，見下圖（i），同時(shí)得到4?。?*3!=24）值為24，這時(shí)，棧已經(jīng)為空，算法結(jié)束，故最后得到的結(jié)果為24，即4！=24。2023年11月28日282023年11月28日293.2隊(duì)列3.2.1隊(duì)列的定義僅允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，稱為隊(duì)列（queue）。允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。隊(duì)列的含義與我們?nèi)粘Ｉ钪械亩喾N排隊(duì)現(xiàn)象相類似，后來的人只能排在隊(duì)尾（插入），先來排隊(duì)的人，可以先辦完事先離開（刪除）。因此，隊(duì)列是一種先進(jìn)先出（FirstInFirstOut）的特殊線性表，或稱FIFO表。若隊(duì)列中沒有任何元素，則稱為空隊(duì)列，否則稱為非空隊(duì)列。隊(duì)列的描述如下圖所示。2023年11月28日303.2.2隊(duì)列的基本運(yùn)算隊(duì)列可定義如下五種基本運(yùn)算：1．初始化隊(duì)列INIQUEUE(&Q)將隊(duì)列Q設(shè)置成一個(gè)空隊(duì)列。2．入隊(duì)列ENQUEUE(&Q,X)將元素X插入到隊(duì)尾中，也稱“進(jìn)隊(duì)”，“插入”。3．出隊(duì)列DLQUEUE(&Q)將隊(duì)列Q的隊(duì)頭元素刪除，也稱“退隊(duì)”、“刪除”。4．取隊(duì)頭元素GETHEAD(Q)得到隊(duì)列Q的隊(duì)頭元素之值。2023年11月28日315．判隊(duì)空EMPTY(Q)判斷隊(duì)列Q是否為空，若為空返回1，否則返回0。3.2.3隊(duì)列的抽象數(shù)據(jù)類型描述隊(duì)列的抽象數(shù)據(jù)類型可描述為：ADTQUEUEISData：含有n個(gè)元素a1,a2,a3,…an，按FIFO規(guī)則存放，每個(gè)元素的類型為elemtype。Operation：voidINIQUEUE(&Q) //將隊(duì)列Q設(shè)置成一個(gè)空隊(duì)列voidENQUEUE(&Q,X) //將元素X插入到隊(duì)尾中，也稱“進(jìn)隊(duì)”，“插入”voidDLQUEUE(&Q) //將隊(duì)列Q的隊(duì)頭元素刪除，也稱“退隊(duì)”、“刪除”elemtypeGETHEAD(Q) //得到隊(duì)列Q的隊(duì)頭元素之值intEMPTY(Q) //判斷隊(duì)列Q是否為空，若為空返回1，否則返回0Endqueue2023年11月28日323.2.4循環(huán)隊(duì)列1．隊(duì)列的順序存儲(chǔ)數(shù)據(jù)類型描述CONSTintmaxsize=maxlen; //定義隊(duì)列的最大容量為maxlenclassseqqueue{public:elemtypequeue[maxsize]; //將隊(duì)列中元素定為數(shù)組型，元素類型為elemtypeintfront; //隊(duì)頭指針intrear; //隊(duì)尾指針voidINIQUEUE(&Q) //將隊(duì)列Q設(shè)置成一個(gè)空隊(duì)列voidENQUEUE(&Q,X) //將元素X插入到隊(duì)尾中，也稱“進(jìn)隊(duì)”，“插入”voidDLQUEUE(&Q) //將隊(duì)列Q的隊(duì)頭元素刪除，也稱“退隊(duì)”、“刪除”ElemtypeGETHEAD(Q) //得到隊(duì)列Q的隊(duì)頭元素之值boolEMPTY(Q) //判斷隊(duì)列Q是否為空，若為空返回真，否則返回假};2023年11月28日332．順序隊(duì)列將隊(duì)列中元素全部存入一個(gè)一維數(shù)組中，數(shù)組的低下標(biāo)一端為隊(duì)頭，高下標(biāo)一端為隊(duì)尾，將這樣的隊(duì)列看成是順序隊(duì)列。在順序隊(duì)列中，隊(duì)列的存儲(chǔ)空間為從queue[0]到queue[maxsize-1]，則判斷隊(duì)列為空的條件為front=rear=-1，若有一個(gè)元素進(jìn)隊(duì)，則rear的值增1，若有一個(gè)元素出隊(duì)，則front的值增1。為了與我們的日常規(guī)定相符，建議順序隊(duì)列的存儲(chǔ)空間為從queue[1]到queue[maxsize]，此時(shí)隊(duì)列為空的條件變成front=rear=0。雖然浪費(fèi)一個(gè)存儲(chǔ)單元queue[0]，但可以給我們的操作帶來方便。設(shè)一個(gè)順序隊(duì)列為(a1,a2,a3,a4,a5)，對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)見下圖（a），此時(shí)front=0,rear=5，若有一個(gè)元素a6進(jìn)隊(duì)，見下圖（b），此時(shí)front=0,rear=6，若有連續(xù)三個(gè)元素a1,a2,a3出隊(duì)，見下圖（c），此時(shí)front=3,rear=6，若所有元素都出隊(duì)，見下圖（d），此時(shí)front=6,rear=6，隊(duì)列也變?yōu)榭?，即有front=rear時(shí)，隊(duì)列為空。因此，隊(duì)列為空的條件是front=rear。2023年11月28日34（a）a1,a2,a3,a4,a5進(jìn)隊(duì)后的順序隊(duì)列（b）a1,a2,a3,a4,a5,a6進(jìn)隊(duì)后的順序隊(duì)列（c）a1,a2,a3出隊(duì)后的順序隊(duì)列（d）元素全部出隊(duì)后的順序隊(duì)列2023年11月28日35若一維數(shù)組中所有位置都被元素裝滿，稱為隊(duì)滿，即尾指針rear指向一維數(shù)組最后，而頭指針指向一維數(shù)組開頭，稱為隊(duì)滿。但有可能出現(xiàn)這樣的情況，尾指針指向一維數(shù)組最后，但前面有很多元素已經(jīng)出隊(duì)，即空出很多位置，這時(shí)要插入元素，仍然會(huì)發(fā)生溢出。例如，在上圖（d）中，若隊(duì)列的最大容量maxsize=9，此時(shí)，front=rear=6，若再有元素a7，a8，a9進(jìn)隊(duì)，front=6，rear=9，這時(shí)，若有元素a10進(jìn)隊(duì)，將發(fā)生溢出。我們將這種溢出稱為“假溢出”，因?yàn)閒ront的前面有6個(gè)空位置，還能裝6個(gè)元素。要克服“假溢出”，可以將整個(gè)隊(duì)列中的元素向前移動(dòng)，直到頭指針front為零，或者每次出隊(duì)時(shí)，都將隊(duì)列中的元素前移一個(gè)位置。因此，順序隊(duì)列的隊(duì)滿判定條件為rear=maxsize。但是，在順序隊(duì)列中，這些克服“假溢出”的方法都會(huì)引起大量元素的移動(dòng)，花費(fèi)大量的時(shí)間，所以在實(shí)際應(yīng)用中很少采用，一般采用下面的循環(huán)隊(duì)列形式。2023年11月28日363．循環(huán)隊(duì)列為了克服順序隊(duì)列中假溢出，通常將一維數(shù)組queue[0]到q[maxsize-1]看成是一個(gè)首尾相接的圓環(huán)，即queue[0]與queue[maxsize-1]相接在一起。將這種形式的順序隊(duì)列稱為循環(huán)隊(duì)列，見下圖。2023年11月28日37這時(shí)，可以不必浪費(fèi)存儲(chǔ)單元queue[0]，但是，必須規(guī)定頭指針front指向的是隊(duì)頭前一位置，尾指針rear指向當(dāng)前隊(duì)尾。在循環(huán)隊(duì)列中，若front=rear,則稱為隊(duì)空，若(rear+1)%maxsize=front，則稱為隊(duì)滿，這時(shí)，循環(huán)隊(duì)列中能裝入的元素個(gè)數(shù)為maxsize-1，即浪費(fèi)一個(gè)存儲(chǔ)單元，但是這樣可以給操作帶來較大方便。4．循環(huán)隊(duì)列上五種運(yùn)算的實(shí)現(xiàn)（1）隊(duì)列初始化

voidseqqueue::INIQUEUE(seqqueue&Q){Q.front=Q.rear=maxsize-1;}2023年11月28日38（2）進(jìn)隊(duì)列voidseqqueue::ENQUEUE(seqqueue&Q,elemtypex){if((Q.rear+1)%maxsize==Q.front)cout<<"overflow";else{Q.rear=(Q.rear+1)%maxsize;Q.queue[Q.rear]=x;}}（3）出隊(duì)列voidseqqueue::DLQUEUE(seqqueue&Q){if(Q.rear==Q.front)cout<<"underflow";elseQ.front=(Q.front+1)%maxsize;}2023年11月28日39（4）取隊(duì)頭元素（注意得到的應(yīng)為頭指針后面一個(gè)位置值）elemtypeseqqueue::GETHEAD(seqqueueQ){if(Q.rear==Q.front){cout<<"underflow";returnNULL;}elsereturnQ.queue[(Q.front+1)%maxsize];}（5）判隊(duì)列空否boolseqqueue::EMPTY(seqqueueQ){if(Q.rear==Q.front)returntrue;elsereturnfalse;}2023年11月28日403.2.5鏈隊(duì)列1．鏈隊(duì)列的數(shù)據(jù)類型描述隊(duì)列的鏈?zhǔn)酱鎯?chǔ)，稱為鏈隊(duì)列，與前面介紹的單鏈表類似，但為了使頭指針、尾指針統(tǒng)一起來，另外定義了一種數(shù)據(jù)類型。因此鏈隊(duì)列可用C++描述如下。classlink //定義單鏈表數(shù)據(jù)類型

{public:elemtypedata;link*next;};classlinkqueue //定義鏈隊(duì)列數(shù)據(jù)類型

{public:link*front,*rear; //定義頭指針和尾指針voidiniqueue(linkqueue&s);voidenqueue(linkqueue&s,elemtypex);boolempty(linkqueues);elemtypegethead(linkqueues);voiddlqueue(linkqueue&s);};2023年11月28日41鏈隊(duì)列如下圖所示。（a）空鏈隊(duì)列（b）非空鏈隊(duì)列2023年11月28日422．鏈隊(duì)列上的基本運(yùn)算同樣，鏈隊(duì)列上也可以給出五種運(yùn)算如下：（1）鏈隊(duì)列上的初始化voidlinkqueue::iniqueue(linkque