资源简介

(共21张PPT)
选择性必修1《数据与数据结构》
第三章 字符串、队列和栈
3.2 队列的概念、特性及基本操作
情境导入
知识讲解
1.队列的概念
队首
队尾
2.队列的特性
先进先出、后进后出
有限序列性
队首：一个后继
队尾：一个前驱
已出队元素
既有前驱又有后继
队列-基本操作
队列的概念
队首：允许删除的一端
队尾：允许插入的一端
返回
3.2.2 队列的基本操作
队列一般按顺序结构存储，可以用数组来实现。
如图3.2.2所示，数组que（4个元素）：队首元素为，队尾元素为。
由于需要入队和出队，队首元素和队尾元素在数组que中的位置在改变。因此设置头指针变量head和尾指针变量tail，head指向队首元素所在的位置，tail指向队尾元素的下一个位置。
0 1 2 3
数组que的下标
图3.2.2 队列的存储
3.2.2 队列的基本操作
0 1 2 3
数组que的下标
图3.2.3 队列的head、tail指针的变化图
初始时，head指针变量与tail指针变量均指向下标为0的位置。
队列元素,均入队后，tail指向下标为4的位置，head指向位置不变。
0 1 2 3 4
数组que的下标
head
tail
0 1 2 3 4
数组que的下标
head
tail
tail指向队尾元素的下一个位置


图3.2.2 队列的存储
3.2.2 队列的基本操作
0 1 2 3 4
数组que的下标
head
tail
0 1 2 3 4
head
tail
图3.2.3 队列的head、tail指针的变化图
数组que的下标
tail指向队尾元素的下一个位置


当后，head记录下标为2的位置，tail值不变。
当后，head与tail的值均为4，队列为空。
head
队列的基本操作
1.建队
head=0
tail=0
que=[“ ”]*5
2.出队、入队
A
0 1
A B
0 1 2
A B C
0 1 2 3
A B C D
0 1 2 3 4
tail
tail
tail
tail


队列的基本操作
A
0 1
A B
0 1 2
A B C
0 1 2 3
A B C D
0 1 2 3 4
2.出队、入队
tail
tail
tail
tail


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值时，队列为空。
为了解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。计算机将所有的打印任务依次写入缓冲区，以便打印机按序打印。数据缓冲区中的数据如何存储及构造
问题与讨论
按时间指令排队打印——队列
拓展链接
循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。有效解决“有空闲位置不能入队”的问题。
某队列分配最大空间为5，其最后一个位置上的元素为”E“,队首指针变量head的值为4，队尾指针变量tail的值为5（tail超出队列的边界）。
此时，数组中存在空闲位置，但新的元素不能入队。
改为循环队列，则在元素“E”入队后，head的值为4，队尾指针重新指向队首（tail=0）,当新元素“F”入队后，就加入到队首，然后tail 的值变为1,如图所示。
循环队列
E
0
1
2
3
4
E
0
1
2
3
4
F
tail
tail
head
head
例1 信息的加密（字符串：S1，S2，…，Sn）
按如下过程加密:
取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn 后面，得到字符串S3…SnS2;
接着把S3取出，S4放到字符串的末尾Sn后面……直到最后一个字母Sn被取出。
这些字母按取出的顺序形成一个新的字符串，称为密串。
【此加密过程：取出队首元素，存到秘串中，队列中第二个元素升级为队首元素；再取出队首元素，并把该元素插入队尾。】
以“STRING”为例：
T R I N G
0 1 2 3 4 5 6 7
R I N G
0 1 2 3 4 5 6 7
R I N G T
0 1 2 3 4 5 6 7
head
tail
head
head
tail
tail
例1 信息的加密（字符串：S1，S2，…，Sn）
程序 测试结果
s=input("请输入字符串:") print("输入后的字串为：") que=[""]*100 head=0 tail=0 for i in range(len(s)): #将原串全部压入队列 que[tail]=s[i] tail+=1 while head输入后的字串为：Ptoynh
银行叫号排队系统
什么情况下适合采用“队列”解决？？？
若问题中存在“先进先出，后进后出”的特性，即可用“队列”解决问题。
①建立队列que，队列的初始长度设置为1000，初始值均为-1；设置head=tail=0。
②设计输入提示界面，实现多次取号和叫号功能。
用X存储输入的数字，如果X等于1，实现取号功能; X等于2，实现叫号功能; X等于3时，程序退出。
③当x=1时，分配一个号码，入队指针tail+1，并显示需要等待的人数。
④当x=2时，先判断que队列是否为空。若为空，则显示无等待的人员;否则，que队首元素出队，head+1，并显示可以办理业务的客户号码。
银行叫号系统
为了简要实现“银行叫号排队系统”的功能，把取号、叫号流程集中到一个输入界面上，用队列que存储用户取的号
程序 测试结果
que=[-1]*1000 head=0 tail=0 print("请输入具体的操作编号：") print("1.新到顾客（取号）") print("2.下一个顾客（取号）") print("3.程序结束") x=int(input()) 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")) >> %Run 22222.py
请输入具体的操作编号：
1.新到顾客（取号）
2.下一个顾客（取号）
3.程序结束
1
您当前的号码为：A0,需要等待的人数为0
请输入操作
1
您当前的号码为：A1,需要等待的人数为1
请输入操作
2
请A0号客户准备马上将为您办理业务。
请输入操作
3
拓展链接
Python自带的队列模块
Python中自带了队列模块，可以实现队列的建队、入队、出队等操作，代码如下：
import queue #引入队列模块
q=queue.Queue(10) #建一个长度为10的队列q
q.put(“A”) #字母“A”入队
q.put(“B”) #字母“B”入队
print(q.qsize( )) #输出队列中元素的个数，个数为2
print(q.get( )) #队首元素出队，出队元素为“A”
print(q.qsize( )) #输出队列中的元素个数，个数为1
思考与练习
1.当需要统计队列中元素的个数时,如何统计 请编程实现
2.给定一个能存储100个元素的队列,可用的下标为0到99,队列中tail指针变量指向下标99，head指针变量指向下标51。再插入一个元素时,提示“队列空间不够,无法入队”。由tail指针变量和head指针变量的值可知,队列中的第1位置至第50位置是空的。由此说明提示信息为“假溢出”。请描述队列出现“假溢出”现象的原因,并给出解决办法。
队列的概念
队列的特性
队列的基本操作
队列的简单应用
课堂小结
返回
实践任务
要求：约瑟夫问题的队列实现
n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，……，1，2，3，……”报数，报到m(m>1)的人退出圈子。这样不断循环下去，圈子里的人数将不断减少。请按序输出出圈的编号。
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能从新课导入中的对比图中感知队列的应用。 5 4 3 2 1 5 4 3 2 1
能理解队列的概、特性。 5 4 3 2 1 5 4 3 2 1
能自主学习教材中“队列的基本操作”，并迁移完成队列的出队操作。 5 4 3 2 1 5 4 3 2 1
能利用队列的基本操作，解决一些简单的含有入队、出队等思想的问题。 5 4 3 2 1 5 4 3 2 1
谢谢观看

展开更多......

收起↑