第四篇数据结构队列和串.docVIP

§9.3 队列 队列是不同于栈的另一种线性表。在日常生活中，无论是购物、订票或候车都有可能要排队。排队所遵循的原则是“先来先服务”，后来者总是加到队尾，排头者总是先离开队伍。队列就是从日常生活中的排队现象抽象出来的。 一、队列的定义 所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0（如下图）。 显然，在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。与栈相似，队列的顺序存储空间可以用一维数组q[1‥m]模拟： 我们按照如下方式定义队列： Const m=队列元素的上限； Type equeue=array[1…m] of qtype；{队列的类型定义} Var q：equeue； {队列} r，f：integer； {队尾指针和队首指针} 二、队列的基本运算 队列的运算主要有两种：入队（aDD）和出队（DEL） 1、过程ADD(q，x，r)q的尾端插入元素x procedure ADD(var q： equeue； x：qtype； var r：integer)； begin if r=m then writeln (’overflow’) {上溢} else begin {后移队尾指针并插入元素x} r←r+1； q[r]x； end；{else} end；{ADD} 2、过程DEL(q，y，f，rq队列的队首元素y procedure DEL(var q：equeue； var y：qtype； var f：integer)； begin if f=r then writeln (’under flow’) else begin {后移队首指针并取出队首元素} f←f+1； yq[f]； end；{else} end；{DEL}r=m）而不能再加入元素时，存储空间的前部却有一片存储区无端浪费，这种现象称为“假溢出”。下图给出了一个“假溢出”的示例： 三、循环队列 为了解决“假溢出”的问题，我们不妨作这样的设想：在队列中，当存储空间的最后一个位置已被使用而要进行入队运算时，只要存储空间第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的队列结构后，可以有效地解决假溢出的问题，避免数据元素的移动，这就是所谓的循环队列。下图给出了循环队列的结构。 循环队列将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，循环队列的存取方法亦为““先进先出””。 对循环队列操作有以下几种状态： ⑴初始时队列空，队首指针和队尾指针均指向存储空间的最后一个位置，即f=r=m。 ⑵入队运算时，尾指针进一，即 r←r+1； if r=m+1 then r1； r←r mod m+1；f←f+1；if f=m+1 then f1； f←f mod m+1； f=r。 ⑸队列满时有f=r mod m+1。（为了区分队列空和队列满，改用“队尾指针追上队首指针” 这 一特征作为队列满标志。这种处理方法的缺点是浪费队列空间的一个存储单元） 循环队列的运算有两种： 1、过程ADD2(q，x，rq中插入一个新元素x procedure ADD2 (var q：equeue； x：qtype； var r：integer)； begin t←r mod m+1；{计算插入位置} if t=f then writeln(’full’) {队列满} else begin