数据结构-队列课件

第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