數(shù)據(jù)結(jié)構(gòu) 課件 第4章 隊列

第4章隊列4.1隊列的應(yīng)用實例及概念4.2隊列的存儲方式4.2.1隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)4.2.2隊列的順序存儲結(jié)構(gòu)4.3隊列的有關(guān)操作4.3.1循環(huán)隊列的操作實現(xiàn)4.3.2鏈隊列的操作實現(xiàn)4.4隊列的ADT定義4.5順序循環(huán)隊列的應(yīng)用4.6上機(jī)實驗本章小結(jié)習(xí)題1第4章隊列總體要求：熟悉隊列的定義熟悉隊列的抽象數(shù)據(jù)類型描述中各種操作的含義熟練掌握順序存儲隊列的建立、入隊列、出隊列算法熟練掌握鏈?zhǔn)酱鎯﹃犃械慕ⅰ⑷腙犃?、出隊列算?/p>

核心技能點：隊列應(yīng)用于實際問題的能力

擴(kuò)展技能點：C語言環(huán)境下隊列各種算法的實現(xiàn)

2第4章隊列相關(guān)知識點：C語言數(shù)組的知識C語言結(jié)構(gòu)體的知識C語言指針的知識C語言函數(shù)的知識學(xué)習(xí)重點：熟悉隊列的定義

熟悉隊列的抽象數(shù)據(jù)類型描述中各種操作的含義

掌握隊列各種存儲結(jié)構(gòu)下算法的實現(xiàn)

3第4章隊列4.1隊列的應(yīng)用實例及概念

數(shù)據(jù)結(jié)構(gòu)中所定義的隊列與日常生活中的排隊相當(dāng)類似。在日常生活中，有許多是“先來先服務(wù)”的例子。例如，在銀行排隊等待取款的事件，或者在公共汽車站排隊等車事件等等。在這些排隊事件中，新來的成員總是加入在隊尾，而每次離開的成員總是隊列頭上的成員，即入隊在隊尾進(jìn)行，而出隊在隊頭進(jìn)行。

隊列是限定只能在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表。在表中允許插入的一端叫做隊尾(Rear)，允許刪除的一端叫做隊頭(Front)，向隊尾插入一個元素的操作叫做入隊操作，從隊頭取出一個元素的操作叫做出隊操作。隨著入隊、出隊操作的執(zhí)行，隊列的隊頭、隊尾也不斷地隨之改變。由于隊列的操作具有“先進(jìn)先出”的特點，因此隊列又稱作先進(jìn)先出表(FIFO，即FirstInFirstOut)。4第4章隊列

在圖4．1所表示的隊列中，a0是隊頭元素，an-1是隊尾元素。隊列中的元素以a0，a1，…，an-1的順序進(jìn)隊列。如果對這個隊列執(zhí)行入隊操作，入隊元素為an，則該隊列的隊尾元素就變?yōu)閍n；如果對這個隊列執(zhí)行出隊操作，則隊列的隊頭元素a0從隊列中取出，當(dāng)前的隊頭元素就變?yōu)閍1。5圖4.1隊列結(jié)構(gòu)示意圖

一般，一個隊列是由n個元素組成的有限序列，可記作：Q=(a0，a1，…ai，…，an-1)

其中，每個ai都是隊列Q的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類型，但必須屬于同一種數(shù)據(jù)對象。第4章隊列6

綜上所述，隊列是一種數(shù)據(jù)類型，其數(shù)據(jù)元素之間呈線性關(guān)系，其操作的特點是“先進(jìn)先出”，主要操作有入隊、出隊和取隊頭元素等。

隊列在程序設(shè)計中也經(jīng)常使用。一個最典型的例子就是操作系統(tǒng)中的作業(yè)排隊。在允許多道程序運(yùn)行的計算機(jī)系統(tǒng)中，作業(yè)輸入后通常處于后備狀態(tài)，由操作系統(tǒng)中的作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)入執(zhí)行。作業(yè)調(diào)度程序可以采用不同的調(diào)度策略，其中最簡單的調(diào)度策略就是“先來先服務(wù)”，也就是要使用一個隊列來實現(xiàn)這種調(diào)度策略。同樣在做輸出時也要按請求輸出的先后次序排隊。作業(yè)輸出統(tǒng)一由操作系統(tǒng)中的輸出程序來執(zhí)行，每當(dāng)輸出程序傳輸完畢可以接收新的輸出任務(wù)時，隊頭的輸出作業(yè)從隊列中退出做輸出操作。凡是請求輸出的作業(yè)都是從隊尾進(jìn)入隊列的。

