浙教版 (2019)3.2 队列优质课件ppt

这是一份浙教版 (2019)3.2 队列优质课件ppt，共16页。PPT课件主要包含了约瑟夫游戏，输出3，tail，head，输出361，队列的特性，队列的操作，①队列的存储，约瑟夫的队列实现，输出36等内容，欢迎下载使用。

n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m（m＞1）的人退出圈子。按原始编号输出最后一个出圈的编号。
任务一：当n=8,m=3时，用队列数据结构，请每位同学按游戏规则模拟一下，并按顺序输出出圈人员的编号。
1.队列的概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。
① 先进先出、后进后出。队首元素a1优先出队，紧接着是a2，a3，…，an–1，队尾元素an最后出队。
② 有限序列性。队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。
队列一般按顺序结构存储，可以用数组来实现。如图所示，数组que中存储了一个队列，共有4个元素，队首元素为“A”，队尾元素为“D” 。由于在入队和出队的过程中，队首元素和队尾元素的位置会改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。
② 队列的入队、出队
初始时，head指针变量与tail指针变量均记录下标为0的位置。元素“A”，“B”，“C”，“D”依次入队后，tail值为4，head值为0，如图所示。
que=[]head=0tail=0n,m=map(int,input().split())fr i in range(n): que.append(i+1) tail+=1tmp=0cnt=0
while head当第3个人出圈时，队列中前面的9个位置是空的，造成空间上的浪费，请问可以用什么方法解决？
循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。如图3.2.6所示，某队列分配的最大空间为5，其最后一个位置上的元素为“E”，队首指针变量head的值为4，队尾指针变量tail的值为5（tail超出了队列的边界），此时，数组中存在空闲位置，但新的元素不能入队。
将该队列改为循环队列，则在元素“E”入队后， head的值为4，队尾指针重新指向队首（tail的值为0），当新元素“F”入队时，就加入到队首，然后tail的值变为1，如图3.2.7所示。
当n=8,m=3时，循环队列的入队、出队如图所示：
n,m=map(int,input().split())que=[0]*(n+1)head=0tail=0fr i in range(n): que[tail]=i+1 tail+=1cnt=0tmp=0
while head!=tail: tmp=que[head] head=(head+1)%(n+1) cnt+=1 if cnt==m: print(tmp,end=" ") cnt=0 else: que[tail]=tmp tail=(tail+1)%(n+1)