3.2队列课件-2021-2022学年浙教版（2019）高中信息技术选修1（21张PPT）

(共21张PPT)
3.2 队列
去银行、医院办理业务时，取号机能
按照到达时间的先后顺序，合理地安
排办事次序。
这些事件对数据的处理都具有排队的
特性，可以使用队列来解决。
队列的概念与特性
一、队列的概念
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。
队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个
元素称为出队。
n1
n2
n3
n4
nn
…
队尾元素
队首元素
入队
出队
图1
二、队列的特性
（1）先进先出、后进后出
由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图1所示，
出队时，队首元素n1优先出队，紧接着是n2,n3,…nn，队尾元素nn最后出队。
（2）有限序列性
队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含
多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素
只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。
队列的基本操作
队列一般按顺序结构存储，可以用数组来实现。如下图所示，数组que中存储了一个
队列、共有4个元素，队首元素为a1，队尾元素为a4。由于在入队和出队的过程中，
队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾
指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。
a1 a2 a3 a4
0 1 2 3
队列的存储
a1 a2 a3 a4
0 1 2 3 4
0 1 2 3 4
tail
head
数组que的下标
head
tail
队列的head、tail指针变化图
对于下图所示的队列，初始时，head指针变量与tail指针变量均记录下标为
0的位置。元素a1、a2、a3、a4依次入队后，tail值为4,head值为0。
当a1、a2出队后，head记录下标为2的位置，tail值不变。当a3、a4出队后，
head与tai的值均为4，队列为空。
队列的常用操作有建队、入队、出队等。
1.建队
由于队列以数组形式存储，因此python中用列表创建队列。例如，有4个字母
“A”“B”“C”“D”按序入队、出队时，可以创建一个队列que，长度为5，
python代码如下所示：
head=0
tail=0
que=[“”]*5
2.入队、出队
字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪
各元素入队。如下图所示：
A
0 1
tail
A B
0 1
tail
A B C
0 1 2 3
tail
A B C D
0 1 2 3 4
tail
（1）
（2）
（3）
（4）
入队的Python代码如下：
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
出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。
拓展链接：循环队列
循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列
中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有
位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。
E
0
1
2
3
4
下标
head
tail
tail超出队列的边界
如上图所示，某队列分配的最大空间为5，其最后一个位置上的元素为
“E”，队首指针变量head的值为4，队尾指针变量tail的值为5（tail超
出了队列的边界），此时，数组中存在空闲位置，但新的元素不能入队。
将队列改为循环队列，则在元素“E”入队后，head的值为4，队尾
指针重新指向队首（tail的值为0），当新元素“F”入队时，就加入
到队首，然后tail的值变为1。如下图所示。
0
1
2
3
4
E
head
tail
①“E”入队
0
1
2
3
4
head
tail
E
F
②“F”入队
循环队列
队列模块queue
在python中有自带的队列模块queue，方法如下。
代码 说明
import queue 导入队列模块
q=queue.Queue(5) 建立一个长度为5的队列q
q.put(1) 将数字1入队
q.qsize() 输出队列中元素的个数
q.get() 队首元素出队
队列的应用
例：信息的加密
给定一个字符串S1，S2，…，Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…SnS2；接着把S3取出，S4放到字符串的末尾S2后面……直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。
加密的过程，类似队列的入队、出队操作。先把原字符串中各字符
依次入队，得到一个队列，再执行加密的过程：取出队首元素，存
到密串中，队列中第二个元素升级为队首元素；再取出队首元素，
并把该元素插入队尾。反复操作，直至队列为空，得到密串。
以字符串“STRING”为例，算法步骤如下：
①创建que队列，把字符串“STRING”按序压入队列，tail值为6，head值为0。
②加密过程。先取出队首元素“S”，并输出，同时head值加1，记录新的队首元素“T”所在的位置。再取出队首元素“T”，并把该元素加入队尾，head值、tail值均加1。
③重复操作②，直至队列为空。
前两个字母的出队、入队过程如下图所示：
队列 que T R I N G
0 1 2 3 4 5 6 7
head
tail
①“S”出队
队列 que R I N G
1 2 3 4 5 6 7
②“T”出队
head
tail
队列 que R I N G T
0 1 2 3 4 5 6 7
head
tail
③“T”入队
用python 实现的完整程序及测试结果：
s=input(“请输入字符串：”)
print(“加密后的串为：”)
que=[“”]*100
head=0
tail=0
for i in range(len(s)): #把原串全部压入队列
que[tail]=s[i]
tail+=1
While headprint(que[head],end=“”)
head+=1
if headque[tail]=que[head]
tail+=1
head+=1
请输入字符串：
Python
加密后的串为：
Ptoynh
练一练
1.依次在初始为空的队列中将元素“h”，“e”，“l”，“l”，“o”
入队以后，紧接着做了两次删除操作，此时的队首元素是：
A.“h” B.“e” C.“l” D.“o”
C
2.有如下python 程序段，使用长度为3的列表q模拟队列的出队
入队活动：
q=[1,2,3]
ys=[]
for i in range(4,10):
ys.append(q[0])
q[0]=q[1]
q[1]=q[2]
q[2]=i
print(ys,q)
程序运行结束后，列表ys中元素的数量为___________。
6
3.有如下python程序段：
from queue import Queue
q=Queue(5)
print(“能存放的最多元素个数=”,q.maxsize)
for i in range(q.maxsize):
q.put(3*i)
print(“是否满：”,q.full())
for i in range(q.qsize()):
print(“当前实际长度=”,q.qsize())
print(“取出元素：”,q.get())
从队列中取出的元素依次是________________。
0,3,6,9,12
谢 谢