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

第4章隊(duì)列4.1隊(duì)列的應(yīng)用實(shí)例及概念4.2隊(duì)列的存儲(chǔ)方式4.3隊(duì)列的有關(guān)操作4.4隊(duì)列的ADT定義及類定義4.5應(yīng)用實(shí)例的實(shí)現(xiàn)4.6實(shí)習(xí)四：循環(huán)隊(duì)列演示程序第4章隊(duì)列4.1隊(duì)列的應(yīng)用實(shí)例及概念14.1隊(duì)列的應(yīng)用實(shí)例及概念隊(duì)列限定只能在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表。在表中允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端叫做隊(duì)頭（front）,向隊(duì)尾插入一個(gè)元素的操作叫做入隊(duì)（enque）操作，從隊(duì)頭取出一個(gè)元素的操作叫做出隊(duì)（dlque）操作。隨著入隊(duì)、出隊(duì)操作的執(zhí)行，隊(duì)列的隊(duì)頭、隊(duì)尾也不斷地隨之改變。由于隊(duì)列的操作具有“先進(jìn)先出”的特點(diǎn)，因此隊(duì)列又稱作先進(jìn)先出表（FIFO，即FirstInFirstOut）。4.1隊(duì)列的應(yīng)用實(shí)例及概念隊(duì)列限定只能在2圖4.1隊(duì)列結(jié)構(gòu)示意圖入隊(duì)圖4.1隊(duì)列結(jié)構(gòu)示意圖入隊(duì)3一般，一個(gè)隊(duì)列是由n個(gè)元素組成的有限序列，可記作：Q=(a1,a2,…,ai,…,an)其中，每個(gè)ai都是隊(duì)列Q的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類型，但必須屬于同一種數(shù)據(jù)元素類。從銀行排隊(duì)等待取款的實(shí)例中我們可以看到，隊(duì)列的操作與排隊(duì)、離隊(duì)的動(dòng)作非常相似，入隊(duì)操作就相當(dāng)于來了一位新的顧客在隊(duì)尾排隊(duì)等候的事件，而出隊(duì)操作就相當(dāng)于取款后離隊(duì)的事件。除了入隊(duì)(enque)、出隊(duì)(dlque)操作以外，隊(duì)列的操作通常還包括初始化（init）、求當(dāng)前元素個(gè)數(shù)（currentsize）、判是否為空隊(duì)列（empty）、清空（clear）以及取隊(duì)頭元素（getfirst）等。一般，一個(gè)隊(duì)列是由n個(gè)元素組成的有限序列，可記作：Q=(4綜上所述，隊(duì)列是一種數(shù)據(jù)類型，其數(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)度策略就是“先來先服務(wù)”，也就是要使用一個(gè)隊(duì)列來實(shí)現(xiàn)這種調(diào)度策略。同樣在做輸出時(shí)也要按請(qǐng)求輸出的先后次序排隊(duì)。作業(yè)輸出統(tǒng)一由操作系統(tǒng)中的輸出程序來執(zhí)行，每當(dāng)輸出程序傳輸完畢可以接收新的輸出任務(wù)時(shí)，隊(duì)頭的輸出作業(yè)從隊(duì)列中退出做輸出操作。凡是請(qǐng)求輸出的作業(yè)都是從隊(duì)尾進(jìn)入隊(duì)列的。綜上所述，隊(duì)列是一種數(shù)據(jù)類型，其數(shù)據(jù)元素之間5此外，在一些算法中也經(jīng)常使用隊(duì)列。例如，在圖的遍歷的非遞歸算法中，要使用一個(gè)“層次隊(duì)列”來存放已訪問的上層元素，由此來實(shí)現(xiàn)對(duì)下層元素的依次訪問。為了對(duì)隊(duì)列及其有關(guān)操作的實(shí)現(xiàn)方法有比較直觀的了解，我們可以作成一個(gè)循環(huán)隊(duì)列的演示程序。在演示操作屏幕中設(shè)置一個(gè)繪圖板顯示循環(huán)隊(duì)列的當(dāng)前狀態(tài)，即用一個(gè)環(huán)形的區(qū)域表示循環(huán)隊(duì)列并顯示其中的當(dāng)前元素，數(shù)據(jù)元素可以使用形影線來標(biāo)記；設(shè)置一個(gè)組合框用于指定當(dāng)前的入隊(duì)元素及顯示當(dāng)前的出隊(duì)元素；設(shè)置清空、入隊(duì)、出隊(duì)、退出等四個(gè)操作按鈕用于進(jìn)行演示操作（見實(shí)習(xí)四：循環(huán)隊(duì)列演示程序）。此外，在一些算法中也經(jīng)常使用隊(duì)列。例如，在64.2隊(duì)列的存儲(chǔ)方式4.2.1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖4.2鏈隊(duì)列示意圖4.2隊(duì)列的存儲(chǔ)方式4.2.1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖7圖4.3鏈隊(duì)列指針變化狀況(a)空隊(duì)列；(b)a入隊(duì)列；(c)b入隊(duì)列；(d)a出隊(duì)列圖4.3鏈隊(duì)列指針變化狀況8圖4.4鏈隊(duì)列類型結(jié)構(gòu)圖4.4鏈隊(duì)列類型結(jié)構(gòu)9假設(shè)結(jié)點(diǎn)類型名為nodetp，結(jié)點(diǎn)指針類型名為link，結(jié)點(diǎn)類型中數(shù)據(jù)域名為data，指針域名為next，數(shù)據(jù)元素的類型為elemtp,鏈隊(duì)列的頭指針和尾指針分別為front與rear，則鏈隊(duì)列類型lquetp可定義如下：typelink=^nodetpnodetp=recorddata:elemtp;next:link;end;lquetp=recordfront:link;rear:link;end;假設(shè)結(jié)點(diǎn)類型名為nodetp，結(jié)點(diǎn)指針類型名10在程序中使用的鏈隊(duì)列可以用一個(gè)lquetp型變量來表示，例如:varlq1:lquetp;當(dāng)lq1.front=lq1.rear時(shí)，這個(gè)隊(duì)列就成為空隊(duì)列，否則，lq1.front^.next指向隊(duì)頭結(jié)點(diǎn)，而lq1.rear指向隊(duì)尾結(jié)點(diǎn)。和鏈棧的情形相同，一般不會(huì)出現(xiàn)隊(duì)列滿的情形，除非整個(gè)可用空間都被占滿，new(p)都無法執(zhí)行的情形下才會(huì)發(fā)生上溢。同樣空隊(duì)列的狀態(tài)在程序設(shè)計(jì)中也被用作實(shí)現(xiàn)控制轉(zhuǎn)移的條件。在程序中使用的鏈隊(duì)列可以用一個(gè)lquetp型114.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)圖4.5順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)4.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)圖4.5順序隊(duì)列的存12圖4.6順序隊(duì)列中頭尾指針的變化(a)空隊(duì)列；(b)a、b、c、d依次入隊(duì)；(c)a、b、c依次出隊(duì)；(d)e、f入隊(duì)圖4.6順序隊(duì)列中頭尾指針的變化13對(duì)一般的順序隊(duì)列，我們可以用front=rear作為判別隊(duì)列是否為空的條件；用rear≥max作為判別隊(duì)列是否為滿的條件。當(dāng)隊(duì)列非空時(shí)，可執(zhí)行如下的出隊(duì)操作：front:=front+1;data:=elem［front］;當(dāng)隊(duì)列非滿時(shí)，可執(zhí)行如下的入隊(duì)操作：rear:=rear+1;elem［rear］:=data;對(duì)一般的順序隊(duì)列，我們可以用front=r14在這里值得考慮的是：當(dāng)rear≥max時(shí)，隊(duì)列是否真正為滿？假設(shè)當(dāng)前隊(duì)列是處在圖4.6(d)的狀態(tài)，即max=6,rear=6,front=3,顯然此時(shí)不能再做入隊(duì)列的操作，因?yàn)閞ear≥max，但隊(duì)列中實(shí)際上并未存滿元素，這種現(xiàn)象稱為假溢出。當(dāng)然，在發(fā)生假溢出時(shí)可以將全部元素向下移動(dòng)直至頭指針為0，但這樣處理效率不高。一個(gè)比較巧妙的辦法是將隊(duì)列設(shè)想成首尾相接的環(huán)，一端放滿時(shí)再?gòu)牧硪欢舜嫒?，只要尾指針不與頭指針相遇，該隊(duì)列即可使用下去。這就是我們所講的循環(huán)隊(duì)列。在這里值得考慮的是：當(dāng)rear≥max時(shí)，隊(duì)15圖4.7循環(huán)隊(duì)列示意圖圖4.7循環(huán)隊(duì)列示意圖16圖4.8循環(huán)隊(duì)列的頭尾指針(a)空隊(duì)列;(b)隊(duì)列中有一個(gè)元素；(c)隊(duì)列滿圖4.8循環(huán)隊(duì)列的頭尾指針17另外對(duì)于循環(huán)隊(duì)列，無論是頭指針還是尾指針，在對(duì)其進(jìn)行加1處理時(shí)，都要考慮對(duì)結(jié)果取模。綜上所述：我們可以用front=rear作為判別隊(duì)列是否為空的條件；用(rear+1)modmax=front作為判別隊(duì)列是否為滿的條件。當(dāng)隊(duì)列非空時(shí)，可執(zhí)行如下的出隊(duì)操作：front:=(front+1)modmax;data:=elem［front］;當(dāng)隊(duì)列非滿時(shí)，可執(zhí)行如下的入隊(duì)操作：rear:=(rear+1)modmax;elem［rear］:=data;另外對(duì)于循環(huán)隊(duì)列，無論是頭指針還是尾指針，18如前所述，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，應(yīng)該包括一個(gè)存儲(chǔ)數(shù)據(jù)元素的一維數(shù)組，取其名為elem，其長(zhǎng)度可取為一個(gè)適當(dāng)?shù)淖畲笾祄ax，另外還應(yīng)包括兩個(gè)位置指示器front和rear，它們分別指向隊(duì)頭和隊(duì)尾的位置，使用Pascal語言，我們可以定義以下的記錄（結(jié)構(gòu)）類型來表示順序隊(duì)列或循環(huán)隊(duì)列，假設(shè)其類型名用squetp表示：constmax＝隊(duì)列中允許存放元素個(gè)數(shù)的最大值；typesquetp=recordelem:array［1..max］ofelemtp；front,rear:0..maxend；如前所述，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，應(yīng)該包括19在定義了順序隊(duì)列的類型squetp之后，我們就可以定義屬于這種類型的隊(duì)列，例如：varq1:squetp；此后可在程序中引用順序隊(duì)列q1的相應(yīng)成分，例如，q1.elem［q1.rear］表示隊(duì)尾元素等。在定義了順序隊(duì)列的類型squetp之后，我204.3隊(duì)列的有關(guān)操作4.3.1循環(huán)隊(duì)列的操作實(shí)現(xiàn)1.入隊(duì)操作循環(huán)隊(duì)列的入隊(duì)操作可表示為：functionenque(varcq:squetpel:elemtp):boolean;其中，參數(shù)cq表示指定的循環(huán)隊(duì)列，其類型為squetp；參數(shù)el表示入隊(duì)列的元素，其類型為元素類型elemtp。該操作返回一個(gè)布爾型的函數(shù)值，表示入隊(duì)操作是否執(zhí)行成功。操作的功能為在循環(huán)隊(duì)列cq中插入元素el。若循環(huán)隊(duì)列cq不滿，則插入el新的隊(duì)尾元素，并返回函數(shù)值true，否則隊(duì)列的狀態(tài)不變且返回函數(shù)值false。4.3隊(duì)列的有關(guān)操作4.3.1循環(huán)隊(duì)列的操作實(shí)現(xiàn)21處理過程為判是否隊(duì)列滿。若隊(duì)列滿，則返回false，否則，隊(duì)列尾指針加1，將el從隊(duì)尾插入隊(duì)列并返回true。程序如下：functionenque(varcq:squetp,el:elemtp):boolean;beginif(cq.rear+1)modmax=cq.frontthenresult:=falseelsebegincq.rear:=(cq.rear+1)modmax;cq.elem［cq.rear］:=el;result:=trueendend;處理過程為判是否隊(duì)列滿。若隊(duì)列滿，則返回f222.出隊(duì)操作循環(huán)隊(duì)列的出隊(duì)操作可表示為：functiondlque(varcq:squetp):elemtp;其中，參數(shù)cq表示指定的循環(huán)隊(duì)列，其類型為squetp。該操作是一個(gè)函數(shù)，其返回值表示從隊(duì)列中取出的隊(duì)頭元素。操作的功能為：若循環(huán)隊(duì)列cq非空，則從cq中取出隊(duì)頭元素并返回該元素，否則返回空元素NULL。處理過程為判隊(duì)列是否為空隊(duì)列。若隊(duì)列為空隊(duì)列，則返回NULL，否則，隊(duì)列頭指針加1并返回隊(duì)頭元素。2.出隊(duì)操作23程序如下：functiondlque(varcq:squetp):elemtp;beginifcq.front＝cq.rearthenresult:=NULLelsebegincq.front:=(cq.front+1)modmax;result:=cq.elem［cq.front］endend;程序如下：243.其他操作初始化操作：設(shè)置循環(huán)隊(duì)列cq為空的循環(huán)隊(duì)列。procedureinit(varcq:squetp);begincq.front:=0;cq.rear:=0;end;3.其他操作25求長(zhǎng)度操作：返回循環(huán)隊(duì)列cq中所含元素的個(gè)數(shù)。functionsize(cq:squetp):integer;beginsize:=(cq.rear-cq.front+max)modmax;end;求長(zhǎng)度操作：返回循環(huán)隊(duì)列cq中所含元素的個(gè)數(shù)。26判空隊(duì)列操作：若隊(duì)列為空，則返回true，否則返回false。functionempty(cq:squetp):boolean;beginifcq.front=cq.rearthenempty:=trueelseempty:=false;end;判空隊(duì)列操作：若隊(duì)列為空，則返回true，否則返回fa27判隊(duì)列滿操作：若隊(duì)列滿，則返回true，否則返回false。functionfull(cq:squetp):boolean;beginif(cq.rear+1)modmax=cq.frontthenfull:=trueelsefull:=falseend;判隊(duì)列滿操作：若隊(duì)列滿，則返回true，否則返回fal28取隊(duì)頭操作：若隊(duì)列非空，則返回隊(duì)頭元素，否則返回NULL。functiongetf(cq:squetp):elemtp;beginifcq.front＝cq.rearthenresult:=NULLelseresult:=cq.elem［(cq.front+1)modmax］end;取隊(duì)頭操作：若隊(duì)列非空，則返回隊(duì)頭元素，否則返回NUL294.3.2鏈隊(duì)列的操作實(shí)現(xiàn)1.入隊(duì)列操作鏈隊(duì)列的入隊(duì)操作可表示為procedureenque(varq:lquetpel:elemtp);其中，參數(shù)q表示指定的鏈隊(duì)列，其類型為lquetp；參數(shù)el表示入隊(duì)列的元素，其類型為元素類型elemtp。操作的功能為在鏈隊(duì)列q中插入新的隊(duì)尾元素el。4.3.2鏈隊(duì)列的操作實(shí)現(xiàn)1.入隊(duì)列操30圖4.9鏈隊(duì)列入隊(duì)操作示意圖圖4.9鏈隊(duì)列入隊(duì)操作示意圖31處理過程為（見圖4.9）：（1）生成一個(gè)元素值為el的新結(jié)點(diǎn)：（2）將該結(jié)點(diǎn)從隊(duì)尾插入隊(duì)列。程序如下：procedureenque(varq:lquetp,el:elemtp);varp:link;beginnew(p);p^.data:=el;p^next:=NIL;q.rear^next:=p;q.rear:=p;end;處理過程為（見圖4.9）：322．出隊(duì)列操作鏈隊(duì)列的出隊(duì)操作可表示為functiondlque(varq:lquetp):elemtp;其中，參數(shù)q表示指定的鏈隊(duì)列，其類型為lquetp。該操作是一個(gè)函數(shù)，其返回值表示從隊(duì)列中取出的隊(duì)頭元素。操作的功能為：若鏈隊(duì)列q非空，則從q中取出隊(duì)頭元素并返回該元素，否則返回空元素NULL。2．出隊(duì)列操作33圖4.10鏈隊(duì)列出隊(duì)操作示意圖圖4.10鏈隊(duì)列出隊(duì)操作示意圖34若鏈隊(duì)列q為空，則返回空元素NULL，否則：（1）刪除隊(duì)頭元素，即使頭結(jié)點(diǎn)中的指針指向隊(duì)頭的下一個(gè)結(jié)點(diǎn)。（2）若刪除后成為空隊(duì)列，則使頭尾指針值相同。（3）取刪除結(jié)點(diǎn)的值作為返回值，并釋放該結(jié)點(diǎn)。若鏈隊(duì)列q為空，則返回空元素NULL，35程序如下：functiondlque(varq:lquetp):elemtp;vars:link;el:elemtp;beginifq.front＝q.rearthenresult:=NULLelsebegins:=q.front^next;q.front^next:=s^.next;ifs^.next=nilthenq.rear:=q.front;el:=s^.data;dispose(s);result:=elendend;程序如下：363.其他操作初始化操作：設(shè)置一個(gè)空的鏈隊(duì)列，由q表示之。處理過程：生成一個(gè)頭結(jié)點(diǎn)，并使q的頭尾指針均指向它。procedureinit(varq:lquetp);beginnew(q.front);q.rear:=q.front;q.front^.next:=nil;end;3.其他操作37求長(zhǎng)度操作：返回鏈隊(duì)列q中所含元素的個(gè)數(shù)。functionsize(q:lquetp):integer;varp:link;i:integer;beginp:=q.front^.next;i:=0;whilep<>nildobegini:=i+1;p:=p^.nextendsize:=i;end;求長(zhǎng)度操作：返回鏈隊(duì)列q中所含元素的個(gè)數(shù)。38判空隊(duì)列操作：若隊(duì)列為空，則返回true，否則返回false。functionempty(q:lquetp):boolean;beginifq.front=q.rearthenempty:=trueelseempty:=false;end;判空隊(duì)列操作：若隊(duì)列為空，則返回true，否則返回false39取隊(duì)頭操作：若隊(duì)列非空，則返回隊(duì)頭元素，否則返回NULL。functiongetf(q:lquetp):elemtp;beginifq.front＝q.rearthenresult:=NULLelseresult:=q.front^.next^.data;end;取隊(duì)頭操作：若隊(duì)列非空，則返回隊(duì)頭元素，否則返回NULL。404.4隊(duì)列的ADT定義及類定義4.4.1隊(duì)列的ADT定義與線性表、棧的情形類似，我們可以定義隊(duì)列的抽象數(shù)據(jù)類型。一種數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。以下是隊(duì)列的ADT定義：元素：可以是各種類型的數(shù)據(jù)，但必須同屬于一個(gè)數(shù)據(jù)元素類；結(jié)構(gòu)：隊(duì)列中的n個(gè)元素呈線性關(guān)系；4.4隊(duì)列的ADT定義及類定義4.4.1隊(duì)列的ADT定41(1)init(q)：初始化操作。設(shè)定一個(gè)空的隊(duì)列q。(2)currentsize(q)：求長(zhǎng)度函數(shù)。函數(shù)值為給定隊(duì)列q中數(shù)據(jù)元素的個(gè)數(shù)。(3)empty(q)：判空隊(duì)列函數(shù)。若q為空隊(duì)列，則返回布爾值true,否則返回布爾值false。(4)clear(q)：隊(duì)列清空操作。操作的結(jié)果使q成為空隊(duì)列。(5)enque(q,x)：入隊(duì)列操作。在隊(duì)列q的尾部插入元素x。若隊(duì)列q不滿，則元素x成為插入前隊(duì)尾元素的后繼，即x為新的隊(duì)尾元素。操作：對(duì)隊(duì)列可執(zhí)行以下的基本操作：(1)init(q)：初始化操作。設(shè)定42(6)dlque(q)：出隊(duì)列函數(shù)。若隊(duì)列q非空，則刪除隊(duì)頭元素并返回該元素，且其后繼為新的隊(duì)頭元素，否則返回函數(shù)值為空元素NULL。(7)getf(q)：取隊(duì)頭元素函數(shù)。若隊(duì)列q非空，則返回函數(shù)值為隊(duì)頭元素，否則返回函數(shù)值為空元素NULL。(6)dlque(q)：出隊(duì)列函數(shù)。若434.4.2循環(huán)隊(duì)列的類定義在循環(huán)隊(duì)列的類定義中，其數(shù)據(jù)部分應(yīng)包括存儲(chǔ)數(shù)據(jù)元素的一個(gè)一維數(shù)組，取名為elem，另外還應(yīng)包括表示隊(duì)頭、隊(duì)尾的整型變量，分別取名為front及rear。相應(yīng)的操作為初始化(init)，顯示(prnt)，入隊(duì)列(enque)，出隊(duì)列(dlque)等等。變量elem、front及rear為類中的內(nèi)部數(shù)據(jù)，要封裝在這個(gè)類中，因此為私有變量，外界的程序不能訪問這個(gè)變量，但在這個(gè)類定義之內(nèi)，所有的過程或函數(shù)都能訪問它，也正因?yàn)檫@樣，在類中定義的過程或函數(shù)的參數(shù)中，不必指定所要操作的循環(huán)隊(duì)列。類中所定義的操作是該類向外界提供的接口，因此被定義成公用型。類型elemtp是表示循環(huán)隊(duì)列中的元素類型，在應(yīng)用程序中，它再與另一種具體的類型相對(duì)應(yīng)。例如，在演示程序中，數(shù)據(jù)元素的類型elemtp與字符類型相對(duì)應(yīng)。4.4.2循環(huán)隊(duì)列的類定義44循環(huán)隊(duì)列的類Txhdl可定義如下：constmax＝隊(duì)列中允許存放元素個(gè)數(shù)的最大值；typeelemtp=char;Txhdl=classprivateelem:array［1..max］ofelemtp；front,rear:0..maxpublicprocedureinit;procedureprnt;循環(huán)隊(duì)列的類Txhdl可定義如下：constmax＝隊(duì)45functionenque(el:elemtp):boolean;functiondlque:elemtp;functiongetf:elemtp;functionempty:boolean;functionfull:boolean;functionsize:integer;end;implementationprocedureTxhdl.init;beginfront:=0;rear:=0;end;functionenque(el:ele46procedureTxhdl.prnt;varip:integer;beginiffront<>rearthenbeginip:=front;whileip<>reardobegin顯示elem［ip］;ip:=(ip+1)modmax;endendend……procedureTxhdl.prnt;47與順序表、順序棧的情形相類似，對(duì)上述類定義有以下幾點(diǎn)需作說明：(1)上述類定義中數(shù)組采用了靜態(tài)分配的方式，但為了實(shí)現(xiàn)數(shù)據(jù)封裝，最好采用動(dòng)態(tài)分配，同時(shí)將數(shù)組的長(zhǎng)度max定義為類中私有量。(2)在類定義時(shí)數(shù)據(jù)元素的類型實(shí)際上是不確定的，所以最好是采用“模板”方式。即在類定義時(shí)指定參數(shù)化數(shù)據(jù)類型，而在實(shí)例生成時(shí)才指定對(duì)應(yīng)的元素類型。(3)初始化過程init的處理過程是將隊(duì)列的頭尾指針設(shè)置為0，即front:=0;rear:=0。入隊(duì)、出隊(duì)操作的處理過程已在前節(jié)中作過討論，稍有不同的是在類定義中，可直接引用elem、front、rear而無需加上“cq.”。(4)對(duì)于顯示程序prnt，其功能是顯示循環(huán)隊(duì)列中的當(dāng)前元素。與順序表、順序棧的情形相類似，對(duì)上述類定義有484.4.3鏈隊(duì)列的類定義

在鏈隊(duì)列的類定義中，其數(shù)據(jù)部分應(yīng)包括一個(gè)以鏈表形式存儲(chǔ)的隊(duì)列，可以用一個(gè)頭指針和一個(gè)尾指針來表示它，分別取名為front與rear。由于結(jié)點(diǎn)的類定義為Tnode，而在ObjectPascal中，實(shí)例變量實(shí)際上就是相應(yīng)類的指針變量，因此front與rear的類型可指定為Tnode型。相應(yīng)的操作也與循環(huán)隊(duì)列的類定義中的操作相類似,所不同的是入隊(duì)操作是一個(gè)過程而不是函數(shù)，因此鏈隊(duì)列的入隊(duì)操作不必考慮隊(duì)列是否滿的問題。變量front與rear作為私有變量封裝在這個(gè)類中，外界的程序不能訪問這個(gè)變量，但在這個(gè)類定義之內(nèi)，所有的過程或函數(shù)都能訪問它。也正因?yàn)檫@樣，在類中定義的過程或函數(shù)的參數(shù)中，不必指定所要操作的鏈隊(duì)列。類中所定義的操作是該類向外界提供的接口，因此被定義成公用型。類型elemtp是表示鏈隊(duì)列中的元素類型，在應(yīng)用程序中，它應(yīng)與一種具體的類型相對(duì)應(yīng)。4.4.3鏈隊(duì)列的類定義49鏈隊(duì)列的類Tldl可定義如下：typeTnode=classprivatedata:elemtp;next:Tnode;end;Tldl=classprivatefront:Tnode;rear:Tnode;鏈隊(duì)列的類Tldl可定義如下：50publicprocedureinit;procedureprnt;procedureenque(el:elemtp)functiondlque:elemtp;functiongetf:elemtp;functionempty:boolean;functionfull:boolean;functionsize:integer;end;implementationprocedureTldl.init;beginfront:=Tnode.create;rear:=front;public51front.next:=nil;end;procedureTldl.prnt;varp:Tnode;beginp:=front.next;whilep<>nildobegin顯示p.data;p:=p.next;end;end;……front.next:=nil;52在這個(gè)類的實(shí)現(xiàn)中，初始化過程init的處理過程是生成一個(gè)附加結(jié)點(diǎn)，由front及rear指向，并將該結(jié)點(diǎn)的指針域設(shè)置為nil。入隊(duì)與出隊(duì)操作的處理過程已在前節(jié)中作過討論，但在類定義中，我們已將結(jié)點(diǎn)的類型定義也改成了類定義(Tnode)，為此需作以下改動(dòng)：(1)應(yīng)將link型的變量改為Tnode型。因?yàn)樵贠bjectPascal中，實(shí)體變量實(shí)際上就是相應(yīng)類的指針變量，例如p:link應(yīng)改為p:Tnode。(2)在引用時(shí)也不必加上指針符號(hào)^，例如p^.data應(yīng)改為p.data。(3)在生成時(shí)不是使用new，而是用create。例如new(p)應(yīng)改為p:=Tnode.create。在這個(gè)類的實(shí)現(xiàn)中，初始化過程init的處理過534.5應(yīng)用實(shí)例的實(shí)現(xiàn)圖4.11楊輝三角形及其一維排列4.5應(yīng)用實(shí)例的實(shí)現(xiàn)圖4.11楊輝三角形及其一維排列54處理過程為：（1）設(shè)置隊(duì)列初態(tài)。初態(tài)時(shí)在隊(duì)列中存放第二行的元素和第三行的第一個(gè)元素，front指針指向第二行的第一個(gè)元素，而rear指針指向下一個(gè)將要存入的元素的位置。（2）在不是遇到行尾的1的情形下（行尾為1即在循環(huán)隊(duì)列中隊(duì)頭及隊(duì)二兩個(gè)元素均為1），可將隊(duì)頭及隊(duì)二兩個(gè)元素相加，形成一個(gè)新元素從隊(duì)尾進(jìn)入，頭尾指針均移動(dòng)一個(gè)位置；在遇到行尾的1的情形下，從隊(duì)尾連續(xù)的進(jìn)入兩個(gè)1，而從隊(duì)頭只退出一個(gè)1。（3）重復(fù)執(zhí)行過程（2），直至隊(duì)列滿。處理過程為：55圖4.12楊輝三角形的生成過程(a)第六行元素已生成的狀態(tài)；(b)第七行元素已生成的狀態(tài)圖4.12楊輝三角形的生成過程56在使用Delphi實(shí)現(xiàn)該算法時(shí)，先要建立一個(gè)循環(huán)隊(duì)列的類Tcq，隊(duì)列的元素類型為整型，該類向外界提供入隊(duì)enq、出隊(duì)dlq、取隊(duì)頭getf、取隊(duì)二gets、判隊(duì)滿full及顯示prt等操作。由于前二行比較特殊，算法從第三行起開始處理，即初態(tài)時(shí)在隊(duì)列中存放第二行的元素和第三行的第一個(gè)元素。隊(duì)列實(shí)體q1的生成及初態(tài)的設(shè)置是在窗體建立事件中進(jìn)行的：procedureTyhsjForm.FormCreate(Sender:TObject);beginq1:=Tcq.Create;q1.init;q1.enq(1);q1.enq(2);q1.enq(1);q1.enq(1);end;在使用Delphi實(shí)現(xiàn)該算法時(shí)，先要建立一個(gè)57下述程序的功能是由第i-1行的兩個(gè)相鄰的元素，生成第i行的一個(gè)相應(yīng)的元素。vara,b:integer;beginifnotq1.fullthenbeginif(q1.getf=1)and(q1.gets=1)thenbeginq1.dlq;q1.enq(1);q1.enq(1);endelsebegina:=q1.dlq;b:=q1.getf;q1.enq(a+b);end;q1.prt;endend;下述程序的功能是由第i-1行的兩個(gè)相鄰的元素58上述程序中的a:=q1.dlq;b:=q1.getf。因?yàn)檫\(yùn)算中要使用兩個(gè)元素，而隊(duì)列中的頭指針只要移動(dòng)一個(gè)位置，所以一個(gè)執(zhí)行dlq操作，而另一個(gè)執(zhí)行g(shù)etf操作。iffront<>rearthenbeginip:=front;whileip<>reardobegins:=inttostr(elem［ip］);yhsjform.PaintBox1.Canvas.textout(ip*30,10,s);ip:=(ip+1)modmax;endend上述程序中的a:=q1.dlq;b:=q159整個(gè)程序的清單如下：constn=12;typeelemtp=integer;Tcq=classprivatefront,rear:integer;elem:array［0..n-1］ofelemtp;publicprocedureinit;functionfull:boolean;functionenq(el:elemtp):boolean;functiondlq:elemtp;functiongetf:elemtp;functiongets:elemtp;procedureprt;end;整個(gè)程序的清單如下：60implementationvarq1:Tcq;procedureTcq.init;beginfront:=0;rear:=0end;functionTcq.full:boolean;beginif(rear+1)modn=frontthenfull:=trueelsefull:=falseend;implementation61functionTcq.enq(el:elemtp):boolean;beginif(rear+1)modn=frontthenenq:=falseelsebeginelem［rear］:=el;rear:=(rear+1)modn;enq:=trueendend;functionTcq.dlq:elemtp;varel:elemtp;beginifrear=frontthendlq:=0elsebeginel:=elem［front］;front:=(front+1)modn;dlq:=elendfunctionTcq.enq(el:elemtp)62end;functionTcq.getf:elemtp;beginifrear=frontthengetf:=0elsegetf:=elem［front］end;functionTcq.gets:elemtp;beginif(rear=front)or((front+1)modn=rear)thengets:=0elsegets:=elem［(front+1)modn］end;end;63procedureTcq.prt;varip,i,ix,iy,ix0,iy0:integer;rect1:Trect;\s:string［25］;beginrect1:=rect(0,0,400,100);yhsjform.PaintBox1.Canvas.Brush.Color:=clBtnFace;yhsjform.PaintBox1.Canvas.FillRect(rect1);yhsjform.PaintBox1.Canvas.pen.Color:=clblack;yhsjform.PaintBox1.Canvas.pen.width:=1;yhsjform.PaintBox1.Canvas.font.Color:=clred;yhsjform.PaintBox1.Canvas.font.size:=15;iffront<>rearthenbeginip:=front;procedureTcq.prt;64whileip<>reardobegins:=inttostr(elem［ip］);yhsjform.PaintBox1.Canvas.textout(ip*30,10,s);ip:=(ip+1)modn;endendend;procedureTyhsjForm.ButxygClick(Sender:TObject);vara,b:integer;beginifnotq1.fullthenbeginif(q1.getf=1)and(q1.gets=1)thenwhileip<>reardo65beginq1.dlq;q1.enq(1);q1.enq(1);endelsebegina:=q1.dlq;b:=q1.getf;q1.enq(a+b);end;q1.prt;endend;procedureTyhsjForm.FormCreate(Sender:TObject);beginq1:=Tcq.Create;q1.init;q1.enq(1);q1.enq(2);q1.enq(1);q1.enq(1);end;begin66procedureTyhsjForm.FormClose(Sender:TObject;varAction:TCloseAction);beginq1.Free;end;procedureTyhsjForm.ButtcClick(Sender:TObject);beginclose;release;end;procedureTyhsjForm.PaintBox1Paint(Sender:TObject);beginq1.prtend;procedureTyhsjForm.FormClose(674.6實(shí)習(xí)四：循環(huán)隊(duì)列演示程序4.6.1問題說明循環(huán)隊(duì)列是隊(duì)列中的頭尾兩個(gè)存儲(chǔ)單元在邏輯上相鄰的隊(duì)列。入隊(duì)時(shí)指定的元素從隊(duì)尾進(jìn)入，尾指針加1并對(duì)長(zhǎng)度取模；出隊(duì)時(shí)從隊(duì)頭取出一個(gè)元素，頭指針加1并對(duì)長(zhǎng)度取模。只有在頭尾指針相遇時(shí)才能確定為隊(duì)列存儲(chǔ)空間滿。因此，其存儲(chǔ)空間的使用效率比一般的順序隊(duì)列要高。編制一個(gè)具有Windows圖形用戶界面的教學(xué)演示程序，模擬循環(huán)隊(duì)列的入隊(duì)、出隊(duì)等操作的執(zhí)行過程。4.6實(shí)習(xí)四：循環(huán)隊(duì)列演示程序4.6.1問題說明684.6.2界面外觀及功能要求圖4.13循環(huán)隊(duì)列演示程序4.6.2界面外觀及功能要求圖4.13循環(huán)隊(duì)列演示程694.6.3實(shí)現(xiàn)要點(diǎn)循環(huán)隊(duì)列實(shí)現(xiàn)的要點(diǎn)：(1)循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)及操作儲(chǔ)存區(qū)：elem［0..n-1］隊(duì)頭指針：front隊(duì)尾指針：rear空隊(duì)列：front=rear滿隊(duì)列：(rear+1)modn=front入隊(duì)操作：elem［rear］:=el;rear:=(rear+1)modn出隊(duì)操作：ch:=elem［front］;front:=(front+1)modn;返回ch;4.6.3實(shí)現(xiàn)要點(diǎn)70(2)繪圖處理：用紅色的圓點(diǎn)表示front指針，用白色的圓點(diǎn)表示rear指針，用較密的半徑線表示已入隊(duì)的元素。設(shè)環(huán)形的圓心坐標(biāo)為（100，100），位置半徑為30，指針指向第i個(gè)緩沖區(qū)，圓點(diǎn)的半徑為3，則圓點(diǎn)可以用Ellipse方法畫出：ix0:=100+round(30*cos(pi*front/6+pi/12));iy0:=100-round(30*sin(pi*front/6+pi/12));Ellipse(ix0-3,iy0-3,ix0+3,iy0+3);(2)繪圖處理：71同樣，環(huán)形的內(nèi)半徑分別為50、80，則標(biāo)記第i個(gè)緩沖區(qū)已存入元素的程序如下：fori:=1to9dobeginix0:=100+round(50*cos(pi*ip/6+pi*i/60));iy0:=100-round(50*sin(pi*ip/6+pi*i/60));moveto(ix0,iy0);ix:=100+round(80*cos(pi*ip/6+pi*i/60));iy:=100-round(80*sin(pi*ip/6+pi*i/60));lineto(ix,iy);end;同樣，環(huán)形的內(nèi)半徑分別為50、80，724.6.4類定義將循環(huán)隊(duì)列定義成一個(gè)類，其數(shù)據(jù)由n個(gè)元素的隊(duì)列存儲(chǔ)區(qū)域elem及隊(duì)列頭front、指針隊(duì)列尾指針rear組成。相應(yīng)的操作為初始化(procedureinit)，入隊(duì)列(functionenq(el:elemtp):boolean)，出隊(duì)列(functiondlq:elemtp)及隊(duì)列顯示(procedureprt)等。在本演示程序中，元素類型elemtp為字符類型char。循環(huán)隊(duì)列類Tcq的定義如下：4.6.4類定義73elemtp=char;Tcq=classprivatefront,rear:integer;elem:array［0..n-1］ofelemtp;publicprocedureinit;functionenq(el:elemtp):boolean;functiondlq:elemtp;procedureprt;end;elemtp=char;744.6.5類的實(shí)現(xiàn)(1)初始化過程(init)：將front,rear指針均設(shè)置為0。(2)入隊(duì)列函數(shù)(enq(el:elemtp):boolean)：將數(shù)據(jù)值為el的元素從隊(duì)末插入到隊(duì)列中。若隊(duì)列為滿，則返回false,否則插入后返回true。(3)出隊(duì)列函數(shù)(dlq:elemtp)：可取出并返回隊(duì)頭元素。若隊(duì)列為空，則返回空元素。4.6.5類的實(shí)現(xiàn)75(4)隊(duì)列顯示過程(prt)：顯示當(dāng)前的循環(huán)隊(duì)列。其處理步驟如下：①繪圖板清空。②畫兩個(gè)同心圓，即以環(huán)形區(qū)域表示循環(huán)隊(duì)列。③在環(huán)形區(qū)域中畫元素分割線。④分別畫出front指針與rear指針。⑤將循環(huán)隊(duì)列中的當(dāng)前元素在環(huán)形區(qū)域中表示出來。(4)隊(duì)列顯示過程(prt)：顯示當(dāng)前的764.6.6組件設(shè)置PaintBox1：繪圖板，用于顯示一個(gè)環(huán)形區(qū)域表示循環(huán)隊(duì)列的當(dāng)前狀態(tài)。Comb1：組合框，用于指定入隊(duì)元素或顯示出隊(duì)元素。ButRd,Cd,Qt,Tc：分別為入隊(duì)、出隊(duì)、取頭及退出操作按鈕。4.6.6組件設(shè)置774.6.7界面功能的實(shí)現(xiàn)我們已將循環(huán)隊(duì)列定義成一個(gè)類，在實(shí)現(xiàn)界面功能時(shí)只需生成一個(gè)該類的實(shí)體并對(duì)其施行相應(yīng)的操作即可。各事件處理程序如下：(1)窗體生成事件處理程序：在窗體生成事件處理程序中生成一個(gè)Tcq類的實(shí)體q1，并執(zhí)行初始化。procedureTForm1.FormActivate(Sender:TObject);beginq1:=Tcq.Create;q1.init;end;4.6.7界面功能的實(shí)現(xiàn)78(2)窗體關(guān)閉事件處理程序：在窗體關(guān)閉事件處理程序中釋放已生成的實(shí)體q1，并關(guān)閉窗體釋放空間。procedureTForm1.FormClose(Sender:TObject;varAction:TCloseAction);beginq1.Free;close;release;end;(2)窗體關(guān)閉事件處理程序：79(3)入隊(duì)按鈕的事件處理程序：以組合框中的信息為參數(shù)對(duì)q1執(zhí)行入隊(duì)操作。若成功，則重新顯示循環(huán)隊(duì)列（即對(duì)q1執(zhí)行顯示操作），否則輸出相應(yīng)的通告信息。procedureTForm1.ButrdClick(Sender:TObject);varch:elemtp;beginch:=comb1.text［1］;ifq1.enq(ch)thenq1.prtelseshowmessage('full');end;(3)入隊(duì)按鈕的事件處理程序：以組合框中的信80(4)出隊(duì)按鈕的事件處理程序：對(duì)q1執(zhí)行出隊(duì)操作。若返回的結(jié)果為空，則輸出相應(yīng)的通告信息，否則將返回信息顯示在組合框并重新顯示循環(huán)隊(duì)列（即對(duì)q1執(zhí)行顯示操作）。procedureTForm1.ButcdClick(Sender:TObject);varch:elemtp;beginch:=q1.dlq;ifch<>’’thenbeginComb1.text:=ch;q1.prtendelseshowmessage(’empty’);end;(4)出隊(duì)按鈕的事件處理程序：對(duì)q1執(zhí)行出814.6.8程序清單constn=12;typeelemtp=char;Tcq=classprivatefront,rear:integer;elem:array［0..n-1］ofelemtp;publicprocedureinit;functionenq(el:elemtp):boolean;functiondlq:elemtp;functiongeth:elemtp;procedureprt;end;4.6.8程序清單constn=12;82implementationvarq1:Tcq;ax,ay:array［0..n-1］ofinteger;procedureTcq.init;beginfront:=0;rear:=0end;functionTcq.enq(el:elemtp):boolean;beginif(rear+1)modn=frontthenenq:=falseelsebeginelem［rear］:=el;rear:=(rear+1)modn;enq:=trueendimplementation83end;functionTcq.dlq:elemtp;varch:elemtp;beginifrear=frontthendlq:=’’elsebeginch:=elem［front］;front:=(front+1)modn;dlq:=chendend;functionTcq.geth:elemtp;beginifrear=frontthengeth:=’’elsegeth:=elem［front］end;end;84procedureTcq.prt;varip,i,ix,iy,ix0,iy0:integer;rect1:Trect;s:string［25］;beginrect1:=rect(0,0,200,200);xhdlform.PaintBox1.Canvas.Brush.Color:=clBtnFace;xhdlform.PaintBox1.Canvas.FillRect(rect1);xhdlform.PaintBox1.Canvas.pen.Color:=clblack;xhdlform.PaintBox1.Canvas.pen.width:=1;xhdlform.PaintBox1.Canvas.font.Color:=clred;xhdlform.PaintBox1.Canvas.font.size:=15;xhdlform.PaintBox1.Canvas.Brush.Color:=clwhite;xhdlform.PaintBox1.Canvas.Ellipse(21,21,180,180);xhdlform.PaintBox1.Canvas.Brush.Color:=clBtnFace;xhdlform.PaintBox1.Canvas.Ellipse(51,51,150,150);fori:=0to11doprocedureTcq.prt;85beginix0:=100+round(50*cos(pi*i/6));iy0:=100-round(50*sin(pi*i/6));xhdlform.PaintBox1.Canvas.moveto(ix0,iy0);ix:=100+round(80*cos(pi*i/6));iy:=100-round(80*sin(pi*i/6));xhdlform.PaintBox1.Canvas.lineto(ix,iy);end;xhdlform.PaintBox1.Canvas.Brush.Color:=clred;xhdlform.PaintBox1.Canvas.pen.Color:=clred;ix0:=100+round(30*cos(pi*front/6+pi/12));iy0:=100-round(30*sin(pi*front/6+pi/12));xhdlform.PaintBox1.Canvas.Ellipse(ix0-3,iy0-3,ix0+3,iy0+3);xhdlform.PaintBox1.Canvas.Brush.Color:=clwhite;xhdlform.PaintBox1.Canvas.pen.Color:=clwhite;ix0:=100+round(40*cos(pi*rear/6+pi/12));begin86iy0:=100-round(40*sin(pi*rear/6+pi/12));xhdlform.PaintBox1.Canvas.Ellipse(ix0-3,iy0-3,ix0+3,iy0+3);xhdlform.PaintBox1.Canvas.Brush.Color:=clBtnFace;xhdlform.PaintBox1.Canvas.pen.Color:=clred;xhdlform.PaintBox1.Canvas.pen.width:=1;iffront<>rearthenbeginip:=front;whileip<>reardobeginfori:=1to9dobeginix0:=100+round(50*cos(pi*ip/6+pi*i/60));iy0:=100-round(50*sin(pi*ip/6+pi*i/60));iy0:=100-round(40*sin(pi*re87xhdlform.PaintBox1.Canvas.moveto(ix0,iy0);ix:=100+round(80*cos(pi*ip/6+pi*i/60));iy:=100-round(80*sin(pi*ip/6+pi*i/60));xhdlform.PaintBox1.Canvas.lineto(ix,iy);end;s:=elem［ip］;ix:=ax［ip］;iy:=ay［ip］;xhdlform.PaintBox1.Canvas.textout(ix,iy,s);ip:=(ip+1)modn;endendend;xhdlform.PaintB88procedureTxhdlForm.ButrdClick(Sender:TObject);varch:elemtp;beginch:=comb1.text［1］;ifq1.enq(ch)thenq1.prtelseshowmessage('full');end;procedureTxhdlForm.ButqtClick(Sender:TObject);varch:elemtp;beginch:=q1.geth;ifch<>’’thencomb1.text:=chelseshowmessage('empty');end;procedureTxhdlForm.ButcdClick(Sender:TObject);procedureTxhdlForm.ButrdClick89varch:elemtp;beginch:=q1.dlq;ifch<>’’thenbegincomb1.text:=ch;q1.prtendelseshowmessage(’empty’);end;procedureTxhdlForm.FormCreate(Sender:TObject);beginq1:=Tcq.Create;q1.init;end;varch:elemtp;90procedureTxhdlForm.FormClose(Sender:TObject;varAction:TCloseAction);beginq1.Free;end;procedureTxhdlForm.ButtcClick(Sender:TObject);beginclose;release;end;procedureTxhdlForm.PaintBox1Paint(Sender:TObject);beginq1.prtend;procedureTxhdlForm.FormClose(91begin{數(shù)組ax,ay確定循環(huán)隊(duì)列中各元素的文字標(biāo)記位置}ax［0］:=185;ay［0］:=70;ax［1］:=165;ay［1］:=30;ax［2］:=115;ay［2］:=0;ax［3］:=75;ay［3］:=0;ax［4］:=30;ay［4］:=28;ax［5］:=5;ay［5］:=70;ax［6］:=5;ay［6］:=120;ax［7］:=30;ay［7］:=155;ax［8］:=75;ay［8］:=178;ax［9］:=115;ay［9］:=178;ax［10］:=160;ay［10］:=155;ax［11］:=180;ay［11］:=115;end;end.begin{數(shù)組ax,ay確定循環(huán)隊(duì)列中各元素的文字標(biāo)92第4章隊(duì)列4.1隊(duì)列的應(yīng)用實(shí)例及概念4.2隊(duì)列的存儲(chǔ)方式4.3隊(duì)列的有關(guān)操作4.4隊(duì)列的ADT定義及類定義4.5應(yīng)用實(shí)例的實(shí)現(xiàn)4.6實(shí)習(xí)四：循環(huán)隊(duì)列演示程序第4章隊(duì)列4.1隊(duì)列的應(yīng)用實(shí)例及概念934.1隊(duì)列的應(yīng)用實(shí)例及概念隊(duì)列限定只能在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表。在表中允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端叫做隊(duì)頭（front）,向隊(duì)尾插入一個(gè)元素的操作叫做入隊(duì)（enque）操作，從隊(duì)頭取出一個(gè)元素的操作叫做出隊(duì)（dlque）操作。隨著入隊(duì)、出隊(duì)操作的執(zhí)行，隊(duì)列的隊(duì)頭、隊(duì)尾也不斷地隨之改變。由于隊(duì)列的操作具有“先進(jìn)先出”的特點(diǎn)，因此隊(duì)列又稱作先進(jìn)先出表（FIFO，即FirstInFirstOut）。4.1隊(duì)列的應(yīng)用實(shí)例及概念隊(duì)列限定只能在94圖4.1隊(duì)列結(jié)構(gòu)示意圖入隊(duì)圖4.1隊(duì)列結(jié)構(gòu)示意圖入隊(duì)95一般，一個(gè)隊(duì)列是由n個(gè)元素組成的有限序列，可記作：Q=(a1,a2,…,ai,…,an)其中，每個(gè)ai都是隊(duì)列Q的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類型，但必須屬于同一種數(shù)據(jù)元素類。從銀行排隊(duì)等待取款的實(shí)例中我們可以看到，隊(duì)列的操作與排隊(duì)、離隊(duì)的動(dòng)作非常相似，入隊(duì)操作就相當(dāng)于來了一位新的顧客在隊(duì)尾排隊(duì)等候的事件，而出隊(duì)操作就相當(dāng)于取款后離隊(duì)的事件。除了入隊(duì)(enque)、出隊(duì)(dlque)操作以外，隊(duì)列的操作通常還包括初始化（init）、求當(dāng)前元素個(gè)數(shù)（currentsize）、判是否為空隊(duì)列（empty）、清空（clear）以及取隊(duì)頭元素（getfirst）等。一般，一個(gè)隊(duì)列是由n個(gè)元素組成的有限序列，可記作：Q=(96綜上所述，隊(duì)列是一種數(shù)據(jù)類型，其數(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)度策略就是“先來先服務(wù)”，也就是要使用一個(gè)隊(duì)列來實(shí)現(xiàn)這種調(diào)度策略。同樣在做輸出時(shí)也要按請(qǐng)求輸出的先后次序排隊(duì)。作業(yè)輸出統(tǒng)一由操作系統(tǒng)中的輸出程序來執(zhí)行，每當(dāng)輸出程序傳輸完畢可以接收新的輸出任務(wù)時(shí)，隊(duì)頭的輸出作業(yè)從隊(duì)列中退出做輸出操作。凡是請(qǐng)求輸出的作業(yè)都是從隊(duì)尾進(jìn)入隊(duì)列的。綜上所述，隊(duì)列是一種數(shù)據(jù)類型，其數(shù)據(jù)元素之間97此外，在一些算法中也經(jīng)常使用隊(duì)列。例如，在圖的遍歷的非遞歸算法中，要使用一個(gè)“層次隊(duì)列”來存放已訪問的上層元素，由此來實(shí)現(xiàn)對(duì)下層元素的依次訪問。為了對(duì)隊(duì)列及其有關(guān)操作的實(shí)現(xiàn)方法有比較直觀的了解，我們可以作成一個(gè)循環(huán)隊(duì)列的演示程序。在演示操作屏幕中設(shè)置一個(gè)繪圖板顯示循環(huán)隊(duì)列的當(dāng)前狀態(tài)，即用一個(gè)環(huán)形的區(qū)域表示循環(huán)隊(duì)列并顯示其中的當(dāng)前元素，數(shù)據(jù)元素可以使用形影線來標(biāo)記；設(shè)置一個(gè)組合框用于指定當(dāng)前的入隊(duì)元素及顯示當(dāng)前的出隊(duì)元素；設(shè)置清空、入隊(duì)、出隊(duì)、退出等四個(gè)操作按鈕用于進(jìn)行演示操作（見實(shí)習(xí)四：循環(huán)隊(duì)列演示程序）。此外，在一些算法中也經(jīng)常使用隊(duì)列。例如，在984.2隊(duì)列的存儲(chǔ)方式4.2.1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖4.2鏈隊(duì)列示意圖4.2隊(duì)列的存儲(chǔ)方式4.2.1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖99