1、第4章 队 列 第第4 4章章 队队 列列 4.1 队列的应用实例及概念队列的应用实例及概念 4.2 队列的存储方式队列的存储方式4.3 队列的有关操作队列的有关操作 4.4 队列的队列的ADT定义及类定义定义及类定义 4.5 应用实例的实现应用实例的实现 4.6 实习四：实习四：循环队列演示程序循环队列演示程序第4章 队 列 4.1 队列的应用实例及概念队列的应用实例及概念 队列限定只能在表的一端进行插入，而在表的另一端进行删除的线性表。在表中允许插入的一端叫做队尾（rear），允许删除的一端叫做队头（front）,向队尾插入一个元素的操作叫做入队（enque）操作，从队头取出一个元素的操作
2、叫做出队（dlque）操作。随着入队、出队操作的执行，队列的队头、队尾也不断地随之改变。由于队列的操作具有“先进先出”的特点，因此队列又称作先进先出表（FIFO，即First In First Out）。第4章 队 列 图 4.1 队列结构示意图 入队入队第4章 队 列 一般，一个队列是由n个元素组成的有限序列，可记作：Q=(a1,a2,ai,an)其中，每个ai都是队列Q的数据元素，数据元素可以是各种类型，但必须属于同一种数据元素类。从银行排队等待取款的实例中我们可以看到，队列的操作与排队、离队的动作非常相似，入队操作就相当于来了一位新的顾客在队尾排队等候的事件，而出队操作就相当于取款后离队
3、的事件。除了入队(enque)、出队(dlque)操作以外，队列的操作通常还包括初始化（init）、求当前元素个数（currentsize）、判是否为空队列（empty）、清空（clear）以及取队头元素（getfirst）等。第4章 队 列 综上所述，队列是一种数据类型，其数据元素之间呈线性关系，其操作的特点是“先进先出”，主要操作有入队、出队和取队头元素等。队列在程序设计中也经常使用。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，作业输入后通常处于后备状态，由操作系统中的作业调度程序将作业调入执行。作业调度程序可以采用不同的调度策略，其中最简单的调度策略就是“
4、先来先服务”，也就是要使用一个队列来实现这种调度策略。同样在做输出时也要按请求输出的先后次序排队。作业输出统一由操作系统中的输出程序来执行，每当输出程序传输完毕可以接收新的输出任务时，队头的输出作业从队列中退出做输出操作。凡是请求输出的作业都是从队尾进入队列的。第4章 队 列 此外，在一些算法中也经常使用队列。例如，在图的遍历的非递归算法中，要使用一个“层次队列”来存放已访问的上层元素，由此来实现对下层元素的依次访问。为了对队列及其有关操作的实现方法有比较直观的了解，我们可以作成一个循环队列的演示程序。在演示操作屏幕中设置一个绘图板显示循环队列的当前状态，即用一个环形的区域表示循环队列并显示其
5、中的当前元素，数据元素可以使用形影线来标记；设置一个组合框用于指定当前的入队元素及显示当前的出队元素；设置清空、入队、出队、退出等四个操作按钮用于进行演示操作（见实习四：循环队列演示程序）。第4章 队 列 4.2 队列的存储方式队列的存储方式 4.2.1 队列的链式存储结构队列的链式存储结构 图 4.2 链队列示意图 队头队尾frontrear第4章 队 列 图 4.3 链队列指针变化状况(a)空队列；(b)a入队列；(c)b入队列；(d)a出队列 frontrear(a)frontreara(b)frontreara(c)bfrontreara(d)b第4章 队 列 图 4.4 链队列类型结
6、构 datanext结点类型rearfront链队列类型第4章 队 列 假设结点类型名为nodetp，结点指针类型名为link，结点类型中数据域名为data，指针域名为next，数据元素的类型为elemtp,链队列的头指针和尾指针分别为front与rear，则链队列类型lquetp可定义如下：type link=nodetp nodetp=record data:elemtp;next:link;end;lquetp=record front:link;rear:link;end;第4章 队 列 在程序中使用的链队列可以用一个lquetp型变量来表示，例如:var lq1:lquetp;当lq
7、1.front=lq1.rear时，这个队列就成为空队列，否则，lq1.front.next指向队头结点，而lq1.rear指向队尾结点。和链栈的情形相同，一般不会出现队列满的情形，除非整个可用空间都被占满，new(p)都无法执行的情形下才会发生上溢。同样空队列的状态在程序设计中也被用作实现控制转移的条件。第4章 队 列 4.2.2 队列的顺序存储结构队列的顺序存储结构 图 4.5 顺序队列的存储结构 J5J4maxrearfrontelem1.max第4章 队 列 图 4.6 顺序队列中头尾指针的变化(a)空队列；(b)a、b、c、d 依次入队；(c)a、b、c 依次出队；(d)e、f入队(
8、a)frontdcba(b)rearrear1023456front1023456d(c)rear1023456fronted(d)rearf1023456front第4章 队 列 对一般的顺序队列，我们可以用front=rear作为判别队列是否为空的条件；用rearmax作为判别队列是否为满的条件。当队列非空时，可执行如下的出队操作：front:=front+1;data:=elemfront;当队列非满时，可执行如下的入队操作：rear:=rear+1;elemrear:=data;第4章 队 列 在这里值得考虑的是：当rearmax时，队列是否真正为满？假设当前队列是处在图4.6(d)的
9、状态，即max=6,rear=6,front=3,显然此时不能再做入队列的操作，因为rearmax，但队列中实际上并未存满元素，这种现象称为假溢出。当然，在发生假溢出时可以将全部元素向下移动直至头指针为0，但这样处理效率不高。一个比较巧妙的办法是将队列设想成首尾相接的环，一端放满时再从另一端存入，只要尾指针不与头指针相遇，该队列即可使用下去。这就是我们所讲的循环队列。第4章 队 列 图 4.7 循环队列示意图 01235476rearfront第4章 队 列 图 4.8 循环队列的头尾指针(a)空队列;(b)队列中有一个元素；(c)队列满 01235476frontrear(a)0123547
10、6front(b)rear01235476front(b)rear第4章 队 列 另外对于循环队列，无论是头指针还是尾指针，在对其进行加1处理时，都要考虑对结果取模。综上所述：我们可以用front=rear作为判别队列是否为空的条件；用(rear+1)mod max=front作为判别队列是否为满的条件。当队列非空时，可执行如下的出队操作：front:=(front+1)mod max;data:=elemfront;当队列非满时，可执行如下的入队操作：rear:=(rear+1)mod max;elemrear:=data;第4章 队 列 如前所述，在队列的顺序存储结构中，应该包括一个存储数
11、据元素的一维数组，取其名为elem，其长度可取为一个适当的最大值max，另外还应包括两个位置指示器front和rear，它们分别指向队头和队尾的位置，使用Pascal语言，我们可以定义以下的记录（结构）类型来表示顺序队列或循环队列，假设其类型名用squetp 表示：const max队列中允许存放元素个数的最大值；type squetp=record elem:array1.max of elemtp；front,rear:0.max end；第4章 队 列 在定义了顺序队列的类型squetp之后，我们就可以定义属于这种类型的队列，例如：var q1:squetp；此后可在程序中引用顺序队列q
12、1的相应成分，例如，q1.elemq1.rear表示队尾元素等。第4章 队 列 4.3 队列的有关操作队列的有关操作 4.3.1 循环队列的操作实现循环队列的操作实现 1.入队操作入队操作 循环队列的入队操作可表示为：function enque(var cq:squetp el:elemtp):boolean;其中，参数cq表示指定的循环队列，其类型为squetp；参数el表示入队列的元素，其类型为元素类型elemtp。该操作返回一个布尔型的函数值，表示入队操作是否执行成功。操作的功能为在循环队列cq中插入元素el。若循环队列cq不满，则插入el新的队尾元素，并返回函数值true，否则队列的
13、状态不变且返回函数值false。第4章 队 列 处理过程为判是否队列满。若队列满，则返回false，否则，队列尾指针加1，将el从队尾插入队列并返回true。程序如下：function enque(var cq:squetp,el:elemtp):boolean;begin if(cq.rear+1)mod max=cq.front then result:=false else begin cq.rear:=(cq.rear+1)mod max;cq.elemcq.rear:=el;result:=true endend;第4章 队 列 2.出队操作出队操作 循环队列的出队操作可表示为：fu
14、nction dlque(var cq:squetp):elemtp;其中，参数cq表示指定的循环队列，其类型为squetp。该操作是一个函数，其返回值表示从队列中取出的队头元素。操作的功能为：若循环队列cq非空，则从cq中取出队头元素并返回该元素，否则返回空元素NULL。处理过程为判队列是否为空队列。若队列为空队列，则返回NULL，否则，队列头指针加1并返回队头元素。第4章 队 列 程序如下：function dlque(var cq:squetp):elemtp;begin if cq.frontcq.rear then result:=NULL else begin cq.front:=
15、(cq.front+1)mod max;result:=cq.elemcq.front endend;第4章 队 列 3.其他操作其他操作初始化操作：设置循环队列cq为空的循环队列。procedure init(var cq:squetp);begin cq.front:=0;cq.rear:=0;end;第4章 队 列 求长度操作：返回循环队列cq中所含元素的个数。function size(cq:squetp):integer;begin size:=(cq.rear-cq.front+max)mod max;end;第4章 队 列 判空队列操作：若队列为空，则返回true，否则返回fal
16、se。function empty(cq:squetp):boolean;begin if cq.front=cq.rear then empty:=true else empty:=false;end;第4章 队 列 判队列满操作：若队列满，则返回true，否则返回false。function full(cq:squetp):boolean;begin if(cq.rear+1)mod max=cq.front then full:=true else full:=falseend;第4章 队 列 取队头操作：若队列非空，则返回队头元素，否则返回NULL。function getf(cq:s
17、quetp):elemtp;begin if cq.frontcq.rear then result:=NULL else result:=cq.elem(cq.front+1)mod maxend;第4章 队 列 4.3.2 链队列的操作实现链队列的操作实现 1.入队列操作入队列操作 链队列的入队操作可表示为 procedure enque(var q:lquetp el:elemtp);其中，参数q表示指定的链队列，其类型为lquetp；参数el表示入队列的元素，其类型为元素类型elemtp。操作的功能为在链队列q中插入新的队尾元素el。第4章 队 列 图 4.9 链队列入队操作示意图 f
18、rontelrear第4章 队 列 处理过程为（见图4.9）：（1）生成一个元素值为el的新结点：（2）将该结点从队尾插入队列。程序如下：procedure enque(var q:lquetp,el:elemtp);var p:link;begin new(p);p.data:=el;pnext:=NIL;q.rearnext:=p;q.rear:=p;end;第4章 队 列 2 出队列操作出队列操作 链队列的出队操作可表示为 function dlque(var q:lquetp):elemtp;其中，参数q表示指定的链队列，其类型为lquetp。该操作是一个函数，其返回值表示从队列中取出
19、的队头元素。操作的功能为：若链队列q非空，则从q中取出队头元素并返回该元素，否则返回空元素NULL。第4章 队 列 图 4.10 链队列出队操作示意图 frontrear(a)front(b)frontrearrears第4章 队 列 若链队列q为空，则返回空元素NULL，否则：（1）删除队头元素，即使头结点中的指针指向队头的下一个结点。（2）若删除后成为空队列，则使头尾指针值相同。（3）取删除结点的值作为返回值，并释放该结点。第4章 队 列 程序如下：function dlque(var q:lquetp):elemtp;var s:link;el:elemtp;begin if q.fro
20、ntq.rear then result:=NULL else begin s:=q.frontnext;q.frontnext:=s.next;if s.next=nil then q.rear:=q.front;el:=s.data;dispose(s);result:=el endend;第4章 队 列 3.其他操作其他操作初始化操作：设置一个空的链队列，由q表示之。处理过程：生成一个头结点，并使q的头尾指针均指向它。procedure init(var q:lquetp);begin new(q.front);q.rear:=q.front;q.front.next:=nil;end;
21、第4章 队 列 求长度操作：返回链队列q中所含元素的个数。function size(q:lquetp):integer;var p:link;i:integer;begin p:=q.front.next;i:=0;while p nil do begin i:=i+1;p:=p.next end size:=i;end;第4章 队 列 判空队列操作：若队列为空，则返回true，否则返回false。function empty(q:lquetp):boolean;begin if q.front=q.rear then empty:=true else empty:=false;end;第4
22、章 队 列 取队头操作：若队列非空，则返回队头元素，否则返回NULL。function getf(q:lquetp):elemtp;begin if q.frontq.rear then result:=NULL else result:=q.front.next.data;end;第4章 队 列 4.4 队列的队列的ADT定义及类定义定义及类定义 4.4.1 队列的队列的ADT定义定义 与线性表、栈的情形类似，我们可以定义队列的抽象数据类型。一种数据类型的ADT定义由数据元素、结构及操作三部分组成。以下是队列的ADT定义：元素：可以是各种类型的数据，但必须同属于一个数据元素类；结构：队列中的
23、n个元素呈线性关系；第4章 队 列 (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为新的队尾元素。操作：对队列可执行以下的基本操作：第4章 队 列 (6)dlque(q)：出队列函数。若队列q非空，则删除队头元素并返回该元素，
24、且其后继为新的队头元素，否则返回函数值为空元素NULL。(7)getf(q)：取队头元素函数。若队列q非空，则返回函数值为队头元素，否则返回函数值为空元素NULL。第4章 队 列 4.4.2 循环队列的类定义循环队列的类定义 在循环队列的类定义中，其数据部分应包括存储数据元素的一个一维数组，取名为elem，另外还应包括表示队头、队尾的整型变量，分别取名为front及rear。相应的操作为初始化(init)，显示(prnt)，入队列(enque)，出队列(dlque)等等。变量elem、front及rear为类中的内部数据，要封装在这个类中，因此为私有变量，外界的程序不能访问这个变量，但在这个类
25、定义之内，所有的过程或函数都能访问它，也正因为这样，在类中定义的过程或函数的参数中，不必指定所要操作的循环队列。类中所定义的操作是该类向外界提供的接口，因此被定义成公用型。类型elemtp是表示循环队列中的元素类型，在应用程序中，它再与另一种具体的类型相对应。例如，在演示程序中，数据元素的类型elemtp与字符类型相对应。第4章 队 列 循环队列的类Txhdl可定义如下：const max队列中允许存放元素个数的最大值；type elemtp=char;Txhdl=class private elem:array1.max of elemtp；front,rear:0.max public p
26、rocedure init;procedure prnt;第4章 队 列 function enque(el:elemtp):boolean;function dlque:elemtp;function getf:elemtp;function empty:boolean;function full:boolean;function size:integer;end;implementationprocedure Txhdl.init;begin front:=0;rear:=0;end;第4章 队 列 procedure Txhdl.prnt;var ip:integer;begin if
27、frontrear then begin ip:=front;while ip rear do begin 显示elemip;ip:=(ip+1)mod max;end endend 第4章 队 列 与顺序表、顺序栈的情形相类似，对上述类定义有以下几点需作说明：(1)上述类定义中数组采用了静态分配的方式，但为了实现数据封装，最好采用动态分配，同时将数组的长度max定义为类中私有量。(2)在类定义时数据元素的类型实际上是不确定的，所以最好是采用“模板”方式。即在类定义时指定参数化数据类型，而在实例生成时才指定对应的元素类型。(3)初始化过程init的处理过程是将队列的头尾指针设置为 0，即fro
28、nt:=0;rear:=0。入队、出队操作的处理过程已在前节中作过讨论，稍有不同的是在类定义中，可直接引用elem、front、rear而无需加上“cq.”。(4)对于显示程序prnt，其功能是显示循环队列中的当前元素。第4章 队 列 4.4.3 链队列的类定义链队列的类定义 在链队列的类定义中，其数据部分应包括一个以链表形式存储的队列，可以用一个头指针和一个尾指针来表示它，分别取名为front与rear。由于结点的类定义为Tnode，而在Object Pascal中，实例变量实际上就是相应类的指针变量，因此front与rear的类型可指定为Tnode型。相应的操作也与循环队列的类定义中的操作
29、相类似,所不同的是入队操作是一个过程而不是函数，因此链队列的入队操作不必考虑队列是否满的问题。变量front与rear作为私有变量封装在这个类中，外界的程序不能访问这个变量，但在这个类定义之内，所有的过程或函数都能访问它。也正因为这样，在类中定义的过程或函数的参数中，不必指定所要操作的链队列。类中所定义的操作是该类向外界提供的接口，因此被定义成公用型。类型elemtp是表示链队列中的元素类型，在应用程序中，它应与一种具体的类型相对应。第4章 队 列 链队列的类Tldl可定义如下：type Tnode=class private data:elemtp;next:Tnode;end;Tldl=c
30、lass private front:Tnode;rear:Tnode;第4章 队 列 public procedure init;procedure prnt;procedure enque(el:elemtp)function dlque:elemtp;function getf:elemtp;function empty:boolean;function full:boolean;function size:integer;end;implementationprocedure Tldl.init;begin front:=Tnode.create;rear:=front;第4章 队 列
31、 front.next:=nil;end;procedure Tldl.prnt;var p:Tnode;begin p:=front.next;while p nil do begin 显示p.data;p:=p.next;end;end;第4章 队 列 在这个类的实现中，初始化过程init的处理过程是生成一个附加结点，由front及rear指向，并将该结点的指针域设置为nil。入队与出队操作的处理过程已在前节中作过讨论，但在类定义中，我们已将结点的类型定义也改成了类定义(Tnode)，为此需作以下改动：(1)应将link型的变量改为Tnode型。因为在Object Pascal中，实体变量
32、实际上就是相应类的指针变量，例如 p:link应改为p:Tnode。(2)在引用时也不必加上指针符号，例如 p.data应改为p.data。(3)在生成时不是使用new，而是用create。例如 new(p)应改为p:=Tnode.create。第4章 队 列 4.5 应用实例的实现应用实例的实现 图 4.11 杨辉三角形及其一维排列 111211331146411111121133114641 第4章 队 列 处理过程为：（1）设置队列初态。初态时在队列中存放第二行的元素和第三行的第一个元素，front指针指向第二行的第一个元素，而rear指针指向下一个将要存入的元素的位置。（2）在不是遇到
33、行尾的 1 的情形下（行尾为 1 即在循环队列中队头及队二两个元素均为 1），可将队头及队二两个元素相加，形成一个新元素从队尾进入，头尾指针均移动一个位置；在遇到行尾的 1 的情形下，从队尾连续的进入两个1，而从队头只退出一个 1。（3）重复执行过程（2），直至队列满。第4章 队 列 图 4.12 杨辉三角形的生成过程(a)第六行元素已生成的状态；(b)第七行元素已生成的状态 frontrear(a)11510511frontrear(b)1151051161515 611第4章 队 列 在使用Delphi实现该算法时，先要建立一个循环队列的类Tcq，队列的元素类型为整型，该类向外界提供入队e
34、nq、出队dlq、取队头getf、取队二gets、判队满full及显示prt等操作。由于前二行比较特殊，算法从第三行起开始处理，即初态时在队列中存放第二行的元素和第三行的第一个元素。队列实体q1 的生成及初态的设置是在窗体建立事件中进行的：procedure TyhsjForm.FormCreate(Sender:TObject);begin q1:=Tcq.Create;q1.init;q1.enq(1);q1.enq(2);q1.enq(1);q1.enq(1);end;第4章 队 列 下述程序的功能是由第i-1 行的两个相邻的元素，生成第i行的一个相应的元素。var a,b:intege
35、r;begin if not q1.full then begin if(q1.getf=1)and(q1.gets=1)then begin q1.dlq;q1.enq(1);q1.enq(1);end else begin a:=q1.dlq;b:=q1.getf;q1.enq(a+b);end;q1.prt;endend;第4章 队 列 上述程序中的a:=q1.dlq;b:=q1.getf。因为运算中要使用两个元素，而队列中的头指针只要移动一个位置，所以一个执行dlq操作，而另一个执行getf操作。if frontrear then begin ip:=front;while ip re
36、ar do begin s:=inttostr(elemip);yhsjform.PaintBox1.Canvas.textout(ip*30,10,s);ip:=(ip+1)mod max;end end 第4章 队 列 整个程序的清单如下：const n=12;type elemtp=integer;Tcq=class private front,rear:integer;elem:array 0.n-1 of elemtp;public procedure init;function full:boolean;function enq(el:elemtp):boolean;functio
37、n dlq:elemtp;function getf:elemtp;function gets:elemtp;procedure prt;end;第4章 队 列 implementationvar q1:Tcq;procedure Tcq.init;begin front:=0;rear:=0end;function Tcq.full:boolean;begin if(rear+1)mod n=front then full:=true else full:=falseend;第4章 队 列 function Tcq.enq(el:elemtp):boolean;begin if(rear+1
38、)mod n=front then enq:=false else begin elemrear:=el;rear:=(rear+1)mod n;enq:=true endend;function Tcq.dlq:elemtp;var el:elemtp;begin if rear=front then dlq:=0 else begin el:=elemfront;front:=(front+1)mod n;dlq:=el end 第4章 队 列 end;function Tcq.getf:elemtp;begin if rear=front then getf:=0 else getf:=
39、elemfrontend;function Tcq.gets:elemtp;begin if(rear=front)or(front+1)mod n=rear)then gets:=0 else gets:=elem(front+1)mod nend;第4章 队 列 procedure Tcq.prt;var ip,i,ix,iy,ix0,iy0:integer;rect1:Trect;s:string25;begin rect1:=rect(0,0,400,100);yhsjform.PaintBox1.Canvas.Brush.Color:=clBtnFace;yhsjform.Paint
40、Box1.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;if frontrear then begin ip:=front;第4章 队 列 while ip rear do begin s:=inttostr(elemip);yhsjform.PaintBox1.
41、Canvas.textout(ip*30,10,s);ip:=(ip+1)mod n;end endend;procedure TyhsjForm.ButxygClick(Sender:TObject);var a,b:integer;begin if not q1.full then begin if(q1.getf=1)and(q1.gets=1)then 第4章 队 列 begin q1.dlq;q1.enq(1);q1.enq(1);end else begin a:=q1.dlq;b:=q1.getf;q1.enq(a+b);end;q1.prt;endend;procedure T
42、yhsjForm.FormCreate(Sender:TObject);begin q1:=Tcq.Create;q1.init;q1.enq(1);q1.enq(2);q1.enq(1);q1.enq(1);end;第4章 队 列 procedure TyhsjForm.FormClose(Sender:TObject;var Action:TCloseAction);begin q1.Free;end;procedure TyhsjForm.ButtcClick(Sender:TObject);begin close;release;end;procedure TyhsjForm.Pain
43、tBox1Paint(Sender:TObject);begin q1.prtend;第4章 队 列 4.6 实习四：循环队列演示程序实习四：循环队列演示程序 4.6.1 问题说明问题说明 循环队列是队列中的头尾两个存储单元在逻辑上相邻的队列。入队时指定的元素从队尾进入，尾指针加 1 并对长度取模；出队时从队头取出一个元素，头指针加 1 并对长度取模。只有在头尾指针相遇时才能确定为队列存储空间满。因此，其存储空间的使用效率比一般的顺序队列要高。编制一个具有Windows图形用户界面的教学演示程序，模拟循环队列的入队、出队等操作的执行过程。第4章 队 列 4.6.2 界面外观及功能要求界面外观及
44、功能要求 图 4.13 循环队列演示程序 第4章 队 列 4.6.3 实现要点实现要点循环队列实现的要点：(1)循环队列的数据结构及操作储存区：elem 0.n-1队头指针：front队尾指针：rear空队列：front=rear满队列：(rear+1)mod n=front入队操作：elemrear:=el;rear:=(rear+1)mod n出队操作：ch:=elemfront;front:=(front+1)mod n;返回ch;第4章 队 列 (2)绘图处理：用红色的圆点表示 front 指针，用白色的圆点表示 rear 指针，用较密的半径线表示已入队的元素。设环形的圆心坐标为（10
45、0，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);第4章 队 列 同样，环形的内半径分别为 50、80，则标记第i 个缓冲区已存入元素的程序如下：for i:=1 to 9 do begin ix0:=100+round(50*cos(pi*ip/6+pi*i/60);iy0:=100-round(50*sin(
46、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;第4章 队 列 4.6.4 类定义类定义 将循环队列定义成一个类，其数据由n个元素的队列存储区域elem及队列头front、指针队列尾指针rear组成。相应的操作为初始化(procedure init)，入队列(function enq(el:elemtp):boolean)，出队列(function dlq:elemtp)及队列显示(proc
47、edure prt)等。在本演示程序中，元素类型elemtp为字符类型char。循环队列类Tcq的定义如下：第4章 队 列 elemtp=char;Tcq=class private front,rear:integer;elem:array 0.n-1 of elemtp;public procedure init;function enq(el:elemtp):boolean;function dlq:elemtp;procedure prt;end;第4章 队 列 4.6.5 类的实现类的实现 (1)初始化过程(init)：将front,rear指针均设置为 0。(2)入队列函数(enq
48、(el:elemtp):boolean)：将数据值为el的元素从队末插入到队列中。若队列为满，则返回false,否则插入后返回true。(3)出队列函数(dlq:elemtp)：可取出并返回队头元素。若队列为空，则返回空元素。第4章 队 列 (4)队列显示过程(prt)：显示当前的循环队列。其处理步骤如下：绘图板清空。画两个同心圆，即以环形区域表示循环队列。在环形区域中画元素分割线。分别画出front指针与rear指针。将循环队列中的当前元素在环形区域中表示出来。第4章 队 列 4.6.6 组件设置组件设置 PaintBox1：绘图板，用于显示一个环形区域表示循环队列的当前状态。Comb1：组
49、合框，用于指定入队元素或显示出队元素。ButRd,Cd,Qt,Tc：分别为入队、出队、取头及退出操作按钮。第4章 队 列 4.6.7 界面功能的实现界面功能的实现 我们已将循环队列定义成一个类，在实现界面功能时只需生成一个该类的实体并对其施行相应的操作即可。各事件处理程序如下：(1)窗体生成事件处理程序：在窗体生成事件处理程序中生成一个Tcq类的实体q1，并执行初始化。procedure TForm1.FormActivate(Sender:TObject);begin q1:=Tcq.Create;q1.init;end;第4章 队 列 (2)窗体关闭事件处理程序：在窗体关闭事件处理程序中释
50、放已生成的实体q1，并关闭窗体释放空间。procedure TForm1.FormClose(Sender:TObject;var Action:TCloseAction);begin q1.Free;close;release;end;第4章 队 列 (3)入队按钮的事件处理程序：以组合框中的信息为参数对q1 执行入队操作。若成功，则重新显示循环队列（即对q1 执行显示操作），否则输出相应的通告信息。procedure TForm1.ButrdClick(Sender:TObject);var ch:elemtp;begin ch:=comb1.text1;if q1.enq(ch)then
