3.2 队列（python版）课件（共28张PPT）浙教版（2019）高二信息技术选修1《数据与数据结构》

(共28张PPT)
3.2 队列
概念特征操作应用
情景创设
分析食堂打饭为什么需要排队，这样做有什么好处？
银行取号系统和叫号系统是怎么实现的，试着剖析其实现原理？
队列概念
是一种“先进先出”的线性表
允许插入的一端称为队尾，插入叫入队
允许删除的一端称为队首，删除叫出队
队列中的数据称为队列元素
a1 优先入队，紧接着 a2、a3...an 按照顺序依次进入
队列特征
（1）先进先出，后进后出
元素入队顺序和元素出队顺序一致
（2）有限序列性：队列元素个数有限
队列可以为空，也可以包含多个元素，
队首元素只有一个后继点，
队尾元素只有一个前驱点，
其他元素既有一个前驱点，又有一个后继点。
1.小明点的外卖下单后，订单等待被处理
2.机场安检时，排在最前面的人员被告知前往相应位置进行安检
3.由于来餐厅用餐的人数较多，餐厅让客人排队用餐
4.为控制游客的数量，管理人员告知后来的人员无法入园，不必再排队购票，已排队中的人员继续排队购票
5.经过疏导，某车道拥堵车辆已经全部放行，且现在道路上无任何车辆
A.队列满 B.入队 C.出队 D.建队 E.队列空
队列操作（建队）
例：有4个字母“A”“B”“C”“D”按序入队，可创建长度为5的队列que：
代码示例：
que=[“”]*5
head=0
tail=0
队列按顺序结构存储，通过数组实现，所以Python可使用列表创建队列
que的下标
0 1 2 3 4
0 1 2 3 4
队列操作（入队）
头指针head记录队首
尾指针tail记录队尾元素的下一个位置
que的下标
A
0 1 2 3 4
A B
0 1 2 3 4
que[tail]=”A” #A入队
tail=tail+1 #tail=1
A B
0 1 2 3 4
队列操作（入队）
头指针head记录队首
尾指针tail记录队尾元素的下一个位置
que的下标
que[tail]=”A” #A入队
tail=tail+1 #tail=1
que[tail]=”B” #B入队
tail=tail+1 #tail=2
A B C
0 1 2 3 4
队列操作（入队）
头指针head记录队首
尾指针tail记录队尾元素的下一个位置
que的下标
que[tail]=”A” #A入队
tail=tail+1 #tail=1
que[tail]=”B” #B入队
tail=tail+1 #tail=2
que[tail]=”C” #C入队
tail=tail+1 #tail=3
A B C D
0 1 2 3 4
队列操作（入队）
头指针head记录队首
尾指针tail记录队尾元素的下一个位置
que的下标
入队结束后，head=0, tail=4
que[tail]=”A” #A入队
tail=tail+1 #tail=1
que[tail]=”B” #B入队
tail=tail+1 #tail=2
que[tail]=”C” #C入队
tail=tail+1 #tail=3
que[tail]=”D” #D入队
tail=tail+1 #tail=4
队列操作（入队）程序实现
A B C D
0 1 2 3 4
队列操作（出队）
que的下标
出队，排在队首的元素依次出队，head指针变量依次加1，直至head的值等于tail的值
B C D
0 1 2 3 4
队列操作（出队）
que的下标
出队，排在队首的元素依次出队，head指针变量依次加1，直至head的值等于tail的值
C D
0 1 2 3 4
队列操作（出队）
que的下标
出队，排在队首的元素依次出队，head指针变量依次加1，直至head的值等于tail的值
D
0 1 2 3 4
队列操作（出队）
que的下标
出队，排在队首的元素依次出队，head指针变量依次加1，直至head的值等于tail的值
0 1 2 3 4
队列操作（出队）
que的下标
出队，排在队首的元素依次出队，head指针变量依次加1，直至head的值等于tail的值
当head==tail 时，队列数据出空
例.小明在使用队列解决问题的过程中，初始时（空队列），队列的队首指针hea=0，队尾指针tail=0，经过一系列入队、出队操作后，head=4，tail=7。在不考虑队列溢出的情况下，小明接下来进行的操作序列为出队、人队、出队、出队、入队、出队，此时head和tail的值分别为
练习巩固：
作业本p98第8题
给定一个字符串S1,S2,…..Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…..Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串，请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。
队列应用1：信息的加密
1. 将字符串各字符依次入队，得到队列。
算法分析，以“STRING”为例
s=input(“请输入字符串：”)
que=[“”]*100
head=0
tail=0
for i in range(len(s)):
que[tail]=s[i]
tail+=1
2. 加密字符串：出队、入队操作
先取出队首元素“S”并输出，同时head+1，队首元素变为“T”
再取出“T”，加入到队尾，队首变为“R”，队尾变为“T”，head和tail均加1
重复以上操作，直至队列为空head=tail
算法分析，以“STRING”为例
队列
que
索引 0 1 2 3 4 5 6 7 8 9 10 11
取出
取出
取出
取出
取出
取出
head=tail
队列清空
代码分析：
while headprint(que[head],end="")
head+=1
if headque[tail]=que[head]
tail+=1
head+=1
队列应用2：银行叫号排队系统
que=[-1]*1000
head=0
tail=0
print("请输入具体的操作编号：")
print("1.新到顾客（取号）")
print("2.下一个顾客（叫号）")
print("3.程序结束")
x=int(input(("请输入操作\n")))
while x!=3:
if x==1:
que[tail]=que[tail]+1
print("您当前的号码为：A%d,需要等待的人数为%d"%(tail,tail-head))
tail=tail+1
if x==2:
if head==tail:
print("对不起，没有等待的客户")
else:
print("请A%d号客户准备，马上将为您办理业务。"%(head))
head=head+1
x=int(input("请输入操作\n")) #\n表示换行读入
假溢出问题：
0 1 2 3 4
A B C D
队列q
索引
head
tail
ABC出队
E入队
E
5
6
循环队列
tail = (tail+1) % len(q)
假溢出问题：分析下列程序,输出结果
que=[""]*4
head=0
tail=0
que[tail]="A"
tail=(tail+1)%4
que[tail] = "B"
tail = (tail+1) % 4
que[tail] = "C"
tail = (tail+1) % 4
que[tail] = "D"
tail = (tail+1) % 4
que[tail] = "E"
tail = (tail+1) % 4
print(que)
结论：
假溢出现象可通过
对队列元素个数取模运算解决
['E', 'B', 'C', 'D']
队列知识总结
队列的概念及特征
队列的操作
队列的应用