3.2队列的基本操作导学案2024-2025学年高二上学期选择性必修1《数据与数据结构》第三章浙教版（2019）

3.2队列的概念与基本操作导学案 班级 姓名 一、队列的概念与特性 1.概念 队列是一种 的线性表，允许元素插入的一端称为 ，允许元素删除的一端称为 。队列中的数据元素称为 。在队列中插入一个元素称为 ，从队列中删除一个元素称为 。 队首 队尾 2.特性 ①数据具有“先进先出、后进后出”且中间不能“ ”的组织和操作的性质。 ②队列是一种线性表，元素的个数是 。队列可以是空的，也可以包含多个元素。 队首元素只有一个后继点，队尾元素只有一个 ，其他元素既有一个前驱点，又有一个后继点。 2、 单向队列的基本操作 下标/索引 0 1 2 3 queue[] 用head记录 的位置，用tail记录 的位置(即队尾元素的后继指针) 【思考】将队列元素["张","权",”赫”,”帅”]依次入队和出队，head和tail在入队和出队时的变化？ tail 下标/索引 0 1 2 3 queue[] head 入队 "张" "权" ”赫” ”帅” tail 0 出队 "张" "权" ”赫” ”帅” head 0 【思考】head与tail是何种关系时表示队满和队空？ 队满 队空 【思考】用head与tail如何表达队列中的元素个数？ 例如：head=1，tail=3时，队列中的元素个数为？ tail head 【程序实现】 #创建空队列 queue=[""]*4 #用“万金油”--列表来模拟队列 head ,tail=0,0queue=[""]*4 head ,tail=0,0 string="张权赫帅" for i in string: _____________ _____________ #入队操作 queue[tail]="张" tail=tail+1 queue[tail]="权" tail=tail+1 queue[tail]=”赫” tail=tail+1 queue[tail]=”帅” tail=tail+1 #出队操作 print(queue[head])#出"张" while _______________： print(queue[head]) head=head+1 head=head+1 print(queue[head])#出"权" head=head+1 print(queue[head])#出”赫” head=head+1 print(queue[head])#出”帅” head=head+1 【结论】队列的入队和出队的完整代码见py文件并填空。 【教材实例】编码解密：P79 已知有一串加密过的字符串。解密的规则是：首先将第一个字符删除，紧接着将第二个字符放到这串字符的末尾，再将第三个字符删除，并将第四个字符放到这串字符串的末尾，再将第五个字符删除....直到将最后一个字符删除。把这些删除的字符连在一起，得到解密后的信息。 入队后初始队列 下标/索引 0 1 2 3 4 5 6 7 ... queue[] p y t h o n tail head ①“p”出队 下标/索引 0 1 2 3 4 5 6 7 ... queue[] y t h o n tail head ②“y”出队 下标/索引 0 1 2 3 4 5 6 7 ... queue[] t h o n tail head ③“y”入队 下标/索引 0 1 2 3 4 5 6 7 ... queue[] t h o n y tail head 【程序实现】 s=input("请输入字符串：") print("加密后的串为：") que=[""]*8 head ,tail=0,0 #入队 for i in range(len(s)): ___________________ #从尾巴入队 tail=tail+1 #出队 while head<tail:#等价表达式 head!=tail print(________,end="") #从头部出队 head=head+1 if head<tail: ________________ tail=tail+1 head=head+1 【思考】程序运行后，会报以下错误（列表分配索引超出范围--下标越界），如何修改程序？ 3、 循环队列的基本操作 【已知】构造规模为4的队列后，执行4次“入队”操作，再执行2次“出队”操作后，head和tail的值分别为head=2 ，tail=4 。 下标/索引 0 1 2 3 queue[] ”赫” ”帅” tail head 此时可以再入队吗？ 即此时再执行： queue[tail]="!" tail=tail+1 运行程序后发现什么错误？ 明明队列还有空位，但新增不了元素！-----“假溢出”现象 【结论】需要构造循环队列解决这个问题。 【思考】构造规模为4的队列后，执行4次“入队”操作，再执行4次“出队”操作后，head和tail的值是如何变化的，最终head和tail的值是多少？ （1）入队操作 head head 张 tail tail 队空：head,tail=0,0 ① "张" 入队 tail=____ head tail 赫 权 张 权 tail head 张 ② "权" 入队 tail=____ ③ "赫" 入队 tail=____ tail 张 帅 赫 权 head ④ "帅" 入队 队满 head,tail=____,_____ 【结论】通过以上的图示，可以得出tail的值并不是简单的递增+1，而是：tail=___________________________（队列为queue[]） （2）出队操作 权 赫 帅 head tail 队满 head,tail=0,0 ① "张" 出队 head=____ head 帅 tail head 帅 赫 tail ② "权" 出队 head=____ ③ "赫" 出队 head=____ head tail ④ "帅" 出队 队空 head,tail=____,____ 【结论】通过以上的图示，可以得出head的值并不是简单的递增+1，而是：head=___________________________（队列为queue[]） 如此计算，tail指针的遍历依次是：_________________________________________ 【思考】通过上图图示可知，队空和队满时，都满足head = = tail，此时判断条件出现二义性，即到底head = = tail指的是队满还是队空？如何解决这个问题？ 【结论】空闲单元法 即人为浪费一个单元，把队满的特征改为：head = =（tail+1）%len（queue） 队空仍为head = = tail 头指针：head=(head+1)%len(queue) 尾指针：tail=(tail+1)%len(queue) 预备一个 空闲单元 【程序实现】 import random #建队 head,tail=0,0 queue=[0]*5 string="张权赫帅" #入队 while ________________________: for i in string: queue[tail]=i tail=(tail+1)%len(queue) #出队 while ________________: print(queue[head]) head=(head+1)%len(queue) 此程序创建的队列规模为_______，实际被使用的长度为_______。 【思考】循环队列中，tail有可能小于head吗？ 元素个数计算方法：(tail-head+n)%n (其中：n=len(queue)) 【练习1】用python模拟循环队列，并设置头指针head指向队首元素，队尾指针tail指向队尾元素的下一个位置，则当列表长度n = 10，head = 6，tail = 3时，队列中的元素个数为_____________。 【练习2】作业本P123 第4、5、6题 【练习3】约瑟夫环（用队列的方法解决） 在罗马人占领乔塔帕特后，39个犹太人与约瑟夫以及他的一位好友受困在一个洞中。因为迟早会被敌人发现，39个犹太人就决定宁愿死也不能被敌人抓住，商量了一个自杀方式：41个人围城一个圈，由第1个人开始按“123123123...”报数，每数到“3”的人必须自杀，然后再由下一个人重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的好友并不遵从，所以他将自己与朋友安排在两个特殊的位置，最终逃过了这场死亡游戏。 请你用计算机解决这个问题，补全以下代码： n,m=41,3 #下列图解修改为8人 q=[i for i in range(1,n+1)] #入队 q=[1,2,3,4,5,6,7,8] head,tail=0,0 #队满 c=0 #用来报数 while (head+1)% n!=tail：#队列人数不少于1人，修改为幸存者为1人 c=c+1 if c = = m: #满3人 head=(head+1)%n c=0 else: q[tail]=q[head] #报数不为m的出队后马上入队 tail=(tail+1)%n head=(head+1)%n print(f"最后1个幸存者的编号是{q[head]}") 【思考】如果按要求最终两个幸存者应该如何修改程序？ tail head 【理解】当c=3时，head指针后移下一位（索引为3），tail指针保持不动，即目前最后一个元素是②（tail指向的是队尾元素的下一个位置），当下一次c=1时，执行q[tail]=q[head]语句，则④出队马上入队，即③出列了。 第 1 页 共 8 页 学科网（北京）股份有限公司 $$