数据结构与算法(C++)讲队列

1,EssentialofLectureSeven：,一、队列的定义二、队列的存储结构三、队列基本操作的实现四、队列的应用,第六讲队列,难点,2,课前实战：程序阅读题,请简述下面算法的功能ProcDemo(varS2:Seqstack;varS1:Seqstack)/Seqstack是顺序栈类型Seqstacktmp;DataTypex;/DataType是栈中元素的类型Initstack(tmp);Initstack(S2);while(notstackempty(S1)/栈S1非空x=pop(S1);push(tmp,x);while(notstackempty(tmp)x=pop(tmp);push(S1,x);push(S2,x);,3,一、队列的定义queue,只允许在一端插入元素，另一端删除元素的线性表允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)特点：先进先出(FIFO),4,1intLength()const初始条件：队列已存在。操作结果：返回队列元素个数。2boolEmpty()const初始条件：队列已存在。操作结果：如队列为空，则返回true，否则返回false3voidClear()初始条件：队列已存在。操作结果：清空队列。,队列的基本操作,一、队列的定义queue,5,一、队列的定义（queue）,4voidTraverse(void(*Visit)(constElemType/队头队尾指针/辅助函数:voidInit();/初始化队列,链队列类的实现,二、队列的存储结构,13,public:/抽象数据类型方法声明及重载编译系统默认方法声明:LinkQueue();/无参数的构造函数virtualLinkQueue();/析构函数intLength()const;/求队列长度boolEmpty()const;/判断队列是否为空voidClear();/将队列清空voidTraverse(void(*Visit)(constElemType,14,2、顺序队列,front,rear,空队列,front,rear,A入队,A,front,rear,B入队,AB,front,rear,C,D入队,ABCD,front,rear,A出队,BCD,front,rear,B出队,CD,front,rear,E,F,G入队,CDEFG,CDEFG,front,rear,H入队,溢出,15,二、队列的存储结构,2、顺序队列,入队时将新元素按rear指示位置加入再将队尾指针先进一rear=rear+1。出队时将下标为front的元素取出,再将队头指针先进一front=front+1。队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。,16,0,1,2,3,4,5,6,7,front,0,1,2,3,4,5,6,7,front,0,1,2,3,4,5,6,7,front,rear,A,A,B,C,rear,rear,空队列,A入队,B,C入队,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A出队,B出队,0,1,2,3,4,5,6,7,D,E,F,G,H,I入队,front,B,C,rear,A,front,B,C,rear,front,C,rear,D,E,F,G,H,I,3、循环队列CircularQueue,17,当J入队时，队满，此时front=rear但，队空时，front=rear可知，由此无法判断队列空和满。解决方法：（1）另设一个标识符或count统计。（2）少用一个元素空间，约定队头在队尾指针的下一个位置时作为队满的标志。,3、循环队列,18,队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%maxSize=front,3、循环队列,19,templateclassSqQueueprotected:intfront,rear;/队头队尾intmaxSize;/队列最大元素个数ElemType*elem;/元素存储空间/辅助函数:boolFull()const;/判断栈是否已满voidInit();/初始化队列,循环队列类的实现,20,public:/抽象数据类型方法声明及重载编译系统默认方法声明:SqQueue(intsize=DEFAULT_SIZE);/构造函数virtualSqQueue();/析构函数intLength()const;/求队列长度boolEmpty()const;/判断队列是否为空voidClear();/将队列清空voidTraverse(void(*Visit)(constElemType,21,templateboolSqQueue:Full()const/操作结果：如队列已满，则返回true，否则返回falsereturnLength()=maxSize-1;templatevoidSqQueue:Init()/操作结果：初始化队列rear=front=0;,22,templateintSqQueue:Length()const/操作结果：返回队列长度return(rear-front+maxSize)%maxSize;templatevoidSqQueue:Traverse(void(*Visit)(constElemType,23,templateStatusCodeSqQueue:OutQueue(ElemType,24,templateStatusCodeSqQueue:InQueue(constElemType,25,1）解决计算机主机与外设不匹配的问题；,2）离散事件的模拟-模拟实际应用中的各种排队现象；3）用于处理程序中具有先进先出特征的过程；,主要有：,三、队列的应用,26,四、队列的应用,(a+b)i,例如：显示二项式的系数,i=111i=2121i=31331i=414641,27,四、队列的应用,1,1,1,s=1,t=1,2,s+t,1,例如：显示二项式的系数,28,四、队列的应用,例如：显示二项式的系数,1,2,1,1,s=1,t=2,3,s+t,s=t,t=1,3,s+t,1,29,四、队列的应用,例如：显示二项式的系数,1,3,3,1,1,s=1,t=3,4,s+t,s=t,t=3,6,s+t,s=t,t=1,4,s+t,1,30,四、队列的应用,最小优先队列：出队操作删除最小的数据元素值最大优先队列：出队操作删除最大的数据元素值。简单实现方法：入队时不排在队尾，而是插入在队列的适当位置，使队列的元素有序。从队列类派生，重载入队操作即可。,优先队列,31,四、队列的应用,templateclassMinPriorityLinkQueue:publicLinkQueue/链队列的派生类public:StatusCodeInQueue(constElemTypetemplateStatusCodeMinPriorityLinkQueue:InQueue(constElemType/事件发生时刻inteventType;/事件类型，03;,33,四、队列的应用,事件驱动模拟,优先队列：表示客户在银行窗口排队任何时刻发生的事件：客户达到事件1号窗口客户离开事件2号窗口客户离开事件3号窗口客户离开事件,structQElemType/窗口队列中数据元素类型intarrivalTime;/客户到达时刻intduration;/客户办理业务需要的时间;,34,四、队列的应用,银行业务模拟类,事件队列（优先队列）,窗口队列,累计客户停留时间,客户总人数,办理业务的平均时间,两个相邻客户到达银行的平均时间间隔,银行关门时间,35,windowsQ,初始状态,evPQ,ev.occurTime=0;ev.eventType=0;evPQ.InQueue(ev);,evPQ.OutQueue(ev);,0类型为到达事件,36,windowsQ,evPQ,0为到达事件，生成2个随机数durTime=16;该到达的客户需要的时长,发生时刻2到达事件0,interTime=2;下一客户发生时刻0+2，插入优先队列,客户到达时间0办理需要时间16,37,windowsQ,evPQ,016,客户排在1号窗口的队头，生成一个离开事件occurTime=0+16eventType=116,1入队！,发生时刻161号窗口离开事件,38,windowsQ,evPQ,016,evPQ.OutQueue(ev);,2,00为到达事件，生成2个随机数durTime=18interTime=3,下一客户到达事件2+3，0入队,39,windowsQ,evPQ,016,第2个客户排在第2个窗口到达时间2，处理需要时长18,客户排在2号窗口的队头，生成一个离开事件occurTime=2+18eventType=220,2入队！,40,windowsQ,evPQ,016,evPQ.OutQueue(ev);,5,00为到达事件，生成2个随机数durTime=15interTime=6,下一客户到达事件5+6，0入队,第3个客户排在第3个窗口到达时间5，处理需要时长15,41,windowsQ,evPQ,016,客户排在3号窗口的队头，生成一个离开事件occurTime=5+15eventType=320,3入队！,42,windowsQ,evPQ,016,evPQ.OutQueue(ev);,11,00为到达事件，生成2个随机数durTime=17interTime=6,下一客户到达事件11+6，0入队,43,windowsQ,evPQ,016,第4个客户排在第1个窗口到达时间11，处理需要时长17,44,windowsQ,evPQ,016,evPQ.OutQueue(ev);,16,11为离开事件，删除窗口1的队头客户,删除后1号窗口非空，产生1个离开事件16+17,1入队,45,windowsQ,evPQ,1117,46,问题描述：已知集合A=a1,a2,an，及集合上的关系R=(ai,aj)|ai,ajA,ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少。,四、队列的应用,划分子集问题,47,四、队列的应用,划分子集问题,例A=1,2,3,4,5,6,7,8,9R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集划分为：A1=1,3,4,8A2=2,7A3=5A4=6,9,48,算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组所用数据结构冲突关系矩阵rij=1,i,j有冲突rij=0,i,j无冲突循环队列cqn数组resultn存放每个元素分组号工作数组newrn,四、队列的应用,划分子集问题,49,工作过程初始状态：A中元素放于cq中，result和newr数组清零，组号group=1第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组若其在newr中对应位置为“0”,无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束,划分子集问题,50,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,51,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,52,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,53,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,54,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,55,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,56,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,57,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,58,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,59,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,60,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,61,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,62,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,63,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,64,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,65,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3),划分子集问题,66,cq,R=(2,8),(9,4),(2,9),(2,1),(2,5