资源简介

(共15张PPT)
3.2队列
生活中的队列
按照到达时间的先后顺序，合理地安排办事次序。这些事件对数据的处理具有排队的特性，可以使用队列来解决。
出队：从队首中_______一个元素称为出队。
队列是一种__________的线性表，允许插入的一端称为______，允许删除的一端称为_______。队列中的数据元素称为______________。
入队：在队尾中_______一个元素称为入队；
先进先出
队尾
队首
队列元素
插入
删除
出队
入队
队首元素
队尾元素
先进先出、后进后出
一、队列的概念
二.队列的特性
出队
入队
队首元素
队尾元素
只有一个后继点
只有一个前驱点
一个前驱&一个后继
特性一：
特性二：
有限序列性
队列也是一种线性表结构，元素个数是有限的。
先进先出、后进后出
图1
图2
下列事件执行过程与队列特征不相符的是 ( )
A.在汽车加油站排队加油时不允许插队
B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓
冲区
C.把书叠放成一摞，最底下的书要最后才能拿出来
D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”
工作的假象
练习1
C
解析：C选项中最底下的书是最先放入，但要最后才能拿出来，是先进后出，不符合队列先进先出的特性。
队列一般按顺序结构存储的，可以用数组来实现。
如图所示：数组que中存储了一个队列、共有4个元素，队首元素为a1，队尾元素为a4。
a1 a2 a3 a4
0 1 2 3
数组que的下标
在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的______位置。
三、队列的基本操作
队首元素
队尾元素
head
tail
下一个
问题1：在Python语言中如何表示队列？
问题2：如何描述队列入队和出队过程？
活动1.建队：如：有4个字母“A”“B”“C”“D”按序入队、出队时，可以创建一个队列que，长度为5,
head=0tail=0que=[""]*5
0 1 2 3 4
数组que的下标
head
tail
程序实现：
队列为空？
head==tail
初始时，head=tail=0
活动2.入队：
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
0 1 2 3 4
数组que的下标
head
程序实现：
队非空判断条件：
(head!=tail)
A
B
C
D
tail
头指针head记录队首位置
尾指针tail记录队尾元素的下一个位置
队内元素个数=
tail-head
head重大发现
接收入队元素的变量：
que[tail]
活动3.出队：
0 1 2 3 4
数组que的下标
head
程序实现
(将出队的元素存入数组s中)：
D
tail
排在队首的元素依次出队，head指针变量依次加1；
直至______________，说明全部出队，队列为空
C
B
A
s="" while head != tail :
__________________ __________________ print(s)
head==tail
s=s+que[head]
head+=1
判断队列为空的条件：
head==tail
出
出
出
出
每次出队的元素是：
que[head]
a=["a", "b", "c", "d", "e", "f"]q = [0] * 5head = tail = 0
for i in range(5): q[tail] = a[i] tail += 1while head != tail: print(q[head], end=" ") head += 1
输出结果为 :_________________
练习2
# 建立空队列
# 元素依次入队
# 元素依次出队，
直至队列为空
a b c d e f
原顺序输出
1.信息的加密：给定一个字符串S1,S2,…..Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…..Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串，请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。
四、队列的应用
队首取数，队尾插入数
（1）抽象与建模：
思考：加密的过程，符合什么数据结构的特征？
队列
1.信息的加密：
（2）设计算法：以字符串“STRING”为例
①将字符串各字符依次入队，得到队列，tail值为6，head值为0。
四、队列的应用
②加密过程。先取出队首元素“S”，并输出，同时head值加1，记录新的队首元素“T”所在的位置。再取出队首元素“T”，并把该元素加入队尾，head值、tail值均加1。
0 1 2 3 4 5 6 7 8 9 10 11
head
tail
S
T
R
I
N
G
出
出
出
出
出
出
③重复操作②，直至队列为空。
（3）算法实现，在划线处填入正确的语句s=input("请输入字符串：")print("加密后的串为：")
que=[""]*100head=0tail=0for i in range(len(s)):
_________________
tail+=1print(que)while _______________: print(que[head],end="") head+=1 if head_____________________
tail+=1
head+=1
# 建立空队列
#原串入队
#队列非空时,
1-q[head]出队
2-出队的元素加入队尾
que[tail]=s[i]
head！=tail
que[tail]=que[head]
先进先出的线性表
队尾、队首的概念
入队、出队的概念
队列的概念
建空队列\入队\出队
队列的基本操作
先进先出
有限序列性
队列的特性
信息的加密
……
队列的应用
课堂小结
队列为空：head==tail
队列非空：head!=tail
队列元素 个数=tail-head
谢谢观看！

展开更多......

收起↑