《数据库第三章队列教学.ppt》由会员分享，可在线阅读，更多相关《数据库第三章队列教学.ppt（30页珍藏版）》请在三一办公上搜索。
1、数 据 结 构,李 鑫辽宁工程技术大学电信学院,数据结构课程的内容,3.1 栈（Stack）,第三章 栈和队列,3.2 队列（Queue）,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,应用背景-排列问题,在计算机科学中，也有排队问题用队列来解决,1、银行接待客户2、公共资源的使用3、接听电话,排队论,1、解决主机与外部设备之间速度不匹配的问题 例如：主机和打印机，引人打印数据缓冲区2、解决由多用户引起的资源竞争问题 例如：CPU竞争问题,非排列问题-第7章图中应用队列解决图的操作,缓冲区的作用,3.4 队列,与线性表相同，
2、仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。,基本操作：入队或出队，建空队列，判队空或队满等操作。,尾部插入,首部删除,队列定义,队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（）的线性表。,例如：队列 Q=(a1,a2,a3,.,an-1,an),在队尾插入元素称为入队；在队首删除元素称为出队。,队首,队尾,问：为什么要设计队列？它有什么独特用途？,离
3、散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）；操作系统中的作业调度（一个CPU执行多个作业）；3.简化程序设计。,答：,队的实现方式是本节重点，关键是掌握入队和出队操作。具体实现依存储结构（链队或顺序队）的不同而不同。,1.链队列 2.顺序队,队的抽象数据类型定义：ADT Queue数据对象：D=数据关系：R=基本操作：ADT Queue,建队、入队或出队、判队空或队满等，见教材P59,重点是循环顺序队,基本操作,InitQueue（&Q）操作结果：构造一个空队列DestroyQueue（&Q）初始条件：队列Q已经存在操作结果：队列Q被销毁ClearQueue（Q）
4、初始条件：队列Q已经存在操作结果：将Q清为空队列,QueueEmpty（Q）初始条件：队列Q已经存在操作结果：若Q为空队列，则返回TURE,否则FALSEQueueLength（Q）初始条件：队列Q已经存在操作结果：返回Q的元素个数，即队列的长度,EnQueue（&Q，e）初始条件：队列Q已经存在操作结果：插入元素e为Q的新的队尾元素DeQueue（&Q,&e）初始条件：Q为非空队列操作结果：删除Q的对头元素，并用e返回其值,GetHead（Q，&e）初始条件：队列Q为非空队列操作结果：用e返回Q的对头元素QueueTraverse（Q，visit（）初始条件：Q已存在且非空操作结果：从对头到
5、队尾，依次对Q的每个元素调用函数visit（）。一旦visit（）失败，则操作失败,链队列类型定义：typedef struct QueuePtr front;/队首指针 QueuePtr rear;/队尾指针 LinkQueue;,结点类型定义：typedef Struct QNode QElemType data;/元素 Struct QNode*next;/指向下一结点的指针 Qnode,*QueuePtr;,关于整个链队的总体描述,链队中任一结点的结构,1.链队列,Q.rear,讨论：空链队的特征？,怎样实现链队的入队和出队操作？,链队会满吗？,Q.front=Q.rear,一般不会，
6、因为删除时有free动作。除非内存不足！,入队（尾部插入）：Q.rear-next=S;Q.rear=S;S-next=NULL出队（头部删除）：p=Q.front-next;Q.front-next=p-next;,链队示意图：,完整操作函数见教材P62下,(队尾),(队首),Q.front,Q.rear,p,(队尾),Dequeue(linkqueue,只有一个元素情况,Status EnQueue(LinkQueue,核心语句,采用动态分配空间的形式,顺序队类型定义：,建队核心语句：q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAX
7、SIZE);/分配空间,关于整个顺序队的总体描述,#define QUEUE-MAXSIZE 100/最大队列长度 typedef struct QElemType*base;/队列的基址 int front;/队首指针 int rear;/队尾指针 SqQueue,顺序队中每个结点的结构描述在此省略，是QElemType类型。,2.顺序队,(队尾),(队首),队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。,空队列的特征？约定：Q.front=Q.rear,队尾后地址,入队(尾部插入)：Q.rear=e;rear+;出队(头部删除)：e=Q.front;front+;,讨
8、论：,假溢出！,有缺陷,怎样实现入队和出队操作？核心语句如下：,用base做数组名,e,顺序队示意图：,解决假溢出的途径,采用循环队列,答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,问：什么叫“假溢出”？如何解决？,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：使用一个计数器记录队列中元素个数（即队列长度）；加设标志位，删除时置1,插入时置0,则可识别当前front=rear属于何种情况 人为浪费一个单元，则队满特征可改为front=(rear+1)%N；,
9、队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度（即数据元素个数）：L=（Nrearfront）%N,实际中常选用方案3（人为浪费一个单元）：即front和rear二者之一指向实元素，另一个指向空闲元素。,问3：在具有n个单元的循环队列中，队满时共有多少个元素？,N-1个,6,问1：左图中队列maxsize N=？,问2：左图中队列长度L=？,5,（）rf（）（nfr）%n（）nrf（）（nrf）%n,要分析4种公式哪种最合理？当 r f 时（A）合理；当 r f 时（C）合理；,答：,综合2种情况，以（D
10、）的表达最为合理,例2：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先,移动队首指针,取出元素,，后,。,例1：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,例3：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。,删除4个元素后f=5；,再插入4个元素后，r=(0+4)%6=4,rear=4,讨论：循环队列的基本操作如何实现？以建
11、队、入队和出队三种基本操作为例,1）初始化一个空队列,算法要求：生成一空队列算法操作：为队列分配基本容量空间 设置队列为空队列，其特征即：front=rear=0（也可为任意单元，如1，2，甚至-1）,建队的完整算法：,Status InitQueue(SqQueue,算法说明：向循环队列的队尾插入一个元素分 析：(1)插入前应当先判断队列是否满？if(q.rear+1)%QUEUE_MAXSIZE)=q.front)return ERROR;(2）插入动作 q.base q.rear=e;q.rear=(q.rear+1)%QUEUE_MAXSIZE;,2）入队操作,队列尺寸,Status
12、EnQueue(SqQueue,入队操作完整算法,rear指针在元素入队后再加,3）出队操作,算法说明：删除队头元素，返回其值 e 分 析：（1）在删除前应当判断队列是否空？if(q.front=q.rear)return ERROR;（2）删除动作分析；前面约定指针front指向队首元素的位置，故：e=q.base q.front;q.front=(q.front+1)%QUEUE_MAXSIZE;,队列尺寸,front指针在元素出队后再加,Status DeQueue(SqQueue/DeQueue,出队操作完整算法,对这4个数据元素进行的队操作是进队2次，出队1次，再进队2次，出队1次；
13、这时，第1次出队得到的元素是？，第2次出队得到的元素是？。经操作后，最后在队中的元素还有？个，队尾指针指向？。,解：此题用V4大小数组即可（V0V3 4个单元有效）。,例：对4个数据元素进行队操作。在进队操作时，按a1、a2、a3、a4次序每次进入一个元素（假设队的初态为空）。,进队2次,出队1次,再进队2次,出队1次,a1、a2 f=r=0;r+;r+(f=0,r=2),a2、a3、a4 r+;r+(f=1,r=4=0),v0,a1 f+;(f=1,r=2),a2 f+(f=2,r=0),a1,a2,2,本章小结,线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链
14、表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。,运算规则不同：线性表为随机存取；而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。,用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。,不同点：,第3章结束,第3章作业,1、简述队列和栈这两种数据类型的相同点和差异处2、如果用一个循环数组q0m-1表示队列，该队列只有一个头指针front，不设尾指针，而改置计数器count用以记录队列中节点的个数。要求：编写实现队列的5个运算（置空，判空，取对头元 素，出队，入队）队列中能容纳的元素的个数最多是多少？,2023/11/14,数据结构,30,