我們先要考慮隊列的存儲方式，然后考慮有關(guān)的操作如何實現(xiàn)，在以下幾節(jié)中我們將圍繞這些問題展開討論。

第4章隊列74.2隊列的存儲方式

與線性表類似，隊列也有順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種存儲方式。按順序存儲結(jié)構(gòu)建立起來的隊列稱為順序隊列，按鏈?zhǔn)酱鎯Y(jié)構(gòu)建立起來的隊列稱為鏈隊列。4.2.1隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

我們已經(jīng)知道，對于使用中數(shù)據(jù)元素的個數(shù)難以事先估計，而又進(jìn)出變動較大的數(shù)據(jù)結(jié)構(gòu)，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)比采用順序存儲結(jié)構(gòu)更為有利。顯然，隊列也可以采用這種存儲方式。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的隊列簡稱為鏈隊列，如圖4.2所示。圖4.2鏈隊列示意圖

第4章隊列8

對于一個鏈隊列，顯然需要設(shè)置兩個指針，分別指向該隊列的隊頭和隊尾(分別稱為頭指針和尾指針)，一般為了操作方便起見，我們也給鏈隊列增加一個頭結(jié)點，并令頭指針指向頭結(jié)點。由此，空的鏈隊列的判別條件為頭指針和尾指針均指向頭結(jié)點，如圖4.3(a)所示。鏈隊列的操作即為單鏈表的插入和刪除的特殊情形，入隊操作相當(dāng)于從鏈尾插入一個元素，出隊操作相當(dāng)于從鏈頭刪除一個元素。入隊出隊操作均可通過修改尾指針或頭指針來實現(xiàn)，圖4.3(b)～(d)展示了這兩種操作進(jìn)行時的指針變化情況。第4章隊列9

圖4.3鏈隊列指針變化狀況(a)空隊列；(b)a1入隊列；(c)a2入隊列；(d)a1出隊列第4章隊列

10

如前所述，鏈隊列可以由頭指針與尾指針唯一地確定，因此在定義鏈隊列的類型時，應(yīng)該包括一個頭指針與一個尾指針。為了表示鏈隊列的存儲結(jié)構(gòu)，我們先要定義存放隊列中數(shù)據(jù)元素的結(jié)點類型及其指向這種結(jié)點的指針類型，然后再定義由一個頭指針與一個尾指針組成的結(jié)構(gòu)類型來表示一個鏈隊列。如圖4.4所示，假設(shè)結(jié)點類型名為LQNode，結(jié)點類型中數(shù)據(jù)域名為data，指針域名為next，數(shù)據(jù)元素的類型為DataType，鏈隊列的頭指針和尾指針分別為front與rear。第4章隊列

11

鏈隊列類型LQueue可定義如下：typedefstructqnode{DataTypedata;structqnode*next;}LQNode;

typedefstruct{LQNode*front;/*隊頭指針*/LQNode*rear;/*隊尾指針*/}LQueue;圖4．4鏈隊列類型結(jié)構(gòu)第4章隊列

12

在程序中使用的鏈隊列可以用一個LQueue型變量來表示，例如：

LQueueql；當(dāng)ql.front=ql.rear時，這個隊列就成為空隊列，否則，ql.front->next指向隊頭結(jié)點，而ql.rear指向隊尾結(jié)點。和鏈棧的情形相同，一般不會出現(xiàn)隊列滿的情形，除非整個可用空間都被占滿，malloc()都無法執(zhí)行的情形下才會發(fā)生上溢。同樣空隊列的狀態(tài)在程序設(shè)計中也被用作實現(xiàn)控制轉(zhuǎn)移的條件。第4章隊列13

4.2.2隊列的順序存儲結(jié)構(gòu)

隊列的順序存儲結(jié)構(gòu)是指使用一組地址連續(xù)的存儲單元來依次存放隊列中的數(shù)據(jù)元素，除了用一個能容納最多元素個數(shù)的向量以外，還需要兩個指針分別指向隊頭元素和隊尾元素。在C語言中，通常可使用一個一維數(shù)組queue[MaxQueueSize]來存儲隊列中的數(shù)據(jù)元素，兩個整型指示器front與rear分別表示隊頭元素前一個和隊尾元素的位置。類型定義如下：

