高中信息技术浙教版：3-2 队列-教学课件.pptxVIP

3.2队列生活中的队列按照到达时间的先后顺序，合理地安排办事次序。这些事件对数据的处理具有排队的特性，可以使用队列来解决。一、队列的概念队尾先进先出队列是一种__________的线性表，允许插入的一端称为______，允许删除的一端称为_______。队列中的数据元素称为______________。队列元素队首队首元素队尾元素出队入队插入入队：在队尾中_______一个元素称为入队；先进先出、后进后出删除出队：从队首中_______一个元素称为出队。二.队列的特性只有一个前驱点只有一个后继点队首元素队尾元素一个前驱一个后继出队入队图2图1特性一：先进先出、后进后出特性二：有限序列性队列也是一种线性表结构，元素个数是有限的。练习1下列事件执行过程与队列特征不相符的是()A.在汽车加油站排队加油时不允许插队B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区C.把书叠放成一摞，最底下的书要最后才能拿出来D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象C解析：C选项中最底下的书是最先放入，但要最后才能拿出来，是先进后出，不符合队列先进先出的特性。三、队列的基本操作队列一般按顺序结构存储的，可以用数组来实现。问题1：在Python语言中如何表示队列？如图所示：数组que中存储了一个队列、共有4个元素，队首元素为a1，队尾元素为a4。队首元素队尾元素a1a2a3a40123数组que的下标tailhead问题2：如何描述队列入队和出队过程？在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的______位置。下一个活动1.建队：如：有4个字母“A”“B”“C”“D”按序入队、出队时，可以创建一个队列que，长度为5,

初始时，head=tail=0tail程序实现：headhead=0tail=0que=[]*5

01234数组que的下标head==tail队列为空？活动2.入队：头指针head记录队首位置尾指针tail记录队尾元素的下一个位置程序实现：tailheadque[tail]=”A”#A入队tail=tail+1#tail=1que[tail]=”B”#B入队tail=tail+1#tail=2que[tail]=”C”#C入队tail=tail+1#tail=3que[tail]=”D”#D入队tail=tail+1#tail=401234CDAB数组que的下标que[tail]接收入队元素的变量：队非空判断条件：headtail(head!=tail)队内元素个数=tail-head重大发现活动3.出队：排在队首的元素依次出队，head指针变量依次加1；直至______________，说明全部出队，队列为空head==tailtail程序实现(将出队的元素存入数组s中)：head01234ABCDs=whilehead!=tail:

____________________________________print(s)

数组que的下标s=s+que[head]出出出出head+=1head==tail判断队列为空的条件：que[head]每次出队的元素是：练习2a=[a,b,c,d,e,f]q=[0]*5head=tail=0

foriinrange(5):q[tail]=a[i]tail+=1whilehead!=tail:print(q[head],end=)head+=1

#建立空队列#元素依次入队#元素依次出队，直至队列为空原顺序输出abcdef输出结果为:_________________四、队列的应用1.信息的加密：给定一个字符串S1,S2,…..Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…..Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串，请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。（1）抽象与建模：思考：加密的过程，符合什么数据结构的特征？队列队首取数，队尾插入数四、队列的应用1.信息的加密：（2）设计算法：以字符串“STRING”为例①将字符串各字符依次入队，