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

在鏈隊列的類定義中，其數據部分應包括一個以鏈表形式存儲的隊列，可以用一個頭指針和一個尾指針來表示它，分別取名為front與rear。由于結點的類定義為Tnode，而在ObjectPascal中，實例變量實際上就是相應類的指針變量，因此front與rear的類型可指定為Tnode型。相應的操作也與循環隊列的類定義中的操作相類似,所不同的是入隊操作是一個過程而不是函數，因此鏈隊列的入隊操作不必考慮隊列是否滿的問題。變量front與rear作為私有變量封裝在這個類中，外界的程序不能訪問這個變量，但在這個類定義之內，所有的過程或函數都能訪問它。也正因為這樣，在類中定義的過程或函數的參數中，不必指定所要操作的鏈隊列。類中所定義的操作是該類向外界提供的接口，因此被定義成公用型。類型elemtp是表示鏈隊列中的元素類型，在應用程序中，它應與一種具體的類型相對應。4.4.3鏈隊列的類定義49鏈隊列的類Tldl可定義如下：typeTnode=classprivatedata:elemtp;next:Tnode;end;Tldl=classprivatefront:Tnode;rear:Tnode;鏈隊列的類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在這個類的實現中，初始化過程init的處理過程是生成一個附加結點，由front及rear指向，并將該結點的指針域設置為nil。入隊與出隊操作的處理過程已在前節中作過討論，但在類定義中，我們已將結點的類型定義也改成了類定義(Tnode)，為此需作以下改動：(1)應將link型的變量改為Tnode型。因為在ObjectPascal中，實體變量實際上就是相應類的指針變量，例如p:link應改為p:Tnode。(2)在引用時也不必加上指針符號^，例如p^.data應改為p.data。(3)在生成時不是使用new，而是用create。例如new(p)應改為p:=Tnode.create。在這個類的實現中，初始化過程init的處理過534.5應用實例的實現圖4.11楊輝三角形及其一維排列4.5應用實例的實現圖4.11楊輝三角形及其一維排列54處理過程為：（1）設置隊列初態。初態時在隊列中存放第二行的元素和第三行的第一個元素，front指針指向第二行的第一個元素，而rear指針指向下一個將要存入的元素的位置。（2）在不是遇到行尾的1的情形下（行尾為1即在循環隊列中隊頭及隊二兩個元素均為1），可將隊頭及隊二兩個元素相加，形成一個新元素從隊尾進入，頭尾指針均移動一個位置；在遇到行尾的1的情形下，從隊尾連續的進入兩個1，而從隊頭只退出一個1。（3）重復執行過程（2），直至隊列滿。處理過程為：55圖4.12楊輝三角形的生成過程(a)第六行元素已生成的狀態；(b)第七行元素已生成的狀態圖4.12楊輝三角形的生成過程56在使用Delphi實現該算法時，先要建立一個循環隊列的類Tcq，隊列的元素類型為整型，該類向外界提供入隊enq、出隊dlq、取隊頭getf、取隊二gets、判隊滿full及顯示prt等操作。由于前二行比較特殊，算法從第三行起開始處理，即初態時在隊列中存放第二行的元素和第三行的第一個元素。隊列實體q1的生成及初態的設置是在窗體建立事件中進行的：procedureTyhsjForm.FormCreate(Sender:TObject);beginq1:=Tcq.Create;q1.init;q1.enq(1);q1.enq(2);q1.enq(1);q1.enq(1);end;在使用Delphi實現該算法時，先要建立一個57下述程序的功能是由第i-1行的兩個相鄰的元素，生成第i行的一個相應的元素。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行的兩個相鄰的元素58上述程序中的a:=q1.dlq;b:=q1.getf。因為運算中要使用兩個元素，而隊列中的頭指針只要移動一個位置，所以一個執行dlq操作，而另一個執行getf操作。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整個程序的清單如下：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;整個程序的清單如下：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實習四：循環隊列演示程序4.6.1問題說明循環隊列是隊列中的頭尾兩個存儲單元在邏輯上相鄰的隊列。入隊時指定的元素從隊尾進入，尾指針加1并對長度取模；出隊時從隊頭取出一個元素，頭指針加1并對長度取模。只有在頭尾指針相遇時才能確定為隊列存儲空間滿。因此，其存儲空間的使用效率比一般的順序隊列要高。編制一個具有Windows圖形用戶界面的教學演示程序，模擬循環隊列的入隊、出隊等操作的執行過程。4.6實習四：循環隊列演示程序4.6.1問題說明684.6.2界面外觀及功能要求圖4.13循環隊列演示程序4.6.2界面外觀及功能要求圖4.13循環隊列演示程694.6.3實現要點循環隊列實現的要點：(1)循環隊列的數據結構及操作儲存區：elem［0..n-1］隊頭指針：front隊尾指針：rear空隊列：front=rear滿隊列：(rear+1)modn=front入隊操作：elem［rear］:=el;rear:=(rear+1)modn出隊操作：ch:=elem［front］;front:=(front+1)modn;返回ch;4.6.3實現要點70(2)繪圖處理：用紅色的圓點表示front指針，用白色的圓點表示rear指針，用較密的半徑線表示已入隊的元素。設環形的圓心坐標為（100，100），位置半徑為30，指針指向第i個緩沖區，圓點的半徑為3，則圓點可以用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同樣，環形的內半徑分別為50、80，則標記第i個緩沖區已存入元素的程序如下：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;同樣，環形的內半徑分別為50、80，724.6.4類定義將循環隊列定義成一個類，其數據由n個元素的隊列存儲區域elem及隊列頭front、指針隊列尾指針rear組成。相應的操作為初始化(procedureinit)，入隊列(functionenq(el:elemtp):boolean)，出隊列(functiondlq:elemtp)及隊列顯示(procedureprt)等。在本演示程序中，元素類型elemtp為字符類型char。循環隊列類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類的實現(1)初始化過程(init)：將front,rear指針均設置為0。(2)入隊列函數(enq(el:elemtp):boolean)：將數據值為el的元素從隊末插入到隊列中。若隊列為滿，則返回false,否則插入后返回true。(3)出隊列函數(dlq:elemtp)：可取出并返回隊頭元素。若隊列為空，則返回空元素。4.6.5類的實現75(4)隊列顯示過程(prt)：顯示當前的循環隊列。其處理步驟如下：①繪圖板清空。②畫兩個同心圓，即以環形區域表示循環隊列。③在環形區域中畫元素分割線。④分別畫出front指針與rear指針。⑤將循環隊列中的當前元素在環形區域中表示出來。(4)隊列顯示過程(prt)：顯示當前的764.6.6組件設置PaintBox1：繪圖板，用于顯示一個環形區域表示循環隊列的當前狀態。Comb1：組合框，用于指定入隊元素或顯示出隊元素。ButRd,Cd,Qt,Tc：分別為入隊、出隊、取頭及退出操作按鈕。4.6.6組件設置774.6.7界面功能的實現我們已將循環隊列定義成一個類，在實現界面功能時只需生成一個該類的實體并對其施行相應的操作即可。各事件處理程序如下：(1)窗體生成事件處理程序：在窗體生成事件處理程序中生成一個Tcq類的實體q1，并執行初始化。procedureTForm1.FormActivate(Sender:TObject);beginq1:=Tcq.Create;q1.init;end;4.6.7界面功能的實現78(2)窗體關閉事件處理程序：在窗體關閉事件處理程序中釋放已生成的實體q1，并關閉窗體釋放空間。procedureTForm1.FormClose(Sender:TObject;varAction:TCloseAction);beginq1.Free;close;release;end;(2)窗體關閉事件處理程序：79(3)入隊按鈕的事件處理程序：以組合框中的信息為參數對q1執行入隊操作。若成功，則重新顯示循環隊列（即對q1執行顯示操作），否則輸出相應的通告信息。procedureTForm1.ButrdClick(Sender:TObject);varch:elemtp;beginch:=comb1.text［1］;ifq1.enq(ch)thenq1.prtelseshowmessage('full');end;(3)入隊按鈕的事件處理程序：以組合框中的信80(4)出隊按鈕的事件處理程序：對q1執行出隊操作。若返回的結果為空，則輸出相應的通告信息，否則將返回信息顯示在組合框并重新顯示循環隊列（即對q1執行顯示操作）。procedureTForm1.ButcdClick(Sender:TObject);varch:elemtp;beginch:=q1.dlq;ifch<>’’thenbeginComb1.text:=ch;q1.prtendelseshowmessage(’empty’);end;(4)出隊按鈕的事件處理程序：對q1執行出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{數組ax,ay確定循環隊列中各元素的文字標記位置}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{數組ax,ay確定循環隊列中各元素的文字標92第4章隊列4.1隊列的應用實例及概念4.2隊列的存儲方式4.3隊列的有關操作4.4隊列的ADT定義及類定義4.5應用實例的實現4.6實習四：循環隊列演示程序第4章隊列4.1隊列的應用實例及概念934.1隊列的應用實例及概念隊列限定只能在表的一端進行插入，而在表的另一端進行刪除的線性表。在表中允許插入的一端叫做隊尾（rear），允許刪除的一端叫做隊頭（front）,向隊尾插入一個元素的操作叫做入隊（enque）操作，從隊頭取出一個元素的操作叫做出隊（dlque）操作。隨著入隊、出隊操作的執行，隊列的隊頭、隊尾也不斷地隨之改變。由于隊列的操作具有“先進先出”的特點，因此隊列又稱作先進先出表（FIFO，即FirstInFirstOut）。4.1隊列的應用實例及概念隊列限定只能在94圖4.1隊列結構示意圖入隊圖4.1隊列結構示意圖入隊95一般，一個隊列是由n個元素組成的有限序列，可記作：Q=(a1,a2,…,ai,…,an)其中，每個ai都是隊列Q的數據元素，數據元素可以是各種類型，但必須屬于同一種數據元素類。從銀行排隊等待取款的實例中我們可以看到，隊列的操作與排隊、離隊的動作非常相似，入隊操作就相當于來了一位新的顧客在隊尾排隊等候的事件，而出隊操作就相當于取款后離隊的事件。除了入隊(enque)、出隊(dlque)操作以外，隊列的操作通常還包括初始化（init）、求當前元素個數（currentsize）、判是否為空隊列（empty）、清空（clear）以及取隊頭元素（getfirst）等。一般，一個隊列是由n個元素組成的有限序列，可記作：Q=(96綜上所述，隊列是一種數據類型，其數據元素之間呈線性關系，其操作的特點是“先進先出”，主要操作有入隊、出隊和取隊頭元素等。隊列在程序設計中也經常使用。一個最典型的例子就是操作系統中的作業排隊。在允許多道程序運行的計算機系統中，作業輸入后通常處于后備狀態，由操作系統中的作業調度程序將作業調入執行。作業調度程序可以采用不同的調度策略，其中最簡單的調度策略就是“先來先服務”，也就是要使用一個隊列來實現這種調度策略。同樣在做輸出時也要按請求輸出的先后次序排隊。作業輸出統一由操作系統中的輸出程序來執行，每當輸出程序傳輸完畢可以接收新的輸出任務時，隊頭的輸出作業從隊列中退出做輸出操作。凡是請求輸出的作業都是從隊尾進入隊列的。綜上所述，隊列是一種數據類型，其數據元素之間97此外，在一些算法中也經常使用隊列。例如，在圖的遍歷的非遞歸算法中，要使用一個“層次隊列”來存放已訪問的上層元素，由此來實現對下層元素的依次訪問。為了對隊列及其有關操作的實現方法有比較直觀的了解，我們可以作成一個循環隊列的演示程序。在演示操作屏幕中設置一個繪圖板顯示循環隊列的當前狀態，即用一個環形的區域表示循環隊列并顯示其中的當前元素，數據元素可以使用形影線來標記；設置一個組合框用于指定當前的入隊元素及顯示當前的出隊元素；設置清空、入隊、出隊、退出等四個操作按鈕用于進行演示操作（見實習四：循環隊列演示程序）。此外，在一些算法中也經常使用隊列。例如，在984.2隊列的存儲方式4.2.1隊列的鏈式存儲結構圖4.2鏈隊列示意圖4.2隊列的存儲方式4.2.1隊列的鏈式存儲結構圖99