MaxQueueSize=隊列中允許存放元素個數(shù)的最大值；

typedefstruct

{

DataTypequeue[MaxQueueSize];

intrear;/*隊尾指針*/

intfront;/*隊頭指針*/

}SeqQueue;第4章隊列14

順序隊列的存儲結(jié)構(gòu)形式如圖4.5所示：

front指針指向剛出隊的那個元素的位置，而rear指針指向隊尾元素的位置，因為在執(zhí)行入隊、出隊操作時，先修改指針，再取出或送入元素。圖4.5順序隊列的存儲結(jié)構(gòu)第4章隊列15

圖4．6(a)～(d)展示了對這種順序隊列在執(zhí)行入隊、出隊操作時，頭尾指針變化情況。

圖4.6順序隊列中頭尾指針的變化(a)空隊列；(b)A、B、C、D依次入隊；(c)A、B依次出隊；(d)E、F入隊，C出隊

第4章隊列16

從圖4.6可以看出，對一般的順序隊列Q，我們可以用Q.front==Q.rear作為判別隊列是否為空的條件；用Q.rear≥MaxQueueSize-1作為判別隊列是否為滿的條件。當(dāng)隊列非空時，可執(zhí)行如下的出隊操作：Q.front=Q.front+l；data=Q.queue[front]；當(dāng)隊列非滿時，可執(zhí)行如下的入隊操作：Q.rear=Q.rear+1；Q.queue[Q.rear]=data；

在這里值得考慮的是：當(dāng)Q.rear≥MaxQueueSize-1時，隊列是否真正為滿?假設(shè)當(dāng)前隊列是處在圖4.6(d)的狀態(tài)，即MaxQueueSize-1=5，Q.rear=5，Q.front=2，顯然此時不能再做入隊列的操作，因為Q.rear≥MaxQueueSize-1，但隊列中實際上并未存滿元素，這種現(xiàn)象稱為假溢出。當(dāng)然，在發(fā)生假溢出時可以將全部元素向下移動直至頭指針為-1，但這樣處理效率不高。一個比較巧妙的辦法是將隊列設(shè)想成首尾相接的環(huán)，一端放滿時再從另一端存入，只要尾指針不與頭指針相遇，該隊列即可使用下去。這就是我們所講的循環(huán)隊列。第4章隊列17

圖4.7是一個循環(huán)隊列的示意圖。在這個示圖中，循環(huán)隊列的長度MaxQueueSize=8，隊列中元素的序號在0～7之間變化，7號元素的后面又是0號元素。隊列中的元素按順時針的方向進(jìn)入隊列，Q.front指針指向剛出隊的那個元素的位置，即序號為l，當(dāng)前的隊頭元素在2號位，而Q.rear指針正好指向隊尾元素的位置，當(dāng)前的隊尾元素在4號位。

圖4.7循環(huán)隊列示意圖第4章隊列18

對于循環(huán)隊列，當(dāng)頭指針和尾指針相等時，隊列為空隊列，但當(dāng)隊列的元素都存滿時，尾指針也正好與頭指針相等。為了能區(qū)分這兩種不同的狀態(tài)，規(guī)定循環(huán)隊列少用一個元素空間，以尾指針加1等于頭指針為隊列滿的判別條件。圖4．8表示了循環(huán)隊列的各種狀態(tài)與頭尾指針的關(guān)系。

圖4.8循環(huán)隊列的頭尾指針(a)空隊列；(b)隊列中有一個元素；(c)隊列滿

第4章隊列19

另外對于循環(huán)隊列，無論是頭指針還是尾指針，在對其進(jìn)行加l處理時，都要考慮對結(jié)果取模。綜上所述：我們可以用Q.front==Q.rear作為判別隊列是否為空的條件；用(Q.rear+1)%MaxQueueSize=Q.front作為判別隊列是否為滿的條件。當(dāng)隊列非空時，可執(zhí)行如下的出隊操作：Q.front=(Q.front+1)%MaxQueueSize；data=Q.queue[Q.front]；當(dāng)隊列非滿時，可執(zhí)行如下的入隊操作：Q.rear=(Q.rear+1)%MaxQueueSize；Q.queue[Q.rear]=data；第4章隊列20

