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

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

核心技能點(diǎn)：隊(duì)列應(yīng)用于實(shí)際問(wèn)題的能力

擴(kuò)展技能點(diǎn)：C語(yǔ)言環(huán)境下隊(duì)列各種算法的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

第4章隊(duì)列74.2隊(duì)列的存儲(chǔ)方式

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

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

第4章隊(duì)列8

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

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

10

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

11

鏈隊(duì)列類(lèi)型LQueue可定義如下：typedefstructqnode{DataTypedata;structqnode*next;}LQNode;

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

12

在程序中使用的鏈隊(duì)列可以用一個(gè)LQueue型變量來(lái)表示，例如：

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

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

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

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

typedefstruct

{

DataTypequeue[MaxQueueSize];

intrear;/*隊(duì)尾指針*/

intfront;/*隊(duì)頭指針*/

}SeqQueue;第4章隊(duì)列14

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

front指針指向剛出隊(duì)的那個(gè)元素的位置，而rear指針指向隊(duì)尾元素的位置，因?yàn)樵趫?zhí)行入隊(duì)、出隊(duì)操作時(shí)，先修改指針，再取出或送入元素。圖4.5順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)第4章隊(duì)列15

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

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

第4章隊(duì)列16

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

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

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

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

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

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

第4章隊(duì)列19

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

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

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

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

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

1.入隊(duì)操作

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

intQueueAppend(SeqCQueue*Q,DataTypex)；

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

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

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

2.出隊(duì)操作

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

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

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

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

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

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

(1)生成一個(gè)元素值為x的新結(jié)點(diǎn)：

(2)將該結(jié)點(diǎn)從隊(duì)尾插入隊(duì)列。

第4章隊(duì)列29

程序如下：intQueueAppend(LQueue*Q,DataTypex)/*把數(shù)據(jù)元素值x插入鏈?zhǔn)疥?duì)列Q的隊(duì)尾，入隊(duì)列成功則返回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鏈隊(duì)列入隊(duì)操作示意圖第4章隊(duì)列30

2.出隊(duì)列操作鏈隊(duì)列的出隊(duì)操作可表示為

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

(1)刪除隊(duì)頭元素，即使頭結(jié)點(diǎn)中的指針指向隊(duì)頭的下一個(gè)結(jié)點(diǎn)。

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

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

圖4.10鏈隊(duì)列出隊(duì)操作示意圖

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

程序如下：intQueueDelete(LQueue*Q,DataType*d)/*刪除鏈?zhǔn)疥?duì)列Q的隊(duì)頭數(shù)據(jù)元素值到d，出隊(duì)列成功則返回1，否則返回0*/{LQNode*p;if(Q->front==Q->rear){printf("隊(duì)列已空無(wú)數(shù)據(jù)元素出隊(duì)列!\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章隊(duì)列33

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

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

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

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

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

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

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

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

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

程序如下：#defineMaxStackSize100typedefcharDataType;/*定義具體應(yīng)用的數(shù)據(jù)類(lèi)型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章隊(duì)列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章隊(duì)列42

4.6上機(jī)實(shí)驗(yàn)

實(shí)驗(yàn)?zāi)康模?/p>

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

1.完成自己的隊(duì)列頭文件

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

3.模仿實(shí)例，完成其它算法

4.完成實(shí)驗(yàn)報(bào)告第4章隊(duì)列43

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

范例鏈?zhǔn)疥?duì)列頭文件內(nèi)容#include<stdio.h>#include<stdlib.h>typedefcharDataType;

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

第4章隊(duì)列45

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

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

第4章隊(duì)列46

intQueueAppend(LQueue*Q,DataTypex)/*把數(shù)據(jù)元素值x插入鏈?zhǔn)疥?duì)列Q的隊(duì)尾，入隊(duì)列成功則返回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章隊(duì)列47

intQueueDelete(LQueue*Q,DataType*d)/*刪除鏈?zhǔn)疥?duì)列Q的隊(duì)頭數(shù)據(jù)元素值到d，出隊(duì)列成功則返回1，否則返回0*/{LQNode*p;if(Q->front==NULL){printf("隊(duì)列已空無(wú)數(shù)據(jù)元素出隊(duì)列!\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章隊(duì)列48

intQueueGet(LQueueQ,DataType*d)/*取鏈?zhǔn)疥?duì)列Q的當(dāng)前隊(duì)頭數(shù)據(jù)元素值到d，成功則返回1，否則返回0*/{if(Q.front==NULL){printf("隊(duì)列已空無(wú)數(shù)據(jù)元素出隊(duì)列!\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章隊(duì)列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("錯(cuò)誤!\n");return;}else{printf("%c",x);QueueDelete(&myQueue,&x);}}Destroy(myQueue);}第4章隊(duì)列50

本章小結(jié)

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

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

第4章隊(duì)列51

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

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

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

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

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

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

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

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

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

插入和

刪除元素。2.

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