數(shù)據(jù)結(jié)構(gòu)第3章

第3章棧和隊(duì)列BasicSortingAlgorithms3.1棧（Stack）

第三章棧和隊(duì)列3.2隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式3.2隊(duì)列1.定義與同線性表相同，仍為一對(duì)一關(guān)系。順序隊(duì)或鏈隊(duì)，以循環(huán)順序隊(duì)更常見。只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照先進(jìn)先出（FIFO）的原則。關(guān)鍵是掌握入隊(duì)和出隊(duì)操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同。3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式2.邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表（頭刪尾插）基本操作有入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。表尾即an端，稱為隊(duì)尾

；表頭即a1端，稱為隊(duì)頭。它是一種先進(jìn)先出（ＦＩＦＯ）的線性表。例如：隊(duì)列Q=(a1,a2,a3,……….,an-1,an)插入元素稱為入隊(duì)；刪除元素稱為出隊(duì)。隊(duì)頭隊(duì)尾教材P89對(duì)隊(duì)列有更詳細(xì)定義：隊(duì)列的抽象數(shù)據(jù)類型定義見教材Ｐ89隊(duì)列的存儲(chǔ)結(jié)構(gòu)為鏈隊(duì)或順序隊(duì)

（常用循環(huán)順序隊(duì)）53.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)非循環(huán)隊(duì)列的基本運(yùn)算循環(huán)隊(duì)列的基本運(yùn)算順序隊(duì)列的表示和實(shí)現(xiàn)6可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一個(gè)隊(duì)列，其中使用一個(gè)數(shù)組data和兩個(gè)整數(shù)型變量。數(shù)組data順序存儲(chǔ)隊(duì)列中所有元素，兩個(gè)整型變量front和rear分別作為隊(duì)首指針和隊(duì)尾指針。順序隊(duì)列類SqQueueClass的定義如下（本小節(jié)的所有算法均包含在此類中）：classSqStackClass{constintMaxSize=100;//最多元素個(gè)數(shù)publicstring[]data;//存放隊(duì)中的元素publicintfront,rear;//隊(duì)頭和隊(duì)尾指針publicSqStackClass()//構(gòu)造函數(shù)，用于初始化隊(duì)列{data=newstring[MaxSize];front=rear=x;//通常情況下，循環(huán)隊(duì)列x為0，非循環(huán)隊(duì)列x為-1}//順序隊(duì)的基本運(yùn)算};7非循環(huán)隊(duì)列，初始化時(shí)置front=rear=-1隊(duì)空的條件為front==rearrear==Maxsize-1入隊(duì)：元素e進(jìn)隊(duì)的操作是先將隊(duì)尾指針rear增1，然后將e放在隊(duì)尾處出隊(duì)：出隊(duì)操作是先將隊(duì)頭指針front增1，然后取出隊(duì)頭處的元素（1）非循環(huán)隊(duì)列的基本運(yùn)算8若隊(duì)列滿足front==rear條件，則返回true；否則返回false。對(duì)應(yīng)算法如下：publicboolQueueEmpty(){return(front==rear);}1)判斷隊(duì)列是否為空QueueEmpty()9元素進(jìn)隊(duì)只能從隊(duì)尾進(jìn)，不能從隊(duì)頭或中間位置進(jìn)隊(duì)。在進(jìn)隊(duì)運(yùn)算中，在隊(duì)列不滿的條件下，先將隊(duì)尾指針rear增1，然后元素e放到該位置處。對(duì)應(yīng)算法如下：publicboolPush(stringx){if(rear==MaxSize-1)//隊(duì)滿上溢出，返回falsereturnfalse;rear++;//隊(duì)尾指針增1data[rear]=x;returntrue;}2)進(jìn)隊(duì)運(yùn)算enQueue(e)10元素出隊(duì)只能從隊(duì)頭出，不能從隊(duì)頭或中間位置出隊(duì)。在出隊(duì)運(yùn)算中，在隊(duì)列不為空的條件下，將隊(duì)首指針front增1，并將該位置的元素值賦給e。對(duì)應(yīng)算法如下：publicbooldeQueue(refstringe){if(front==rear)//隊(duì)空下溢出時(shí)，返回falsereturnfalse;front++;e=data[front];returntrue;}3)出隊(duì)列deQueue(e)3.2隊(duì)列1.存在問題設(shè)數(shù)組維數(shù)為M，則：當(dāng)front=-1,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出

——真溢出當(dāng)front-1,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出

——假溢出問：什么叫“假溢出”？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。2.解決方案循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：sq[rear]=x;

rear=(rear+1)%M;出隊(duì)：front=(front+1)%M;x=sq[front];

0M-11frontrear…...…...假溢出a3a2a10123M-1rearfront循環(huán)隊(duì)列（臆造）順序隊(duì)列a3a2a1frontrear0123..N-1循環(huán)隊(duì)列新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①加設(shè)標(biāo)志位，讓刪除動(dòng)作使其為1,插入動(dòng)作使其為0,則可識(shí)別當(dāng)前front=rear②使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長度)③人為浪費(fèi)一個(gè)單元，令隊(duì)滿特征為