在隊列的順序存儲結(jié)構(gòu)中，應(yīng)該包括一個存儲數(shù)據(jù)元素的一維數(shù)組，取其名為queue，其長度可取為一個適當(dāng)?shù)淖畲笾礛axQueueSize，另外還應(yīng)包括兩個位置指示器front和rear，它們分別指向隊頭和隊尾的位置。使用C語言，我們可以定義以下的結(jié)構(gòu)類型來表示順序隊列或循環(huán)隊列，設(shè)其類型名用SeqCQueue表示：MaxQueueSize=隊列中允許存放元素個數(shù)的最大值；typedefstruct{DataTypequeue[MaxQueueSize];intrear;/*隊尾指針*/intfront;/*隊頭指針*/}SeqCQueue;第4章隊列21

4.3隊列的有關(guān)操作

在存儲結(jié)構(gòu)確定以后，我們要考慮隊列操作的實現(xiàn)。下面分別按隊列的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種方式來介紹有關(guān)算法的實現(xiàn)過程。4.3.1循環(huán)隊列的操作實現(xiàn)

前面我們已經(jīng)介紹了循環(huán)隊列的類型定義SeqCQueue，在這種類型中包括了一個存儲數(shù)據(jù)元素的一維數(shù)組queue[MaxQueueSize]以及頭指針front和尾指針rear。下面就討論在這種存儲方式下，隊列的有關(guān)操作的實現(xiàn)。第4章隊列22

1.入隊操作

循環(huán)隊列的入隊操作可表示為：

intQueueAppend(SeqCQueue*Q,DataTypex)；

其中，參數(shù)Q表示指定的循環(huán)隊列，其類型為SeqCQueue；參數(shù)x表示入隊列的元素，其類型為元素類型DataType。該操作返回一個函數(shù)值，表示入隊操作是否執(zhí)行成功。

操作的功能為：在循環(huán)隊列Q中插入元素x。若循環(huán)隊列Q不滿，則插入x新的隊尾元素，并返回函數(shù)值1，否則隊列的狀態(tài)不變且返回函數(shù)值0。

處理過程為：判是否隊列滿,若隊列滿，則返回0，否則，隊列尾指針加1，將x從隊尾插入隊列并返回1。第4章隊列23程序如下：intQueueAppend(SeqCQueue*Q,DataTypex)/*把數(shù)據(jù)元素值x插入順序循環(huán)隊列Q的隊尾，成功返回1，失敗返回0*/{if((Q->rear+1)%MaxQueueSize==Q->front){printf("隊列已滿無法插入!\n");return0;}else{Q->rear=(Q->rear+1)%MaxQueueSize;Q->queue[Q->rear]=x;return1;}}第4章隊列24

2.出隊操作

循環(huán)隊列的出隊操作可表示為intQueueDelete(SeqCQueue*Q,DataType*d)；其中，參數(shù)Q表示指定的循環(huán)隊列，其類型為SeqCQueue。該操作是一個函數(shù)，刪除順序循環(huán)隊列Q的隊頭元素，成功返回1，失敗返回0。操作的功能為：若循環(huán)隊列Q非空，則從Q中取出隊頭元素并賦給d，返回1，否則返回0。處理過程為:判隊列是否為空隊列。若隊列為空隊列，則返回0，否則，隊列頭指針加1并返回隊頭元素。第4章隊列25程序如下：intQueueDelete(SeqCQueue*Q,DataType*d)/*刪除順序循環(huán)隊列Q的隊頭元素并賦給d，成功返回1，失敗返回0*/{if(Q->front==Q->rear){printf("循環(huán)隊列已空無數(shù)據(jù)元素出隊列!\n");return0;}else{Q->front=(Q->front+1)%MaxQueueSize;*d=Q->queue[Q->front];return1;}}第4章隊列26

3.其他操作⑴初始化操作：設(shè)置循環(huán)隊列Q為空的循環(huán)隊列。voidQueueInitiate(SeqCQueue*Q)/*初始化順序循環(huán)隊列Q*/{Q->rear=0;/*定義初始隊尾指針下標(biāo)值*/ Q->front=0;/*定義初始隊頭指針下標(biāo)值*/ }⑵求長度操作：返回循環(huán)隊列Q中所含元素的個數(shù)。intQueueSize(SeqCQueue*Q){return(Q->rear-Q->front+MaxQueueSize)%MaxQueueSize;}⑶判空隊列操作：若隊列為非空，則返回1，否則返回0。

