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

第3章棧和隊列BasicSortingAlgorithms3.1棧（Stack）

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

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

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

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

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

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

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

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

:front=rear(初始化時：front=rear)隊滿條件：

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

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

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

問1:左圖中隊列maxsizeM=？J2J3 J1J4

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

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

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