第九讲 链队列与循环队列.pptVIP

第 九 讲 知 识 点 队列的链式存储（链队列） 队列的顺序表示（循环队列）及基本操作 难 点 循环队列空、满的判断标志 要 求 掌握循环队列的定义及出入队算法 3．3 队列 3.3.1 基本概念 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加 入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。 显然退出队列的次序也只能是a1,a2,…an ，也就是说 队列的修改是依先进先出的原则进行的。 向队列添加元素称为入队，从队列中删除元素称为出 队。新入队的元素只能添加在队尾，出队的元素只能 是删除队头的元素 与堆栈类似，队列也可以简单的用一维数组表示。 设数组名为Queue，其下标下界为1，上界为n。 一般使用一个变量r指示队尾的下标值，叫做队尾指针；用另一个变量f指示队头的下标值，称为队头指针 队列中元素的数目等于零称为空队列，此时队头指针和队尾指针均为零，即f=r=0。 假定有A～F 6个元素先后进入队列，但A、B两个元素已陆续出队了，故队尾指针r=6，而队头指针f=3。 3．3．2 链队列 1、 链队列：限制仅在表头删除和表尾插入的单链表 仅有单链表的头指针不便于在表尾做插入操作， 再增加一个尾指针，指向链表的最后一个结点。 2、链队列的定义 typedef struct qnode { elemtype data; struct qnode *next; } Qnode,*qlink; typedef struct{ qlink front; qlink rear; }linkqueue; 2、操作 建立一个空队（P62） 销毁队列(P62） 元素e进队（P62） 当给队列插入元素时，队尾指针r后移而队头指 针不动，但有一个情况例外，即当向空队列插入第一 个元素时，队头指针与队尾指针同时指向新元素。 删除队头元素值（P62） 当从队列删除元素时，队头指针f后移而队尾指 针r不动，同样有例外，即当删除最后元素时， 队头指针与队尾指针同时变为空。 3．3．4 循环队列－队列的顺序表示和实现 由于顺序队列的队头和队尾的位置是变化的， 因而设置两把指针分别指示队头和队尾元素， 初始值均置为０。 入队时将新元素插入尾指针所指位置，然后将 尾指针加１。 出队时，删去头指针所指元素，然后将头指针 加１并返回被删元素。 当头尾指针相等时队列为空。在非空队列里，头指 针始终指向队头元素，而尾指针始终指向队尾元素 的下一位置。 顺序队列中还存在“假上溢”现象。在入队出队操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于最大空间，但可能由于尾指针巳超出上界而不能做入队操作。 循环队列 为克服假上溢现象，将顺序队列想象为一首尾相接的圆环，称为循环队列。 在循环队列中进行出队、入队操作时，头尾指针仍 要移动。只不过当头尾指针指向上界时，其加1操作 的结果是指向向量的下界0。 由于入队时尾指针向前追赶头指针，出队时头指针向 前追赶尾指针，故队空和队满时头尾指针均相等。 无法通过front==rear?来判断队列“空”还是“满”。 改进判断队空或满的方法至少有三种： 其一是另设一个布尔变量以匹别队列的空和满； 其二是少用一个元素的空间，若front==rear，则队列空，若尾指针rear在循环意义下加1后等于头指针，若则队满（注意：rear所指单元始终为空）； 其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。 #define QueueSize 100 typedef Struct { int front; int rear; elemtype *base; }sqQueue; 基本操作 建立一个空队（P64） 求队列长度（P64） 元素e进队（P65） 删除队头元素值（P65） 判断队空 int queueempty(sqQueue Q) { if (Q.front==Q.rear) return