intQueueNotEmpty(SeqCQueueQ)/*判順序循環(huán)隊列Q非空否，非空則返回1，否則返回0*/{if(Q.front==Q.rear)return0;elsereturn1;}第4章隊列27

⑷取隊頭操作：若隊列非空，則返回隊頭元素，否則返回NULL。intQueueGet(SeqCQueueQ,DataType*d)/*取順序循環(huán)隊列Q的當(dāng)前隊頭元素并賦給d，成功返回1，失敗返回0*/{if(Q.front==Q.rear){printf("循環(huán)隊列已空無數(shù)據(jù)元素可取!\n");return0;}else{*d=Q.queue[(Q->front+1)%MaxQueueSize;];return1;}}第4章隊列28

4.3.2鏈隊列的操作實現(xiàn)前面我們已經(jīng)介紹了鏈隊列的類型定義LQueue，在這種類型中包括了一個指向鏈隊列的頭指針LQueue*front和一個尾指針LQueue*rear。下面就討論在這種存儲方式下，隊列的有關(guān)操作的實現(xiàn)。1.入隊列操作

鏈隊列的入隊操作可表示為:intQueueAppend(LQueue*Q,DataTypex)；其中，參數(shù)Q表示指定的鏈隊列，其類型為LQueue,參數(shù)x表示入隊列的元素，其類型為元素類型DataType。操作的功能為：在鏈隊列Q中插入新的隊尾元素x。處理過程為：

(1)生成一個元素值為x的新結(jié)點：

(2)將該結(jié)點從隊尾插入隊列。

第4章隊列29

程序如下：intQueueAppend(LQueue*Q,DataTypex)/*把數(shù)據(jù)元素值x插入鏈?zhǔn)疥犃蠶的隊尾，入隊列成功則返回1，否則返回0*/{LQNode*p;if((p=(LQNode*)malloc(sizeof(LQNode)))==NULL){printf("內(nèi)存空間不足！");return0;}p->data=x;p->next=NULL;Q->rear->next=p;Q->rear=p;return1;}圖4.9鏈隊列入隊操作示意圖第4章隊列30

2.出隊列操作鏈隊列的出隊操作可表示為

intQueueDelete(LQueue*Q,DataType*d)；其中，參數(shù)Q表示指定的鏈隊列，其類型為LQueue。該操作是一個函數(shù)，刪除鏈?zhǔn)疥犃蠶的隊頭數(shù)據(jù)元素值到d。操作的功能為：若鏈隊列Q非空，則刪除鏈?zhǔn)疥犃蠶的隊頭數(shù)據(jù)元素值到d并返回1，否則0。處理過程為(如圖4.10)：若鏈隊列Q為空，則返回0，否則：

(1)刪除隊頭元素，即使頭結(jié)點中的指針指向隊頭的下一個結(jié)點。

(2)若刪除后成為空隊列，則使頭尾指針值相同。

(3)取刪除結(jié)點的值由d帶回，并釋放該結(jié)點。第4章隊列31

圖4.10鏈隊列出隊操作示意圖

(a)一般情況；(b)出隊操作后成為空隊列第4章隊列32

程序如下：intQueueDelete(LQueue*Q,DataType*d)/*刪除鏈?zhǔn)疥犃蠶的隊頭數(shù)據(jù)元素值到d，出隊列成功則返回1，否則返回0*/{LQNode*p;if(Q->front==Q->rear){printf("隊列已空無數(shù)據(jù)元素出隊列!\n");return0;}else{*d=Q->front->next->data;p=Q->front->next;Q->front->next=Q->front->next->next;if(Q->front->next==NULL)Q->rear=Q->front;free(p);return1;}}第4章隊列33

3.其他操作⑴初始化操作：設(shè)置一個空的鏈隊列，由Q表示之。處理過程：生成一個頭結(jié)點，并使Q的頭尾指針均指向它。intQueueInitiate(LQueue*Q) /*初始化鏈?zhǔn)疥犃蠶*/{LQNode*p;if((p=(LQNode*)malloc(sizeof(LQNode)))==NULL){printf("內(nèi)存空間不足！");return0;}Q->rear=Q->front=p;/*定義初始隊頭尾指針下標(biāo)值*/ return1; }第4章隊列34