front=(rear+1)%M；循環(huán)隊(duì)列012345rearfrontJ4J5J6123405J9J8J7rearfrontJ4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==rear解決方案：少用一個(gè)元素空間：隊(duì)空：front==rear隊(duì)滿：(rear+1)%M==front隊(duì)空條件

:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：

front=(rear+1)%M(M=maxsize)隊(duì)列長度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（M＋rear－front）%M

選用空閑單元法：即front和rear之一指向?qū)嵲?，另一指向空閑元素

問3：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？n-1個(gè)6

問1:左圖中隊(duì)列maxsizeM=？J2J3 J1J4

J5frontrear問2：左圖中隊(duì)列長度L=？5方案三:17若隊(duì)列滿足front==rear條件，則返回true；否則返回false。對(duì)應(yīng)算法如下：publicboolQueueEmpty(){return(front==rear);}1)判斷隊(duì)列是否為空QueueEmpty(q)18在進(jìn)隊(duì)運(yùn)算中，在隊(duì)列不滿的條件下，先將隊(duì)尾指針rear循環(huán)增1，然后元素e放到該位置處。對(duì)應(yīng)算法如下：publicboolenQueue(stringe){if((rear+1)%MaxSize==front)//隊(duì)滿上溢出returnfalse;rear=(rear+1)&MaxSize;//隊(duì)尾指針增1data[rear]=x;returntrue;}2)進(jìn)隊(duì)運(yùn)算enQueue(q,e)19在出隊(duì)運(yùn)算中，在隊(duì)列不為空的條件下，將隊(duì)首指針front循環(huán)增1，并將該位置的元素值賦給e。對(duì)應(yīng)算法如下：publicbooldeQueue(refstringe){if(front==rear)//隊(duì)空下溢出時(shí)，返回falsereturnfalse;front=(front+1)%MaxSize;e=data[front];returntrue;}3)出隊(duì)列deQueue(q,e)例【3.7】對(duì)于循環(huán)隊(duì)列來說，如果知道隊(duì)頭指針和隊(duì)尾指針中的元素個(gè)數(shù)，則可以計(jì)算出隊(duì)尾指針。也就是說，可以用隊(duì)列中的元素個(gè)數(shù)代替隊(duì)尾指針。設(shè)計(jì)出循環(huán)隊(duì)列的進(jìn)隊(duì)、出隊(duì)、判隊(duì)空和求隊(duì)中元素個(gè)數(shù)的算法。20解：本例的循環(huán)隊(duì)列包含data數(shù)組、隊(duì)頭指針rear和隊(duì)中的元素個(gè)數(shù)count字段。初始時(shí)front和count均置為0。隊(duì)空的條件為count==0；隊(duì)滿的條件為count==MaxSize；元素e進(jìn)隊(duì)操作是，先根據(jù)隊(duì)頭指針和元素個(gè)數(shù)求出隊(duì)尾指針rear，將rear循環(huán)增1，然后將元素e放置在rear處；出隊(duì)操作是，先將隊(duì)首指針循環(huán)增1，然后取出該位置的元素。設(shè)計(jì)對(duì)應(yīng)的循環(huán)隊(duì)列類SqQueueClass2如下：21ClassSqQueueClass2{constintMaxSize=5;privatestring[]data;//存放隊(duì)中的元素privateintfront;//隊(duì)頭指針privateintcount;//隊(duì)列中的元素個(gè)數(shù)publicSqQueueClass2(){data=newstring[MaxSize]；//構(gòu)造函數(shù)，用于隊(duì)列初始化front=0;count=0;}//順序隊(duì)基本運(yùn)算算法22publicboolQueueEmpty()//判斷隊(duì)列是否為空{(diào)return(count==0);}publicboolenQueue(stringe)//進(jìn)隊(duì)算法{intrear;rear=(front+count)%MaxSize;if(count==MaxSize)returnfalse;rear=(rear+1)%MaxSize;data[rear]=e;count++;returntrue;}23publicintGetCount()//求隊(duì)列中的元素個(gè)數(shù){returncount;}publicbooldeQueue(refstringe)//出隊(duì)算法{if(count==0)returnfalse;front=(front+1)%MaxSize;e=data[front];count--;returntrue;}}243.2.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)鏈隊(duì)列的表示實(shí)現(xiàn)鏈隊(duì)列的基本運(yùn)算鏈隊(duì)列示意圖討論：空隊(duì)列的特征？Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearpfront^rear③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？入隊(duì)（尾部插入）：rear.next=S;rear=S;出隊(duì)（頭部刪除）：front.next=p.next;②隊(duì)列會(huì)滿嗎？front=rear一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足?。?）鏈隊(duì)列的表示和實(shí)現(xiàn)26隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是通過由結(jié)點(diǎn)構(gòu)成的單鏈表實(shí)現(xiàn)的，此時(shí)只允許在單鏈表的表首進(jìn)行刪除操作和在單鏈表表尾進(jìn)行插入操作。因此需要使用兩個(gè)指針：隊(duì)首指針front和隊(duì)尾指針rear。用front指向隊(duì)首結(jié)點(diǎn)，用rear指向隊(duì)尾結(jié)點(diǎn)。用于存儲(chǔ)隊(duì)列的單鏈表稱為鏈隊(duì)。鏈隊(duì)數(shù)據(jù)結(jié)點(diǎn)類LinkNode的定義如下：classLinkNode//鏈隊(duì)數(shù)據(jù)結(jié)點(diǎn)類{publicstringdata;//結(jié)點(diǎn)數(shù)據(jù)字段publicLinkNodenext;//指向下一個(gè)結(jié)點(diǎn)

};27鏈隊(duì)結(jié)點(diǎn)類LinkQueue的定義如下：classLinkQueue//鏈隊(duì)結(jié)點(diǎn)類{publicLinkQueuefront;//指向隊(duì)頭結(jié)點(diǎn)publicLinkQueuerear;//指向隊(duì)尾結(jié)點(diǎn)

};鏈隊(duì)類LinkQueueClass的定義如下：classLinkQueueClass//鏈隊(duì)結(jié)點(diǎn){LinkQueueQ=newLinkQueue();publicLinkQueueClass()//構(gòu)造函數(shù)，用于初始化{Q.front=null;Q.rear=null;}//鏈隊(duì)的基本運(yùn)算算法};28若隊(duì)列滿足rear==null條件，則返回true；否則返回false。對(duì)應(yīng)算法如下：publicboolQueueEmpty(){return(rear==null);}1)判斷隊(duì)列是否為空QueueEmpty(q)29創(chuàng)建data域?yàn)閑的數(shù)據(jù)結(jié)點(diǎn)p。若原隊(duì)列為空，則將鏈隊(duì)結(jié)點(diǎn)的兩個(gè)域均指向p結(jié)點(diǎn)，否則，將p結(jié)點(diǎn)鏈到單鏈表的末尾，并讓鏈隊(duì)結(jié)點(diǎn)的rear域指向它。對(duì)應(yīng)算法如下：publicboolenQueue(stringe){LinkNodep=newLinkNode();p.data=e;p.next=null;if(Q.rear==null)//若鏈隊(duì)為空，則新結(jié)點(diǎn)是隊(duì)首結(jié)點(diǎn)，又是隊(duì)尾結(jié)點(diǎn)Q.front=Q.rear=p;else{Q.rear.next=p;//將p結(jié)點(diǎn)鏈到隊(duì)尾，并將rear指向它Q.rear=p;}}2)進(jìn)隊(duì)運(yùn)算enQueue(e)30若原隊(duì)列不為空，則將第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的data域值賦給e,并刪除它。若出隊(duì)前隊(duì)列只有一個(gè)結(jié)點(diǎn)，則需將鏈隊(duì)結(jié)點(diǎn)的兩個(gè)域均置為null，表示隊(duì)列已為空。對(duì)應(yīng)算法如下：publicbooldeQueue(refstringe){LinkNodep;if(Q.rear==null)//隊(duì)列為空returnfalse;p=Q.front;if(Q.front==Q.rear)//p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)Q.front=Q.rear=null;//隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)elseQ.front=Q.front.next;//隊(duì)列中有多個(gè)結(jié)點(diǎn)時(shí)e=p.data;p=null;returntrue;}3)出隊(duì)列deQueue(e)例【3.8】采用一個(gè)不帶頭結(jié)點(diǎn)，只有一個(gè)尾結(jié)點(diǎn)指針rear的循環(huán)單鏈表存儲(chǔ)隊(duì)列，設(shè)計(jì)出這種鏈隊(duì)的進(jìn)隊(duì)、出隊(duì)、判隊(duì)空和求隊(duì)中元素個(gè)數(shù)的算法。31解：用只有尾結(jié)點(diǎn)指針rear的循環(huán)單鏈表作為隊(duì)列存儲(chǔ)結(jié)構(gòu)，其中每個(gè)結(jié)點(diǎn)的類型為LinkNode。當(dāng)這樣的鏈隊(duì)列中沒有結(jié)點(diǎn)時(shí)，隊(duì)列為空，即rear==null；進(jìn)隊(duì)在鏈表的表尾進(jìn)行，出隊(duì)在鏈表的表頭進(jìn)行。這樣的鏈隊(duì)類LinkQueueClass2的定義如下：ClassLinkQueueClass2{LinkNoderear;//鏈隊(duì)隊(duì)尾指針publicLinkQueueClass2()//構(gòu)造函數(shù)，用于初始化{rear=null;}publicboolQueueEmpty()//判隊(duì)空運(yùn)算算法{return(rear==null);}32publicvoidenQueue(stringe)//進(jìn)隊(duì)運(yùn)算算法{L