數(shù)據(jù)結(jié)構(gòu)解說演示課件

第3章 隊列,與棧一樣，隊列也是一種操作受限的線性表。隊列在操作系統(tǒng)和事務(wù)管理等軟件設(shè)計中應(yīng)用廣泛，如鍵盤輸入緩沖區(qū)問題就是利用隊列的思想實現(xiàn)的。 本章重點和難點： 1、隊列的順序表示與實現(xiàn) 2、隊列的鏈?zhǔn)奖硎九c實現(xiàn),3.1 隊列的定義與抽象數(shù)據(jù)類型,隊列只允許在表的一端進(jìn)行插入操作，在表的另一端進(jìn)行刪除操作。3.1.1 什么是隊列 隊列（queue）是一種先進(jìn)先出（first in first out，縮寫為FIFO）的線性表，它只允許在表的一端進(jìn)行插入，另一端刪除元素。這與我們?nèi)粘Ｉ钪械呐抨犑且恢碌?，最早進(jìn)入隊列的元素最早離開。在隊列中，允許插入的一端稱為隊頭（front），允許刪除的一端稱為隊尾（rear）。因此又稱隊列為先進(jìn)先出（FIFO）表。,3.1 隊列的定義與抽象數(shù)據(jù)類型,假設(shè)隊列為q=（a1，a2，ai，an），那么a1為隊頭元素，an為隊尾元素。進(jìn)入隊列時，是按照a1，a2，an的順序進(jìn)入的，退出隊列時也是按照這個順序退出的。也就是說，當(dāng)先進(jìn)入隊列的元素都退出之后，后進(jìn)入隊列的元素才能退出。即只有當(dāng)a1，a2，an-1都退出隊列以后，an才能退出隊列。,3.1 隊列的定義與抽象數(shù)據(jù)類型,2基本操作集合（1）置空隊列InitQueue(Q)：初始化操作，建立一個空隊列Q。（2）判隊列空QueueEmpty(Q)：若Q為空隊列，返回1，否則返回0。（3）入隊列EnQueue(Q,x)：若隊列不滿，插入元素x到隊列Q的隊尾。（4）出隊列DeQueue(Q)：若隊列不空，刪除隊頭元素，并返回該元素。（5）取隊頭Gethead(Q)：若隊列不空，返回隊頭元素。（,3.2 隊列的順序存儲及實現(xiàn),3.2.1 順序隊列的表示 順序隊列通常采用一維數(shù)組依次存放從隊頭到隊尾的元素。同時，使用兩個指針分別指示數(shù)組中存放的第一個元素和最后一個元素的位置。其中，指向第一個元素的指針被稱為隊頭指針front，指向最后一個元素的指針被稱為隊尾指針rear。 元素a、b、c、d、e、f、g依次進(jìn)入隊列后的狀態(tài)如圖3.2所示。元素a存放在數(shù)組下標(biāo)為0的存儲單元中，g存放在下標(biāo)為6的存儲單元中，隊頭指針front指向第一個元素a，隊尾指針rear指向最后一個元素g的下一位置。,3.2 隊列的順序存儲及實現(xiàn),在使用隊列前，先初始化隊列，此時，隊列為空，隊頭指針front和隊尾指針rear都指向隊列的第一個位置，即front=rear=0，如圖3.3所示。 每一個元素進(jìn)入隊列，隊尾指針rear就會增1，若元素a、b、c依次進(jìn)入空隊列，front指向第一個元素，rear指向下標(biāo)為3的存儲單元，如圖3.4所示。,3.2 隊列的順序存儲及實現(xiàn),當(dāng)一個元素出隊列時，隊頭指針front增1，隊頭元素即a出隊后，front向后移動一個位置，指向下一個位置，rear不變，如圖3.3所示。,3.2 隊列的順序存儲及實現(xiàn),3.2.2 順序隊列的“假溢出” 在對順序隊列進(jìn)行插入和刪除操作的過程中，可能會出現(xiàn)“假溢出”現(xiàn)象。經(jīng)過多次插入和刪除操作后，實際上隊列還有存儲空間，但是又無法向隊列中插入元素，我們將這種溢出稱為“假溢出”。 例如，在圖3.2所示的隊列中插入3個元素h、i、j，然后刪除2個元素a，b之后，就會出現(xiàn)如圖3.6所示的情況。當(dāng)插入元素j后，隊尾指針rear將越出數(shù)組的下界而造成“假溢出”。,3.2 隊列的順序存儲及實現(xiàn),3.2.3 順序循環(huán)隊列的表示 1順序循環(huán)隊列 為了充分利用存儲空間，消除這種“假溢出”現(xiàn)象，當(dāng)隊尾指針rear和隊頭指針front到達(dá)存儲空間的最大值（假定隊列的存儲空間為QueueSize）的時候，讓隊尾指針和隊頭指針轉(zhuǎn)化為0，這樣就可以將元素插入到隊列還沒有利用的存儲單元中。例如，在圖3.6中，插入元素j之后，rear將變?yōu)?，可以繼續(xù)將元素插入到下標(biāo)為0的存儲單元中。這樣就把順序隊列使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。,3.2 隊列的順序存儲及實現(xiàn),當(dāng)隊尾指針rear達(dá)到最大值QueueSize-1時，前提是隊列中還有存儲空間，若要插入元素，就要把隊尾指針rear變?yōu)?；當(dāng)隊頭指針front達(dá)到最大值QueueSize-1時，若要將隊頭元素出隊，要讓隊頭指針front變?yōu)?。這可通過取余操作實現(xiàn)隊列的首尾相連。例如，假設(shè)QueueSize=10，當(dāng)隊尾指針rear=9時，若要將新元素入隊，則先令rear=（rear+1）%10=0，然后將元素存入隊列的第0號單元，通過取余操作實現(xiàn)了隊列的邏輯上的首尾相連。,3.2 隊列的順序存儲及實現(xiàn),2順序循環(huán)隊列的隊空和隊滿判斷 但是，在順序循環(huán)隊列在隊空和隊滿的情況下，隊頭指針front和隊尾指針rear同時都會指向同一個位置，即front=rear，如圖3.7所示。即隊列為空時，有front=0，rear=0，因此front=rear。隊滿時也有front=0，rear=0，因此front=rear。,3.2 隊列的順序存儲及實現(xiàn),為了區(qū)分這隊空還是隊滿，通常有兩個方法：（1）增加一個標(biāo)志位。設(shè)這個標(biāo)志位為flag，初始時，有flag=0；當(dāng)入隊列成功，則flag=1；出隊列成功，有flag=0。則隊列為空的判斷條件為：front=rear&&flag=0，隊列滿的判斷條件為：front=rear&&flag=1。（2）少用一個存儲單元。隊空的判斷條件為front=rear，隊滿的判斷條件為front=(rear+1)%QueueSize。那么，入隊的操作語句為：rear=（rear+1）%QueueSize，Qrear=x。出隊的操作語句為：front=（front+1）%QueueSize。少用一個存儲單元的順序循環(huán)隊列隊滿情況如圖3.8所示。,3.2 隊列的順序存儲及實現(xiàn),順序循環(huán)隊列類型描述如下： #define QueueSize 100/*隊列的容量*/ typedef struct DataType dataQueueSize; int front,rear; /*隊頭指針和隊尾指針*/ CirQueue; 其中，data用來存儲隊列中的元素，front和rear分別表示隊頭指針和隊尾指針。,3.2 隊列的順序存儲及實現(xiàn),3.2.4 順序循環(huán)隊列的基本運算 順序循環(huán)隊列的基本運算算法實現(xiàn)如下。 （1）置空隊列。 void InitQueue(CirQueue *Q) /*順序循環(huán)隊列的初始化*/ Q ->front=Q ->rear=0; ,3.2 隊列的順序存儲及實現(xiàn),（2）判斷隊列是否為空int QueueEmpty(CirQueue *Q) return Q ->front = Q ->rear ;(3)判對滿int QueueFull(CirQueue *Q) return (Q ->rear+1)%QueueSize = Q ->front ;,3.2 隊列的順序存儲及實現(xiàn),（4）入隊 int EnQueue(CirQueue *Q , DataType x) if(QueueFull(Q) printf(“Queue overflow”); else Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; ,3.2 隊列的順序存儲及實現(xiàn),（5）取隊頭元素 DataType GetFront (CirQueue *Q) if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else return Q->dataQ->front; ,3.2 隊列的順序存儲及實現(xiàn),（6）出隊列DataType DeQueue(CirQueue *Q) DataType x; if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else x=Q->dataQ->front; /*將要刪除的元素賦值給x*/ Q->front=(Q->front+1)%QueueSize; return x; ,3.2 隊列的順序存儲及實現(xiàn),3.2.3 順序循環(huán)隊列舉例 P77,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),采用鏈?zhǔn)酱鎯Φ年犃斜环Q為鏈?zhǔn)疥犃谢蜴滉犃小?.3.1 鏈?zhǔn)疥犃械谋硎?鏈?zhǔn)疥犃?鏈?zhǔn)疥犃型ǔＳ面湵韺崿F(xiàn)。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為隊頭指針和隊尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作上的方便，我們給鏈隊列添加一個頭結(jié)點，并令隊頭指針front指向頭結(jié)點，用隊尾指針rear指向最后一個結(jié)點。,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),鏈?zhǔn)疥犃械念愋兔枋鋈缦拢?*結(jié)點類型定義*/typedef struct QNode DataType data; struct QNode * next; QueueNode;/*隊列類型定義*/typedef struct QueueNode * front; /隊頭指針 QueueNode * rear; /隊尾指針LinkQueue; /隊列類型LinkQueue Q; /定義一鏈對列Q,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),一個不帶頭結(jié)點的鏈?zhǔn)疥犃泻蛶ь^結(jié)點的鏈隊列分別如圖3.12、圖3.13所示。,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),對于帶頭結(jié)點的鏈?zhǔn)疥犃?，?dāng)隊列為空時，隊頭指針front和隊尾指針rear都指向頭結(jié)點。如圖3.14所示。 鏈?zhǔn)疥犃兄?，插入和刪除操作只需要移動隊頭指針和隊尾指針，這兩種操作的指針變化如圖3.13、圖3.16和圖3.17所示。圖3.13表示在隊列中插入元素a的情況，圖3.16表示隊列中插入了元素a，b，c之后的情況，圖3.17表示元素a出隊列的情況。,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),3.3.2 鏈?zhǔn)疥犃械幕具\算鏈?zhǔn)疥犃械幕具\算算法實現(xiàn)如下。（1）初始化隊列。void InitQueue(LinkQueue *Q) /*初始化鏈?zhǔn)疥犃?/ Q->front=(QueueNode*)malloc(sizeof(QueueNode); Q->rear =Q->front; Q ->rear->next=NULL;/*把頭結(jié)點的指針域置為null*/,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),（2）判斷隊列是否為空。int QueueEmpty(LinkQueue *Q) return Q->rear=Q->front; /頭尾指針相等隊列為空,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),（3）將元素x入隊。先為新結(jié)點申請一個空間，然后將x賦給數(shù)據(jù)域，并使原隊尾元素結(jié)點的指針域指向新結(jié)點，隊尾指針指向新結(jié)點，從而將結(jié)點加入隊列中。操作過程如圖3.20所示。,將元素x入隊的算法實現(xiàn)如下。void EnQueue(LinkQueue *Q, DataType x)/*將元素x插入到鏈?zhǔn)疥犃形膊?/ QueueNode *p=(QueueNode*)malloc(sizeof(QueueNode); p->data=x; /將元素值賦值給結(jié)點的數(shù)據(jù)域 p->next=NULL; /將結(jié)點的指針域置為空 Q->rear->next=p;/將原來隊列的隊尾指針指向p Q->rear=p;/將隊尾指針指向p,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),（4）取隊頭元素。DataType GetFront (LinkQueue *Q) if(QueueEmpty(Q) printf(“Queue underflow”); exit(0); else return Q->front->next-data;,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),（5）出隊列。DataType DeQueue(LinkQueue *Q) QueueNode *p; if(QueueEmpty(Q) /判斷鏈?zhǔn)疥犃惺欠駷榭?return 0; else p=Q->front;/使指針p指向頭結(jié)點 Q->front=Q->front->next; /頭指針指向原隊列頭結(jié)點 free(p); /釋放原頭結(jié)點 return(Q->front->data); /返回原對頭結(jié)點的數(shù)據(jù) ,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),2鏈?zhǔn)窖h(huán)隊列 將鏈?zhǔn)疥犃械氖孜蚕噙B就構(gòu)成了鏈?zhǔn)窖h(huán)隊列。在鏈?zhǔn)窖h(huán)隊列中，可以只設(shè)置隊尾指針，如圖3.18所示。當(dāng)隊列為空時，如圖3.19所示，隊列LQ為空的判斷條件為LQ.rear->next=LQ.rear。,3.3.3 鏈?zhǔn)疥犃信e例 【例3_7】P81,3.3 隊列的鏈?zhǔn)酱鎯皩崿F(xiàn),入隊列圖,出隊列圖,隊列是只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。 隊列有兩種存儲方式：順序存儲和鏈?zhǔn)酱鎯?。采用順序存儲結(jié)構(gòu)的 隊列稱為順序隊列，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的隊列稱為鏈?zhǔn)疥犃小?順序隊列存在“假溢出”的問題，順序隊列的“假溢出”不是因為存儲空間不足而產(chǎn)生的，為了避免“假溢出”，可用循環(huán)隊列表示順序隊列。 為了區(qū)分循環(huán)隊列的隊空還是隊滿，有3種方案：設(shè)置一個標(biāo)志位，少用一個存儲單元，設(shè)置一個計數(shù)器。 循環(huán)隊列P75，例題P80,3.4 小結(jié),1棧 1>棧的定義： 棧是限定僅在表的一端進(jìn)行插入和刪除操作的線性表。 我們把插入和刪除的一端稱為棧頂（TOP），另一端稱為棧底（BOTTOM）,不包含任何元素的棧稱為空棧。棧又稱為后進(jìn)先出（Last in first out）的線性表，簡稱LIFO結(jié)構(gòu)。 2>棧的存儲結(jié)構(gòu) 由于棧也是線性表，因此線性表的存儲結(jié)構(gòu)對棧也使用，通常有順序棧和鏈棧兩種存儲結(jié)構(gòu)，這兩種存儲結(jié)構(gòu)的不同，即使得實現(xiàn)棧的基本運算的算法也有所不同。 （1）順序存儲結(jié)構(gòu) 其實棧的順序存儲還是挺方便的，因為他只準(zhǔn)棧頂進(jìn)出元素，所以不存在線性表插入和刪除時需要移動元素的問題。不過它有一個很大,3.4 小結(jié),的缺陷，就是必須事先確定數(shù)組存儲空間大小，不夠用了，就需要編程手段來擴展數(shù)組的容量，非常麻煩， （2）鏈?zhǔn)酱鎯Y(jié)構(gòu) 如果棧的使用過程中元素變化不可預(yù)測，有時很小，有時非常大，那么最好是用鏈?！敬鎯臻g不固定可伸縮】。2 隊列 1>隊列的定義 隊列(queue)是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。 隊列是一種先進(jìn)先出(first in first out)的線性表，簡稱FIFO。允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊頭(Front)。 隊列是一種運算受限的線性表，它的運算限制與棧不同，是兩頭都有,3.4 小結(jié),限制，插入只能在表的一端進(jìn)行(只進(jìn)不出)，而刪除只能在表的另一端進(jìn)行(只出不進(jìn))。 2>隊列的存儲結(jié)構(gòu) 隊列也是線性表，所以有兩種存儲方式，順序存儲和鏈?zhǔn)酱鎯Α?（1）順序存儲結(jié)構(gòu)（順序隊列） 缺點，存儲空間不夠用的時候需要開發(fā)人員通過編程手段來擴展數(shù)組容量。 衍生循環(huán)隊列：頭尾相接的順序存儲結(jié)構(gòu)成為循環(huán)隊列。 （2）鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈隊） 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其實也就是線性表的單鏈表，只不過它只能尾進(jìn)頭出而已，我們把它簡稱為鏈隊列。,3.4 小結(jié),總結(jié)： 棧（stack）是限定在表的一端進(jìn)行插入和刪除操作的線性表。 隊列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。它們均可使用線性表的順序存儲結(jié)構(gòu)來實現(xiàn)，但都存在著順序存儲的一些弊端（空間不夠用）。因此它們各自有各級的技巧來解決這個問題， 對于棧來說，如果是兩個相同數(shù)據(jù)類型的棧，則可以用數(shù)組的兩端作為棧底的方法來讓兩個棧共享數(shù)據(jù)，這就可以最大化地利用數(shù)組的空間。 對于隊列來說，為了避免數(shù)組插入和刪除時需要移動數(shù)據(jù)，于是就引入了循環(huán)隊列，使得隊頭和隊尾可以在數(shù)組中循環(huán)變化。解決了移動數(shù)據(jù)的時間損耗。 他們也都可以通過鏈?zhǔn)酱鎯Y(jié)構(gòu)來實現(xiàn)，實現(xiàn)原則上與線性表基本相同。,3.4 小結(jié),例如，一個算術(shù)表達(dá)式為 9 - (2+4*7)/5+3# 這種算術(shù)表達(dá)式中的運算符總是出現(xiàn)在兩個操作數(shù)之間，這種算術(shù)表達(dá)式被稱為中綴表達(dá)式。計算機編譯系統(tǒng)在計算一個算術(shù)表達(dá)式之前，要將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后對后綴表達(dá)式進(jìn)行計算。后綴表達(dá)式就是算術(shù)運算符出現(xiàn)在操作數(shù)之后，并且不含括號。 計算機在求算術(shù)表達(dá)式的值時分為兩個步驟： （1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式； （2）依據(jù)后綴表達(dá)式計算表達(dá)式的值。,3.5 棧和隊列的典型應(yīng)用,1將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 要將一個算術(shù)表達(dá)式的中綴形式轉(zhuǎn)化為相應(yīng)的后綴形式，首先了解下算術(shù)四則運算的規(guī)則。算術(shù)四則運算的規(guī)則是： （1）先乘除，后加減； （3）同級別的運算從左到右進(jìn)行計算； （2）先括號內(nèi)，后括號外。 上面的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式為： 9247 *+5/-3 +,3.5 棧和隊列的典型應(yīng)用,轉(zhuǎn)換后的后綴表達(dá)式具有以下兩個特點： （1）后綴表達(dá)式與中綴表達(dá)式的操作數(shù)出現(xiàn)順序相同，只是運算符先后順序改變了； （2）后綴表達(dá)式不出現(xiàn)括號。 正因為后綴表達(dá)式的以上特點，所以編譯系統(tǒng)不必考慮運算符的優(yōu)先關(guān)系。僅需要從左到右依次掃描后綴表達(dá)式的各個字符，遇到運算符時，直接對運算符前面的兩個操作數(shù)進(jìn)行運算即可。,3.5 棧和隊列的典型應(yīng)用,如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式呢？ 我們約定#作為后綴表達(dá)式的結(jié)束標(biāo)志。則中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法描述如下： （1）初始化棧，并將#入棧； （2）當(dāng)讀到數(shù)字時，直接將其入隊列 ，并讀入下一字符； （3）當(dāng)讀到運算符時，將棧中所有優(yōu)先級高于或等于該運算符的運算符彈出，并入隊列，再將當(dāng)前運算符入棧； （4）當(dāng)讀入左括號時，即入棧； （5）當(dāng)讀入右括號時，將靠近棧頂?shù)牡谝粋€左括號上面的運算符全部依次彈出， 送至隊列中，在刪除棧中的左括號。,3.5 棧和隊列的典型應(yīng)用,運算符的優(yōu)先關(guān)系如表3.1所示。 表3.1 運算符的優(yōu)先關(guān)系,3.5 棧和隊列的典型應(yīng)用,初始化一個空棧，用來對運算符進(jìn)行出棧和入棧操作。中綴表達(dá)式9 - (2+4*7)/5+3#轉(zhuǎn)換為后綴表達(dá)式的具體過程如圖P84所示（為了便于描述，在要轉(zhuǎn)換表達(dá)式的末尾加一個#作為結(jié)束標(biāo)記）。,3.5 棧和隊列的典型應(yīng)用,2求后綴表達(dá)式的值 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式后，就可以計算利用后綴表達(dá)式的值了。計算后綴表達(dá)式的值的規(guī)則如下：依次讀入后綴表達(dá)式中的每個字符，如果是操作數(shù)，則將操作數(shù)進(jìn)入棧；如果是運算符，則將處于棧頂?shù)膬蓚€操作數(shù)出棧，然后利用當(dāng)前運算符進(jìn)行運算，將運行結(jié)果入棧，直到整個表達(dá)式處理完畢。 利用上述規(guī)則，后綴表達(dá)式的9247 *+5/-3 +的值的運算過程如圖P85所示。,3.5 棧和隊列的典型應(yīng)用,