资源简介

(共25张PPT)
3.2 队列
生活中的队列
我们在生活中去超市购物、影院取票都需要排队。去银行、医院办理业务时，取号机能按照到达时间的先后顺序，合理地安排办事次序。
这些事件对数据的处理都具有先到先处理的特性，可以使用队列来解决。
队列的概念
一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。
学号1
学号2
学号3
学号4
学号5
学号6
队首
队尾
入队
出队
队列元素：队列中的数据元素
入 队：在队列中插入一个元素的过程
出 队：从队列中删除一个元素的过程
队列的特性
（1）先进先出、后进后出
由队列的定义可知，队列具备“先进先出、后进后出”的特点。
如图所示，出队时，队首元素a1优先出队，紧接着是a2,a3,……,an-1 ，队尾元素an最后出队。
出队
入队
队首元素
队尾元素
队列的特性
出队
入队
队首元素
队尾元素
只有一个后继点
只有一个前驱点
一个前驱&一个后继
（2）有限序列性
队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征。
队列的小练习
1. 幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适（ ）
A.链表 B.字典 C.字符串 D.队列
2.下列事件执行过程与队列特征不相符的是（ ）
A.在汽车加油站排队加油时不允许插队
B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区
C.把书叠放成一摞，最底下的书要最后才能拿出来
D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象
D
C
队列的基本操作
1 队列的存储结构
队列一般按顺序结构存储，可以用数组来实现，也可以用链式存储结构存储，这被称为链队列。
0 1 2 3 4
tail
head
tail记录链表的队尾节点
head记录链表头节点
头节点
队列的基本操作
下面队列的模拟采用数组来实现。例如“A”“B”“C”“D”要实现按顺序入队、按顺序出队时候，可以创建一个队列que，长度为5，python代码如下：
0 1 2 3 4
2 建队
n=5
head=0
tail=0
que=[""]*n
tail
head
队列的基本操作
字母“A”“B”“C”“D”按顺序入队的python代码如下：
3 入队
0 1 2 3 4
tail
head
tail+=1
que[tail] ="B"
tail+=1
que[tail] ="C"
tail+=1
que[tail] ="D"
tail+=1
A
B
C
D
注意：tail到达最大下标时不能再增加，队列已满！
队列中最多存储n-1个元素
que[tail] ="A"
队列的基本操作
0 1 2 3 4
tail
head
3 入队
队列为空的条件：_________
head==tail
队列的基本操作
0 1 2 3 4
tail
head
3 入队
head记录队首元素所在的位置，tail记录队尾元素的下一个位置。
0 1 2 3 4
A B C D
tail
head
队列为空的条件：_________
队列已满的条件：___________
head==tail
tail==n-1
队列的基本操作
字母“A”“B”“C”“D”按顺序出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。
4 出队
0 1 2 3 4
tail
head
while ______________:
print(que[head])
que[head] =""
head +=1
A
B
C
D
#队列非空时
head != tail
队列的“假溢出”问题
根据上面的操作，我们发现此时在顺序队列中tail=4,已经无法在插入数据，但实际上que[0]的数据已经出队，存储空间可用，这种情况便称之为“假溢出”。
循环队列：将队列的队首和队尾连接起来，形成逻辑上的环状结构。
队列的“假溢出”问题
根据上面的操作，我们发现此时在顺序队列中tail=4,已经无法在插入数据，但实际上que[0]的数据已经出队，存储空间可用，这种情况便称之为“假溢出”。
循环队列：将队列的队首和队尾连接起来，形成逻辑上的环状结构。
解决二义性问题：
为区分队空和满，会在队尾留一个空闲的数据单元，循环队列最多可放n-1个数据元素。
队列的“假溢出”问题
0 1 2 3 4
tail
head
C
D
0 1 2 3 4
tail
head
E
C
D
顺序队列
0 1 2 3 4
tail
head
C
D
0 1 2 3 4
tail
head
E
C
D
循环队列
×
F
循环队列的基本操作
if _______________________ :
q[tail]="E"
tail=(tail+1)%n
#当队伍未满的时候，可入队
head!=(tail+1)%n
while head!=tail:
print(que[head])
head=________________
#若队伍非空，可出队
(head+1) %n
#循环队列实现空间利用需要使用%形成环
顺序队列和循环队列里的元素个数
顺序队列：
... 3 4 5 6 7 n-1
tail
head

head=3，tail=6，元素个数为3
顺序队列的个数=tail-head


顺序队列和循环队列里的元素个数
循环队列：
①当head0 1 2 3 4 5 6 7



tail
head



元素个数为6,个数=tail-head+n个
个数计算通用公式
=（tail-head+n)%n
②当head>tail
队列的应用：银行叫号排队系统
第一章中的“银行叫号排队系统”就可以用队列的结构，实现入队（取号）、出队（叫号）的系统功能。
队列的应用：银行叫号排队系统
第一章中的“银行叫号排队系统”就可以用队列的结构，实现入队（取号）、出队（叫号）的系统功能。
银行叫号排队系统的算法
①建立队列que存储客户取的号，设置队首指针变量为head，队尾tail的值
开始
que=[“”]*1000；head=tail=0
②输入x存储输入的数字，x等于1，实现取号，x等于2实现叫号，x等于3程序退出
x!=3
输入x
结束
NO
YES
③当x=1时候，新客户入队并显示需要等待的人数④当x=2时候，若队列为空，则显示无等待的人员；否则，que队首元素出队，并显示办理业务的号码。
x==1
YES
入队并计算等待人数
NO
x==2
que空？
出队
YES
YES
显示无等待
队列的应用代码实现
que=[-1]*1000;head=0;tail=0
print("请输入具体的操作编号：")
print("1.新到顾客（取号）")
print("2.下一个顾客（叫号）")
print("3.程序结束")
x=int(input(("请输入操作\n")))
while x!=3:
if x==1:
__________________________
print("您当前的号码为：A%d,需要等待的人数为%d"%(tail,tail-head))
tail=tail+1
if x==2:
if ____________:
print("对不起，没有等待的客户")
else:
print("请A%d号客户准备，马上将为您办理业务。"%(head))
head=head+1
x=int(input("请输入操作\n")) #\n表示换行读入
#取号即入队
que[tail]=que[tail]+1
head==tail
#先判断是否有人等待
#队列中有人等待就出队
#号码是递增的
#等待人数计算
Python中自带的队列模块
import queue
q=queue.Queue(10)
q.put("A")
q.put("B")
print(q.size())
print(q.get())
#导入队列模块
#建一个长度为10的队列
#字母“A”入队
#输出队列中元素的个数
#队首元素出队
#字母“B”入队
队列的小总结
1.概念
一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。
2.队列的基本操作
入队和出队注意head和tail的变化
3.python中自带的队列模块queue
Queue、put、size()、get()等等……
谢谢观看，下课！

展开更多......

收起↑