⑵求長度操作：返回鏈隊列Q中所含元素的個數(shù)。intQueueSize(LQueueQ){LQueue*p;inti;P=Q.front->next;i=0;while(p!=NULL){i=i+1;p=p->next;}returni;}⑶判空隊列操作：若隊列為非空，則返回1，否則返回0。intQueueNotEmpty(LQueueQ)/*判鏈?zhǔn)疥犃蠶非空否，非空則返回1，否則返回0*/{if(Q.front==Q.rear)return0;elsereturn1;}第4章隊列35

⑷取隊頭操作：若隊列非空，取鏈?zhǔn)疥犃蠶的當(dāng)前隊頭數(shù)據(jù)元素值到d，成功則返回1，否則返回0。

intQueueGet(LQueueQ,DataType*d)/*取鏈?zhǔn)疥犃蠶的當(dāng)前隊頭數(shù)據(jù)元素值到d，成功則返回1，否則返回0*/{if(Q.front==Q.rear){printf("隊列已空無數(shù)據(jù)元素出隊列!\n");return0;}else{*d=Q.front->next->data;return1;}}第4章隊列36

⑸銷毀操作：釋放所有的空間。voidDestroy(LQueueQ){LQNode*p,*p1;p=Q.front;while(p!=NULL){p1=p;p=p->next;free(p1);}}第4章隊列37

4.4隊列的ADT定義以上我們討論了隊列的結(jié)構(gòu)特征、存儲方式及其相關(guān)操作的實現(xiàn)，在本節(jié)中我們將給出隊列的ADT定義即抽象數(shù)據(jù)類型定義。與線性表、棧的情形類似，我們可以定義隊列的抽象數(shù)據(jù)類型。一種數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。以下是隊列的ADT定義：元素：可以是各種類型的數(shù)據(jù)，但必須同屬于一個數(shù)據(jù)對象；結(jié)構(gòu)：隊列中的n個元素呈線性關(guān)系；第4章隊列38

操作：對隊列可執(zhí)行以下的基本操作：⑴intQueueInitiate(Q) ：初始化操作。設(shè)定一個空的隊列Q。⑵intQueueSize(Q)：求長度函數(shù)。函數(shù)值為給定隊列Q中數(shù)據(jù)元素的個數(shù)。⑶intQueueNotEmpty(Q)：判空隊列函數(shù)。若隊列為非空，則返回1，否則返回0。⑷Queueclear(Q)：隊列清空操作。操作的結(jié)果使Q成為空隊列。⑸QueueAppend(Q,x)：入隊列操作。在隊列Q的尾部插入元素x。若隊列Q不滿，則元素x成為插入前隊尾元素的后繼，即x為新的隊尾元素。⑹intQueueDelete(Q,d)

出隊列函數(shù)。若隊列Q非空，刪除鏈?zhǔn)疥犃蠶的隊頭數(shù)據(jù)元素值到d，出隊列成功則返回1，且其后繼為新的隊頭元素，否則返回0。⑺intQueueGet(Q,d)：取隊頭元素函數(shù)。若隊列Q非空，則返回1，否則返回0。由于在具體的應(yīng)用中，對隊列所進(jìn)行的操作不一定相同，因此隊列的函數(shù)定義就會有所不同。而且由于數(shù)據(jù)存儲方式的不同，函數(shù)定義的實現(xiàn)方法也就不同。第4章隊列39

4.5順序循環(huán)隊列的應(yīng)用由于順序循環(huán)隊列和順序隊列結(jié)構(gòu)近似，但順序循環(huán)隊列的功能大大優(yōu)于順序隊列的功能，所以順序隊列幾乎不被采用。順序循環(huán)隊列的應(yīng)用很廣泛。例如，操作系統(tǒng)中的各種數(shù)據(jù)緩沖區(qū)的先進(jìn)先出管理，應(yīng)用系統(tǒng)中的各種事件排隊管理，等等。這里我們討論一個用順序循環(huán)隊列和順序堆棧實現(xiàn)判斷一個字符序列是否是回文的例子。例4.1編程序判斷一個字符序列是否是回文(回文是指一個字符序列以中間字符為基準(zhǔn)兩邊字符完全相同)。程序從鍵盤輸入一個字符序列存入字符串str中，字符串長度小于等于80，輸入字符序列以回車換行符為結(jié)束標(biāo)記，字符串str中不包括回車換行符。把字符串中字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的元素和退棧的元素是否相等，若全部相等則該字符序列是回文，否則就不是回文。第4章隊列40

