《数据结构解说PPT演示课件》由会员分享，可在线阅读，更多相关《数据结构解说PPT演示课件（44页珍藏版）》请在金锄头文库上搜索。
1、第3章 队列,与栈一样，队列也是一种操作受限的线性表。队列在操作系统和事务管理等软件设计中应用广泛，如键盘输入缓冲区问题就是利用队列的思想实现的。 本章重点和难点： 1、队列的顺序表示与实现 2、队列的链式表示与实现,3.1 队列的定义与抽象数据类型,队列只允许在表的一端进行插入操作，在表的另一端进行删除操作。3.1.1 什么是队列 队列（queue）是一种先进先出（first in first out，缩写为FIFO）的线性表，它只允许在表的一端进行插入，另一端删除元素。这与我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队头（front），允许删除的一
2、端称为队尾（rear）。因此又称队列为先进先出（FIFO）表。,3.1 队列的定义与抽象数据类型,假设队列为q=（a1，a2，ai，an），那么a1为队头元素，an为队尾元素。进入队列时，是按照a1，a2，an的顺序进入的，退出队列时也是按照这个顺序退出的。也就是说，当先进入队列的元素都退出之后，后进入队列的元素才能退出。即只有当a1，a2，an-1都退出队列以后，an才能退出队列。,3.1 队列的定义与抽象数据类型,2基本操作集合（1）置空队列InitQueue(Q)：初始化操作，建立一个空队列Q。（2）判队列空QueueEmpty(Q)：若Q为空队列，返回1，否则返回0。（3）入队列EnQ
3、ueue(Q,x)：若队列不满，插入元素x到队列Q的队尾。（4）出队列DeQueue(Q)：若队列不空，删除队头元素，并返回该元素。（5）取队头Gethead(Q)：若队列不空，返回队头元素。（,3.2 队列的顺序存储及实现,3.2.1 顺序队列的表示 顺序队列通常采用一维数组依次存放从队头到队尾的元素。同时，使用两个指针分别指示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针front，指向最后一个元素的指针被称为队尾指针rear。 元素a、b、c、d、e、f、g依次进入队列后的状态如图3.2所示。元素a存放在数组下标为0的存储单元中，g存放在下标为6的存
4、储单元中，队头指针front指向第一个元素a，队尾指针rear指向最后一个元素g的下一位置。,3.2 队列的顺序存储及实现,在使用队列前，先初始化队列，此时，队列为空，队头指针front和队尾指针rear都指向队列的第一个位置，即front=rear=0，如图3.3所示。 每一个元素进入队列，队尾指针rear就会增1，若元素a、b、c依次进入空队列，front指向第一个元素，rear指向下标为3的存储单元，如图3.4所示。,3.2 队列的顺序存储及实现,当一个元素出队列时，队头指针front增1，队头元素即a出队后，front向后移动一个位置，指向下一个位置，rear不变，如图3.3所示。,3
5、.2 队列的顺序存储及实现,3.2.2 顺序队列的“假溢出” 在对顺序队列进行插入和删除操作的过程中，可能会出现“假溢出”现象。经过多次插入和删除操作后，实际上队列还有存储空间，但是又无法向队列中插入元素，我们将这种溢出称为“假溢出”。 例如，在图3.2所示的队列中插入3个元素h、i、j，然后删除2个元素a，b之后，就会出现如图3.6所示的情况。当插入元素j后，队尾指针rear将越出数组的下界而造成“假溢出”。,3.2 队列的顺序存储及实现,3.2.3 顺序循环队列的表示 1顺序循环队列 为了充分利用存储空间，消除这种“假溢出”现象，当队尾指针rear和队头指针front到达存储空间的最大值（
6、假定队列的存储空间为QueueSize）的时候，让队尾指针和队头指针转化为0，这样就可以将元素插入到队列还没有利用的存储单元中。例如，在图3.6中，插入元素j之后，rear将变为0，可以继续将元素插入到下标为0的存储单元中。这样就把顺序队列使用的存储空间构造成一个逻辑上首尾相连的循环队列。,3.2 队列的顺序存储及实现,当队尾指针rear达到最大值QueueSize-1时，前提是队列中还有存储空间，若要插入元素，就要把队尾指针rear变为0；当队头指针front达到最大值QueueSize-1时，若要将队头元素出队，要让队头指针front变为0。这可通过取余操作实现队列的首尾相连。例如，假设Q
7、ueueSize=10，当队尾指针rear=9时，若要将新元素入队，则先令rear=（rear+1）%10=0，然后将元素存入队列的第0号单元，通过取余操作实现了队列的逻辑上的首尾相连。,3.2 队列的顺序存储及实现,2顺序循环队列的队空和队满判断 但是，在顺序循环队列在队空和队满的情况下，队头指针front和队尾指针rear同时都会指向同一个位置，即front=rear，如图3.7所示。即队列为空时，有front=0，rear=0，因此front=rear。队满时也有front=0，rear=0，因此front=rear。,3.2 队列的顺序存储及实现,为了区分这队空还是队满，通常有两个方法
8、：（1）增加一个标志位。设这个标志位为flag，初始时，有flag=0；当入队列成功，则flag=1；出队列成功，有flag=0。则队列为空的判断条件为：front=rear&flag=0，队列满的判断条件为：front=rear&flag=1。（2）少用一个存储单元。队空的判断条件为front=rear，队满的判断条件为front=(rear+1)%QueueSize。那么，入队的操作语句为：rear=（rear+1）%QueueSize，Qrear=x。出队的操作语句为：front=（front+1）%QueueSize。少用一个存储单元的顺序循环队列队满情况如图3.8所示。,3.2 队列
9、的顺序存储及实现,顺序循环队列类型描述如下： #define QueueSize 100/*队列的容量*/ typedef struct DataType dataQueueSize; int front,rear; /*队头指针和队尾指针*/ CirQueue; 其中，data用来存储队列中的元素，front和rear分别表示队头指针和队尾指针。,3.2 队列的顺序存储及实现,3.2.4 顺序循环队列的基本运算 顺序循环队列的基本运算算法实现如下。 （1）置空队列。 void InitQueue(CirQueue *Q) /*顺序循环队列的初始化*/ Q -front=Q -rear=0;
10、,3.2 队列的顺序存储及实现,（2）判断队列是否为空int QueueEmpty(CirQueue *Q) return Q -front = Q -rear ;(3)判对满int QueueFull(CirQueue *Q) return (Q -rear+1)%QueueSize = Q -front ;,3.2 队列的顺序存储及实现,（4）入队 int EnQueue(CirQueue *Q , DataType x) if(QueueFull(Q) printf(“Queue overflow”); else Q-dataQ-rear=x; Q-rear=(Q-rear+1)%Que
11、ueSize; ,3.2 队列的顺序存储及实现,（5）取队头元素 DataType GetFront (CirQueue *Q) if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else return Q-dataQ-front; ,3.2 队列的顺序存储及实现,（6）出队列DataType DeQueue(CirQueue *Q) DataType x; if(QueueEmpty(Q) printf(“Queue empty”); exit(0); else x=Q-dataQ-front; /*将要删除的元素赋值给x*/ Q-front=
12、(Q-front+1)%QueueSize; return x; ,3.2 队列的顺序存储及实现,3.2.3 顺序循环队列举例 P77,3.3 队列的链式存储及实现,采用链式存储的队列被称为链式队列或链队列。3.3.1 链式队列的表示1链式队列 链式队列通常用链表实现。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为队头指针和队尾指针）才能唯一确定。这里，与单链表一样，为了操作上的方便，我们给链队列添加一个头结点，并令队头指针front指向头结点，用队尾指针rear指向最后一个结点。,3.3 队列的链式存储及实现,链式队列的类型描述如下：/*结点类型定义*/typedef struct
13、 QNode DataType data; struct QNode * next; QueueNode;/*队列类型定义*/typedef struct QueueNode * front; /队头指针 QueueNode * rear; /队尾指针LinkQueue; /队列类型LinkQueue Q; /定义一链对列Q,3.3 队列的链式存储及实现,一个不带头结点的链式队列和带头结点的链队列分别如图3.12、图3.13所示。,3.3 队列的链式存储及实现,对于带头结点的链式队列，当队列为空时，队头指针front和队尾指针rear都指向头结点。如图3.14所示。 链式队列中，插入和删除操作
14、只需要移动队头指针和队尾指针，这两种操作的指针变化如图3.13、图3.16和图3.17所示。图3.13表示在队列中插入元素a的情况，图3.16表示队列中插入了元素a，b，c之后的情况，图3.17表示元素a出队列的情况。,3.3 队列的链式存储及实现,3.3.2 链式队列的基本运算链式队列的基本运算算法实现如下。（1）初始化队列。void InitQueue(LinkQueue *Q) /*初始化链式队列*/ Q-front=(QueueNode*)malloc(sizeof(QueueNode); Q-rear =Q-front; Q -rear-next=NULL;/*把头结点的指针域置为null*/,
