《数据结构与算法》PPT课堂课件-第4章-队列.ppt
2023/3/231第四章 队列队列和栈一样是一种特殊的线性表，是操作受限的线性表，称其为限定性数据结构。队列的定义及特点v定义：队列是限定只能在表的一端进行插入，在 表的另一端进行删除的线性表l队尾尾(rear)允许插入插入的一端l队头头(front)允许删除删除的一端v队列特点：先进先出(FIFO)2023/3/232a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)双端队列a1 a2 a3.an 端1端2入队出队入队出队2023/3/2334.1 ADT队列(Queue)ADT队列上定义的常用的基本运算(1)Empty();(2)Full();(3)First();(4)Last();(5)EnQueue(x);(6)DeQueue(x);2023/3/2344.2 链队列结点定义typedef struct qnode *qlink;typedef struct qnode QItem element;qlink next;QNode;2023/3/235frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队2023/3/2364.3 队列的顺序存储结构实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront2023/3/237存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontrear.实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件2023/3/238012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志设一个标志以区别队空、队满2.少用一个元素空间少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front2023/3/239 4.4 队列的应用举例【举例1】汽车加油站。随着城市里汽车数量的急速增长，汽车加油站也渐随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加若用算法模拟这个过程，就需要设置加油车道数加2个队个队列。列。2023/3/2310【举例2】模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机速度在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。就是一个队列结构。2023/3/2311【举例3】CPU分时系统 在一个带有多个终端的计算机系统中，同时有多在一个带有多个终端的计算机系统中，同时有多个用户需要使用个用户需要使用CPU运行各自的应用程序，它们分别运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用通过各自的终端向操作系统提出使用CPU的请求，操的请求，操作系统通常按照每个请求在时间上的先后顺序，将它作系统通常按照每个请求在时间上的先后顺序，将它们排成一个们排成一个队列队列，每次把每次把CPU分配给分配给当前队当前队首首的请求的请求用户，即将该用户的应用程序投入运行，当该程序运用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将行完毕或用完规定的时间片后，操作系统再将CPU分分配给新的队首请求用户，这样即可以满足每个用户的配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使请求，又可以使CPU正常工作。正常工作。2023/3/2312队列应用举例 【举例4】划分子集问题问题描述：已知集合A=a1,a2,an，及集合上的关系R=(ai,aj)|ai,ajA,ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少例 A=1,2,3,4,5,6,7,8,9 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)可行的子集划分为：A1=1,3,4,8 A2=2,7 A3=5 A4=6,9 2023/3/2313算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组所用数据结构冲突关系矩阵rij=1,i,j有冲突rij=0,i,j无冲突循环队列cqn数组resultn存放每个元素分组号工作数组newrn2023/3/2314工作过程初始状态：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,即队空，运算结束2023/3/2315算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqf r0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 result初始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)2023/3/2316算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2317算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2318算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 1 1 0 00 1 2 3 4 5 6 7 8 newr1 0 1 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2319算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2320算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2321算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2322算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2323算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2324算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2325算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=5 6 7 90 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2326算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 7 9 50 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2327算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=7 9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2328算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2329算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=5 6 90 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2330算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 90 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2331算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 60 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2332算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 60 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2333算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=90 1 2 3 4 5 6 7 8 cqfr0 1 1 0 1 0 1 0 00 1 2 3 4 5 6 7 8 newr1 2 1 1 3 4 2 1 00 1 2 3 4 5 6 7 8 resultR=(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)2023/3/2334算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=0 1 2 3 4 5 6 7 8 cqfr0 1 1 1 1 0 1 0 00 1 2 3 4 5 6 7 8 newr1 2 1 1 3 4 2 1 40 1 2 3 4 5 6 7 8 resultR=(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,8 A2=2,7 A3=5 A4=6,9 2023/3/2335作业：1、P75 4.2(1)-用数组实现 4.2(2)-用指针实现2、假设用一个循环单链表来表示队列(称为循环队列)，且该队列只有队尾指针只有队尾指针，试分别写出入队和出队操作的具体算法。