程序如下：#defineMaxStackSize100typedefcharDataType;/*定義具體應(yīng)用的數(shù)據(jù)類型DataType*/#include"SeqCQueue.h"#include"SeqStack.h"voidHuiWen(charstr[]){SeqCQueuemyQueue;SeqStackmyStack;charx,y;inti,length;length=strlen(str);QueueInitiate(&myQueue);StackInitiate(&myStack);for(i=0;i<length;i++){QueueAppend(&myQueue,str[i]);StackPush(&myStack,str[i]);}第4章隊列41

while(QueueNotEmpty(myQueue)==1&&StackNotEmpty(myStack)==1){if(QueueDelete(&myQueue,&x)==1&&StackPop(&myStack,&y)==1&&x!=y){printf("%s不是回文!\n",str);return;}}if(QueueNotEmpty(myQueue)||StackNotEmpty(myStack))printf("%s不是回文!\n",str);elseprintf("%s是回文!\n",str);}voidmain(void){charstr1[]="ABCDEDCBA";charstr2[]="ABCDEDCAB";HuiWen(str1);HuiWen(str2);}第4章隊列42

4.6上機(jī)實驗

實驗?zāi)康模?/p>

通過上機(jī)實驗，熟悉隊列的各種存儲結(jié)構(gòu)，鍛煉學(xué)生應(yīng)用隊列的知識解決實際問題的能力實驗要求：

1.完成自己的隊列頭文件

2.完成后附范例的上機(jī)驗證

3.模仿實例，完成其它算法

4.完成實驗報告第4章隊列43

實驗步驟:1.逐步完成自己的順序存儲的循環(huán)隊列頭文件（1）編寫頭文件（2）編寫驗證主函數(shù)（3）上機(jī)調(diào)試程序，上機(jī)驗證2.逐步完成自己的鏈?zhǔn)酱鎯Φ年犃蓄^文件（1）編寫頭文件（2）編寫驗證主函數(shù)（3）上機(jī)調(diào)試程序，上機(jī)驗證3.完成應(yīng)用實例程序4.撰寫實驗報告第4章隊列44

范例鏈?zhǔn)疥犃蓄^文件內(nèi)容#include<stdio.h>#include<stdlib.h>typedefcharDataType;

typedefstructqnode{DataTypedata;structqnode*next;}LQNode;typedefstruct{LQNode*front; /*隊頭指針*/LQNode*rear; /*隊尾指針*/}LQueue;

第4章隊列45

voidQueueInitiate(LQueue*Q) *初始化鏈?zhǔn)疥犃蠶*/{Q->rear=NULL; /*定義初始隊尾指針下標(biāo)值*/Q->front=NULL; /*定義初始隊頭指針下標(biāo)值*/}

intQueueNotEmpty(LQueueQ)/*判鏈?zhǔn)疥犃蠶非空否，非空則返回1，否則返回0*/{if(Q.front==NULL)return0;elsereturn1;}

第4章隊列46

intQueueAppend(LQueue*Q,DataTypex)/*把數(shù)據(jù)元素值x插入鏈?zhǔn)疥犃蠶的隊尾，入隊列成功則返回1，否則返回0*/{LQNode*p;if((p=(LQNode*)malloc(sizeof(LQNode)))==NULL){printf("內(nèi)存空間不足！");return0;}p->data=x;p->next=NULL;if(Q->rear!=NULL)Q->rear->next=p;Q->rear=p;if(Q->front==NULL)Q->front=p;return1;}

第4章隊列47

intQueueDelete(LQueue*Q,DataType*d)/*刪除鏈?zhǔn)疥犃蠶的隊頭數(shù)據(jù)元素值到d，出隊列成功則返回1，否則返回0*/{LQNode*p;if(Q->front==NULL){printf("隊列已空無數(shù)據(jù)元素出隊列!\n");return0;}else{*d=Q->front->data;p=Q->front;Q->front=Q->front->next;if(Q->front==NULL)Q->rear=NULL;free(p);return1;}}

