浙教版（2019） 高中信息技术 选修1 第3章 3.2 队列 课件（共16张PPT）

(共16张PPT)
队列
n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m（m＞1）的人退出圈子。按原始编号输出最后一个出圈的编号。
1
2
3
4
5
……
n
6
7
8
约瑟夫游戏
1
2
3
4
5
……
n
6
7
8
约瑟夫游戏
任务一：当n=8,m=3时，用队列数据结构，请每位同学按游戏规则模拟
一下，并按顺序输出出圈人员的编号。
1
2
3
4
5
6
7
8
约瑟夫游戏
1 2 3 4 5 6 7 8 …
4 5 6 7 8 1 2 …
输出：3
tail
tail
head
head
约瑟夫游戏
4 5 6 7 8 1 2 …
head
tail
输出：3 6 1
7 8 1 2 4 5 …
head
tail
2 4 5 7 8 …
head
tail
队列
1.队列的概念
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。
队列
2.队列的特性
① 先进先出、后进后出。队首元素a1优先出队，紧接着是a2，a3，…，an–1，队尾元素an最后出队。
② 有限序列性。队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。
队列
3.队列的操作
①队列的存储
队列一般按顺序结构存储，可以用数组来实现。如图所示，数组que中存储了一个队列，共有4个元素，队首元素为“A”，队尾元素为“D” 。由于在入队和出队的过程中，队首元素和队尾元素的位置会改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。
队列
3.队列的操作
② 队列的入队、出队
初始时，head指针变量与tail指针变量均记录下标为0的位置。元素“A”，“B”，“C”，“D”依次入队后，tail值为4，head值为0，如图所示。
队列
4.约瑟夫的队列实现
que=[]
head=0
tail=0
n,m=map(int,input().split())
for i in range(n):
que.append(i+1)
tail+=1
tmp=0
cnt=0
while headtmp=que[head]
head+=1
cnt+=1
if cnt==3:
print(tmp,end=" ")
cnt=0
else:
tail+=1
que.append(tmp)
1 2 3 4 5 6 7 8 …
tail
head
0
1
2
3
4
5
6
7
队列
5.思考
输出：3 6
7 8 1 2 4 5 …
head
tail
输出：3 6 1
2 4 5 7 8
head
tail
当第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时，循环队列的入队、出队如图所示：
1 2 3 4 5 6 7 8
tail
head
0
1
2
3
4
5
6
7
8
2 3 4 5 6 7 8 1
tail
0
1
2
3
4
5
6
7
8
head
2 3 4 5 6 7 8 1
tail
0
1
2
3
4
5
6
7
8
head
2 4 5 6 7 8 1
tail
0
1
2
3
4
5
6
7
8
head
输出：3
约瑟夫的循环队列实现
n,m=map(int,input().split())
que=[0]*(n+1)
head=0
tail=0
for i in range(n):
que[tail]=i+1
tail+=1
cnt=0
tmp=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)
1 2 3 4 5 6 7 8
tail
head
0
1
2
3
4
5
6
7
8
队列
2.队列的特性
3.队列的基本操作
4.循环队列
1.队列的概念