数据库队列教学省公共课一等奖全国赛课获奖课件.pptx

辽宁工程技术大学辽宁工程技术大学数数 据据 结结 构构李李 鑫鑫辽宁工程技术大学电信学院辽宁工程技术大学电信学院辽宁工程技术大学电信学院辽宁工程技术大学电信学院第第1页页数据结构课程内容数据结构课程内容第第2页页3.1 栈栈（Stack）第三章第三章 栈和队列栈和队列3.2 队列队列（Queue）1.定义定义2.逻辑结构逻辑结构3.存放结构存放结构4.运算规则运算规则5.实现方式实现方式1.定义定义2.逻辑结构逻辑结构3.存放结构存放结构4.运算规则运算规则5.实现方式实现方式第第3页页应用背景-排列问题在计算机科学中，也有排队问题用队列来处理1 1、银行接待客户、银行接待客户2 2、公共资源使用、公共资源使用3 3、接听电话、接听电话排队论排队论1、处理主机与外部设备之间速度不匹配问题、处理主机与外部设备之间速度不匹配问题 比如比如：主机和打印机，：主机和打印机，引人打印数据缓冲区引人打印数据缓冲区2、处理由多用户引发资源竞争问题、处理由多用户引发资源竞争问题 比如：比如：CPU竞争问题竞争问题非排列问题-第7章图中应用队列处理图操作缓冲区缓冲区作用作用第第4页页3.4 3.4 队列队列队列队列与线性表相同，仍为一对一关系。与线性表相同，仍为一对一关系。次序队次序队或或链队链队，以，以循环次序队循环次序队更常见。更常见。只能在队首和队尾运算，且访问结点时依照只能在队首和队尾运算，且访问结点时依照先进先出先进先出（FIFOFIFO）标准。标准。关键是掌握关键是掌握入队入队和和出队出队操作，详细实现依次操作，详细实现依次序队或链队不一样而不一样。序队或链队不一样而不一样。存放结构存放结构存放结构存放结构运算规则运算规则运算规则运算规则实现方式实现方式实现方式实现方式 逻辑结构逻辑结构逻辑结构逻辑结构只能在表一端进行插入运算，在表另一端进只能在表一端进行插入运算，在表另一端进行删除运算线性表。行删除运算线性表。基本操作基本操作：入队或出队，建空队列，判队空或队满等操作。入队或出队，建空队列，判队空或队满等操作。尾部插入尾部插入首部删除首部删除队列定义队列定义队列定义队列定义第第5页页队列队列（Queue）是仅在是仅在表尾表尾进行插入操作，在进行插入操作，在表头表头进行删除操进行删除操作线性表。它是一个先进先出作线性表。它是一个先进先出（）（）线性表。线性表。比如：队列比如：队列 Q=(a1 ,a2 ,a3 ,.,an-1 ,an)在队尾插入元素称为在队尾插入元素称为入队入队入队入队；在队首删除元素称为；在队首删除元素称为出队出队出队出队。队首队首队尾队尾问：为何要设计队列？它有什么独特用途？问：为何要设计队列？它有什么独特用途？1.离散事件模拟离散事件模拟（模拟事件发生先后次序（模拟事件发生先后次序,比如比如 CPUCPU芯芯片中指令译码队列）片中指令译码队列）；2.操作系统中作业调度操作系统中作业调度（一个（一个CPUCPU执行多个作业）执行多个作业）；3.3.简化程序设计。简化程序设计。答：答：第第6页页队实现方式是本节重点，关键是掌握队实现方式是本节重点，关键是掌握入队入队和和出队出队操作操作。详细实现依详细实现依存放结构存放结构（链队链队或或次序队次序队）不一样而不一样。）不一样而不一样。1.链队列链队列 2.次序队次序队队抽象数据类型定义队抽象数据类型定义：ADT Queue数据对象：数据对象：D=数据关系：数据关系：R=基本操作：基本操作：ADT Queue建队、入队或出队、判队空建队、入队或出队、判队空或队满等，见教材或队满等，见教材P59P59重点是循环重点是循环次序队次序队第第7页页基本操作InitQueueInitQueue（&Q&Q）操作结果：结构一个空队列操作结果：结构一个空队列DestroyQueueDestroyQueue（&Q&Q）初始条件：队列初始条件：队列Q Q已经存在已经存在操作结果：队列操作结果：队列Q Q被销毁被销毁ClearQueueClearQueue（Q Q）初始条件：队列初始条件：队列Q Q已经存在已经存在操作结果：将操作结果：将Q Q清为空队列清为空队列QueueEmptyQueueEmpty（Q Q）初始条件：队列初始条件：队列Q Q已经存在已经存在操作结果：若操作结果：若Q Q为空队列，则返回为空队列，则返回TURE,TURE,不然不然FALSEFALSEQueueLengthQueueLength（Q Q）初始条件：队列初始条件：队列Q Q已经存在已经存在操作结果：返回操作结果：返回Q Q元素个数，即队列长度元素个数，即队列长度第第8页页EnQueueEnQueue（&Q&Q，e e）初始条件：队列初始条件：队列Q Q已经存在已经存在操作结果：插入元素操作结果：插入元素e e为为Q Q新队尾元素新队尾元素DeQueueDeQueue（&Q,&e&Q,&e）初始条件：初始条件：Q为非空队列为非空队列操作结果：删除操作结果：删除Q对头元素，并用对头元素，并用e返回其值返回其值GetHeadGetHead（Q Q，&e&e）初始条件：队列初始条件：队列Q为非空队列为非空队列操作结果：用操作结果：用e返回返回Q对头元素对头元素QueueTraverseQueueTraverse（Q Q，visitvisit（）（）初始条件：初始条件：Q Q已存在且非空已存在且非空操作结果：从对头到队尾，依次对操作结果：从对头到队尾，依次对Q Q每个元素调用函数每个元素调用函数visitvisit（）。（）。一旦一旦visitvisit（）失败，则操作失败（）失败，则操作失败第第9页页链链队列队列类型定义：类型定义：typedef struct QueuePtr front;/队首指针队首指针 QueuePtr rear;/队尾指针队尾指针 LinkQueue;结点结点类型定义：类型定义：typedef Struct QNode QElemType data;/元素元素 Struct QNode *next;/指向下一结点指针指向下一结点指针 Qnode,*QueuePtr;关于整个链队总关于整个链队总体描述体描述链队中任一链队中任一结点结构结点结构1.1.链队列链队列链队列链队列Q.Q.rear(队尾队尾)(队首队首)Q.Q.fronta1a2a3p第第10页页讨论：讨论：空链队特征？空链队特征？Q.frontQ.rear 怎样实现链队怎样实现链队入队和出队入队和出队操作？操作？链队会满吗？链队会满吗？Q.front=Q.rear普通不会，因为删除时有普通不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！入队（尾部插入）：入队（尾部插入）：Q.rear-next=S;Q.Q.rear=S;S-next=NULL出队（头部删除）：出队（头部删除）：p=Q.front-next;Q.Q.front-next=p-next;SD链队示意图：链队示意图：完整操作函数完整操作函数见教材见教材P62P62下下(队尾队尾)(队首队首)Q.Q.fronta1a2a3Q.Q.rearp(队尾队尾)Da1a2a3(队尾队尾)第第11页页Dequeue(linkqueue&Q,QelemType&e)/删除对头元素，if(Q.front=Q.rear)return ERROR;p=Q.frontnext;e=pdata;Q.frontnext=pnext;if(Q.rear=p)/if(Q.rear=p)/Q.rear=Q.front;Q.rear=Q.front;free(p);return ok;只有一个元素只有一个元素情况情况第第12页页Status EnQueue(LinkQueue&Q,QElemType e)Status EnQueue(LinkQueue&Q,QElemType e)/插入元素插入元素e e为对尾元素为对尾元素s=(QueuePtr)malloc(sizeof(QNode);s=(QueuePtr)malloc(sizeof(QNode);if(!s)return ERROR;if(!s)return ERROR;s-data=e;s-next=NULL;s-data=e;s-next=NULL;Q.rear-next=s;Q.rear-next=s;Q.rear=s;Q.rear=s;return OK;return OK;关键语句关键语句第第13页页采取动态分配空间形式采取动态分配空间形式次序队类型定义：次序队类型定义：建队建队关键语句关键语句：q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);/分配空间分配空间关于整个次序队关于整个次序队总体描述总体描述#define QUEUE-MAXSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType *base;/队列基址队列基址 int front;/队首指针队首指针 int rear;/队尾指针队尾指针 SqQueue次序队中每个结点结构描述在此省略，是次序队中每个结点结构描述在此省略，是QElemTypeQElemType类型。类型。2.2.次序队次序队次序队次序队第第14页页(队尾队尾)(队首队首)Q.front a1 a2 a3data a40.99Q.rear 队列会满吗？队列会满吗？极易装满！极易装满！因为数组因为数组通常有长度限制，而通常有长度限制，而其前端空间无法释放。其前端空间无法释放。空队列特征？空队列特征？约定：约定：Q.front=Q.rear队尾后地址队尾后地址入队入队(尾部插入尾部插入)：Q.rear=e;rear+;出队出队(头部删除头部删除)：e=Q.front;front+;讨论：讨论：假溢出！假溢出！假溢出！假溢出！有有缺缺点点 怎样实现入队和出队怎样实现入队和出队操作？操作？关键语句以下关键语句以下：用用base做数组名做数组名e次序队示意图：次序队示意图：第第15页页处理假溢出路径处理假溢出路径采取循环队列采取循环队列答：答：在次序队中，当尾指针已经到了数组上在次序队中，当尾指针已经到了数组上界，不能再有入队操作，但其实数组中还有界，不能再有入队操作，但其实数组中还有空位置，这就叫空位置，这就叫“假溢出假溢出”。问：什么叫问：什么叫“假溢出假溢出”？怎样处理？怎样处理？第第16页页a3a2a10123N-1rearfront循环队列（臆造）循环队列（臆造）循环队列（臆造）循环队列（臆造）新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满时也会有队满时也会有front=rear；判决条件将出现二义性！判决条件将出现二义性！处理方案有三：处理方案有三：使用一个使用一个计数器计数器统计队列中元素个数（即队列长度）；统计队列中元素个数（即队列长度）；加加设标志位设标志位，删除时置删除时置1,1,插入时置插入时置0,0,则可识别当前则可识别当前front=rear属于何种情况属于何种情况 人为人为浪费一个单元浪费一个单元，则队满特征可改为，则队满特征可改为front=(rear+1)%N；次序队列次序队列次序队列次序队列a3a2a1frontrear 0 1 2 3 .N-1第第17页页队空条件队空条件:front=rear (初始化时：初始化时：front=rear)队满条件队满条件：front=(rear+1+1)%N (N=maxsize)队列长度队列长度（即数据元素个数）（即数据元素个数）：L=（Nrearfront）%N J2 J3J1 J4 J5frontrear 实际中常选取实际中常选取方案方案3（人为人为浪费一个单元）浪费一个单元）：即即front和和rear二者之一指向实元素，另一个指向空闲元素。二者之一指向实元素，另一个指向空闲元素。问问3：在含有在含有n个单元循环个单元循环队列中，队满时共有多少个队列中，队满时共有多少个元素？元素？N-1个个6 问问1：左图中队列左图中队列maxsize N=？问问2：左图中队列左图中队列长度长度L=？5第第18页页（）（）rf （）（）（nfr）%n （）（）nrf （）（）（nrf）%n要分析要分析4 4种公式哪种最合理？种公式哪种最合理？当当 r f 时（时（A）合理；）合理；当当 r f 时（时（C）合理；）合理；答：答：综合综合2种情况，以种情况，以（D）表示最为合理）表示最为合理例例2：在一个循环队列中，若约定队首指针指向队首元素在一个循环队列中，若约定队首指针指向队首元素前一个前一个位置。那么，从循环队列中删除一个元素时，其操位置。那么，从循环队列中删除一个元素时，其操作是作是 先先 移动队首指针移动队首指针取出元素取出元素，后，后。例例1：数组数组n用来表示一个循环队列，用来表示一个循环队列，f 为当前队列头元素为当前队列头元素前一前一位置，位置，r 为队尾元素位置。假定队列中元素个数小于为队尾元素位置。假定队列中元素个数小于n，计算队列中元素公式为计算队列中元素公式为:第第19页页例例3：一循环队列以下列图所表示，若先删除一循环队列以下列图所表示，若先删除4个元素，接个元素，接着再插入着再插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置?J2 J3J1 J4 J5front=1rear=0解：解：由图可知，队头和队尾指针初态分别为由图可知，队头和队尾指针初态分别为front=1和和rear=0。删除删除4个元素后个元素后f=5；再插入再插入4个元素后，个元素后，r=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4rear=0front=5第第20页页讨论：循环队列基本操作怎样实现？讨论：循环队列基本操作怎样实现？以建队、入队和出队三种基本操作为例以建队、入队和出队三种基本操作为例1）初始化一个空队列）初始化一个空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：算法操作：为队列分配基本容量空间为队列分配基本容量空间 设置队列为设置队列为空队列空队列，其特征即：，其特征即：front=rear=0（也可为任意单元，如（也可为任意单元，如1，2，甚至甚至-1）第第21页页建队完整算法：建队完整算法：Status InitQueue(SqQueue&q)/初始化空循环队列初始化空循环队列 q q q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);/分配空间分配空间if(!q.base)exit(OVERFLOW);/内存分配内存分配失败，退出程序失败，退出程序 q.front=q.rear=0;/置空队列置空队列 return OK;/InitQueue/InitQueue;第第22页页算法说明：向循环队列算法说明：向循环队列队尾插入队尾插入一个元素一个元素分分 析析：(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）入队操作入队操作队列尺寸队列尺寸第第23页页Status EnQueue(SqQueue&q,QElemType e)/向循环队列向循环队列 q q 队尾加入一个元素队尾加入一个元素 e e if(q.rear+1)%QUEUE_MAXSIZE=q.front )return ERROR;/队满则上溢，无法再入队队满则上溢，无法再入队 q.base q.rear =e;/新元素新元素e e入队入队 q.rear=(q.rear+1)%QUEUE_MAXSIZE;/指针后移指针后移 return OK;/EnQueueEnQueue;入队操作完整算法入队操作完整算法rearrear指针在元素入队后再加指针在元素入队后再加第第24页页3）出队操作）出队操作算法说明：删除队头元素，返回其值算法说明：删除队头元素，返回其值 e 分分 析：析：（1）在删除前应该判断队列是否空？在删除前应该判断队列是否空？if(q.front=q.rear)return ERROR;（2）删除动作分析；删除动作分析；前面约定指针前面约定指针frontfront指向队首元素位置，故指向队首元素位置，故：e=q.base q.front ;q.front=(q.front+1)%QUEUE_MAXSIZE;队列尺寸队列尺寸 frontfront指针在元素出队后再加指针在元素出队后再加第第25页页Status DeQueue(SqQueue&q,QElemType&e)/若队列不空，删除循环队列若队列不空，删除循环队列q q队头元素队头元素，/由由 e e 返回其值，并返回返回其值，并返回OKOK if(q.front=q.rear)return ERROR;/队列空队列空 e=q.base q.front ;q.front=(q.front+1)%QUEUE_MAXSIZE;return OK;/DeQueue/DeQueue出队操作完整算法出队操作完整算法第第26页页对这对这4 4个数据元素进行队操作是个数据元素进行队操作是进队进队2 2次，出队次，出队1 1次，再进队次，再进队2 2次，出队次，出队1 1次次；这时，第；这时，第1 1次出队得到元素是次出队得到元素是？，第，第2 2次次出队得到元素是出队得到元素是？。经操作后，最终在队中元素还有。经操作后，最终在队中元素还有？个，队尾指针指向个，队尾指针指向？。解：解：此题用此题用V4V4大小数组即可（大小数组即可（V0V0V3 4V3 4个单元有效）个单元有效）。例：例：对对4 4个数据元素进行队操作。在进队操作时，按个数据元素进行队操作。在进队操作时，按a1a1、a2a2、a3a3、a4a4次序每次进入一个元素（假设队初态为空）。次序每次进入一个元素（假设队初态为空）。进队进队2 2次次 出队出队1 1次次 再进队再进队2 2次次 出队出队1 1次次a1、a2 f=r=0;r+;r+(f=0,r=2)a2、a3、a4 r+;r+(f=1,r=4=0)v0a1 f+;(f=1,r=2)a2 f+(f=2,r=0)a1a22第第27页页本章小结线性表、栈、队异同点：线性表、栈、队异同点：相相相相同同同同点点点点：逻逻辑辑结结构构相相同同，都都是是线线性性；都都能能够够用用次次序序存存放放或或链链表表存存放放；栈栈和和队队列列是是两两种种特特殊殊线线性性表表，即即受受限限线线性性表表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。运算规则不一样：运算规则不一样：线性表为随机存取；线性表为随机存取；而栈是只允许在一端进行插入和删除运算，因而而栈是只允许在一端进行插入和删除运算，因而是后进先出表是后进先出表LIFOLIFO；队列是只允许在一端进行插入、另一端进行删除队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表运算，因而是先进先出表FIFOFIFO。用途不一样，用途不一样，线性表比较通用；堆栈用于函数线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模调用、递归和简化设计等；队列用于离散事件模拟、拟、OSOS作业调度和简化设计等。作业调度和简化设计等。不一样点：不一样点：不一样点：不一样点：第第3章章结束结束第第28页页第第3章作业章作业1 1 1 1、简述队列和栈这两种数据类型相同点和差异处、简述队列和栈这两种数据类型相同点和差异处、简述队列和栈这两种数据类型相同点和差异处、简述队列和栈这两种数据类型相同点和差异处2 2 2 2、假如用一个循环数组、假如用一个循环数组、假如用一个循环数组、假如用一个循环数组q0m-1q0m-1q0m-1q0m-1表示队列，该队列只有一个表示队列，该队列只有一个表示队列，该队列只有一个表示队列，该队列只有一个头指针头指针头指针头指针frontfrontfrontfront，不设尾指针，而改置计数器，不设尾指针，而改置计数器，不设尾指针，而改置计数器，不设尾指针，而改置计数器countcountcountcount用以统计队列用以统计队列用以统计队列用以统计队列中节点个数。中节点个数。中节点个数。中节点个数。要求：编写实现队列要求：编写实现队列要求：编写实现队列要求：编写实现队列5 5 5 5个运算（置空，判空，取对头元个运算（置空，判空，取对头元个运算（置空，判空，取对头元个运算（置空，判空，取对头元 素，出队，入队）素，出队，入队）素，出队，入队）素，出队，入队）队列中能容纳元素个数最多是多少？队列中能容纳元素个数最多是多少？队列中能容纳元素个数最多是多少？队列中能容纳元素个数最多是多少？第第29页页/10/10数据结构30第第30页页