第4章隊列48

intQueueGet(LQueueQ,DataType*d)/*取鏈?zhǔn)疥犃蠶的當(dāng)前隊頭數(shù)據(jù)元素值到d，成功則返回1，否則返回0*/{if(Q.front==NULL){printf("隊列已空無數(shù)據(jù)元素出隊列!\n");return0;}else{*d=Q.front->data;return1;}}voidDestroy(LQueueQ){LQNode*p,*p1;p=Q.front;while(p!=NULL){p1=p;p=p->next;free(p1);}}

第4章隊列49

voidmain(void){LQueuemyQueue;inti;charx='a';QueueInitiate(&myQueue);for(i=0;i<26;i++)QueueAppend(&myQueue,i+x);QueueDelete(&myQueue,&x);printf("%c",x);while(QueueNotEmpty(myQueue)==1){if(QueueGet(myQueue,&x)==0){printf("錯誤!\n");return;}else{printf("%c",x);QueueDelete(&myQueue,&x);}}Destroy(myQueue);}第4章隊列50

本章小結(jié)

本章主要討論隊列的邏輯結(jié)構(gòu)和物理存儲結(jié)構(gòu)以及各種存儲結(jié)構(gòu)下的算法實現(xiàn)。在后續(xù)學(xué)習(xí)中要廣泛的應(yīng)用。其主要內(nèi)容包括：

1.基本概念和術(shù)語⑴隊列是由n個元素組成的有限序列，可記作：Q=（a0，a1，…ai，…，an-1）其中，每個ai都是隊列Q的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類型，但必須屬于同一種數(shù)據(jù)對象。其數(shù)據(jù)元素之間呈線性關(guān)系，其操作的特點是“先進(jìn)先出”，主要操作有入隊、出隊和取隊頭元素等。⑵隊列是限定只能在表的一端進(jìn)行插入操作，另一端進(jìn)行刪除操作的線性表。在表中允許插入的一端叫做隊尾(Rear)，而允許刪除的另一端叫做隊頭(Front)，向隊尾插入一個元素的操作叫做入隊操作，從隊頭取出一個元素的操作叫做出隊操作。

第4章隊列51

2.隊列的存儲結(jié)構(gòu)

⑴順序存儲結(jié)構(gòu)循環(huán)隊列，設(shè)其類型名用SeqCQueue表示，類型定義如下：MaxQueueSize=隊列中允許存放元素個數(shù)的最大值；typedefstruct{DataTypequeue[MaxQueueSize];intrear;/*隊尾指針*/intfront;/*隊頭指針*/}SeqCQueue;

⑵鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈隊列類型LQueue可定義如下：typedefstructqnode{DataTypedata;structqnode*next;}LQNode;

typedefstruct{LQNode*front;/*隊頭指針*/LQNode*rear;/*隊尾指針*/}LQueue;第4章隊列52

3.隊列的有關(guān)操作

對隊列可執(zhí)行以下的基本操作：⑴intQueueInitiate(Q)：初始化操作。設(shè)定一個空的隊列Q。⑵intQueueSize(Q)：求長度函數(shù)。函數(shù)值為給定隊列Q中數(shù)據(jù)元素的個數(shù)。⑶intQueueNotEmpty(Q)：判空隊列函數(shù)。若Q為非空隊列，則返回1，否則返回0。⑷Queueclear(Q)：隊列清空操作。操作的結(jié)果使Q成為空隊列。⑸QueueAppend(LQueue*Q,DataTypex)：入隊列操作。在隊列Q的尾部插入元素x。若隊列Q不滿，則元素x成為插入前隊尾元素的后繼，即x為新的隊尾元素。⑹intQueueDelete(Q,d)出隊列函數(shù)。若隊列Q非空，刪除鏈?zhǔn)疥犃蠶的隊頭數(shù)據(jù)元素值到d，出隊列成功則返回1，且其后繼為新的隊頭元素，否則返回0。⑺intQueueGet(Q,d)：取隊頭元素函數(shù)。若隊列Q非空，則返回1，否則返回0。第4章隊列53

習(xí)題一、填空題1.向量(線性表)和隊列都是

結(jié)構(gòu)，可以在向量的

位置插入和刪除元素；對于隊列只能在

插入和

刪除元素。2.

是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。3.在一個