3.2队列第三章 字符串、队列和栈 课件-2021-2022学年浙教版(2019)高中信息技术选修1

1、3.2队列浙教版新教材(2019)数据与数据结构选择性必修13.2队列温故知新一、队列的概念及特性 概念：一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 特性：先进先出、后进后出 FIFO 有限序列性队列是一种线性表结构，元素个数有限。队列可以为空。 队列中所有元素呈线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。头啊付月月章鼎昊李帅宋炜涛陈悦队首队尾先进先出，即队首出队尾入入队出队课堂练习1.幼儿园小朋友们排队玩华护体，轮流爬上去，再轮流滑下来，此过程用那种数据结构描述最合适（ ） A.链表 B.字典 C.栈 D.队列

2、D课堂练习2.下列事件执行过程与队列特征不相符的是（ ） A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象C二、队列的基本操作存储建队入队出队存储 队列的存储结构：顺序结构存储（线性表结构），可以用数组来实现。 头指针head: 记录队首元素位置 尾指针tail: 记录队尾元素的下一个位置 初始时，head和tail 均记录下标为0的位置栈的存储(top)头啊付月月章鼎昊李帅宋炜涛陈悦head

3、tail存储 队列的链式存储结构建队 队列可以用数组来实现，python中数组通常用列表实现。头啊付月月章鼎昊李帅宋炜涛陈悦建队：head=0tail=0que=*6建栈：top=-1stack=*6VShead=0tail=0头啊付月月章鼎昊李帅宋炜涛陈悦第一个元素入队：quetail=“头啊“tail=tail+1入队head=0tail=0tail=1头啊付月月章鼎昊李帅宋炜涛陈悦第二个元素入队：quetail=“付月月“tail=tail+1入队head=0tail=1tail=2第三、四、五、六个元素入队：quetail=“章鼎昊“tail=tail+1quetail=“李帅“tai

4、l=tail+1quetail=“宋炜涛“tail=tail+1quetail=“陈悦“tail=tail+1入队头啊付月月章鼎昊李帅宋炜涛陈悦tail终值是？头啊付月月章鼎昊李帅宋炜涛陈悦head=0tail=6与入栈方式类似入队头啊付月月章鼎昊李帅宋炜涛陈悦#建队head=tail=0que=*6#入队for i in “头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦“： quetail=i tail+=1出队头啊付月月章鼎昊李帅宋炜涛陈悦head=0tail=6#建队head=tail=0que=*6#入队for i in “头啊“, “付月月“, ”章鼎昊“,

5、”李帅“, ”宋炜涛“, ”陈悦“： tail+=1 quetail=i#出队while head!=tail: print(quehead) head+=1head=6head=3时，队列中有几个元素？#建队head=tail=0que=*6#入队for i in “头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦“： quetail=i tail+=1#出队while head!=tail: print(quehead) head+=1#建栈：top=-1stack=*6#入栈：for i in “头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦

6、“： top+=1 stacktop=i#出栈：while top-1: print(stacktop) top-=1VS头啊付月月章鼎昊李帅宋炜涛陈悦头啊付月月章鼎昊李帅宋炜涛陈悦#建队head=tail=0que=#入队for i in 头啊, 付月月, 章鼎昊, 李帅, 宋炜涛, 陈悦: que.append(i)#出队tail=len(que)while len(que)!=0: print(que.pop(head)print(que)#建栈：top=-1stack=#入栈：for i in 头啊, 付月月, 章鼎昊, 李帅, 宋炜涛, 陈悦: stack.append(i)#出栈：

7、while len(stack)!=0: print(stack.pop()print(stack)VS头啊付月月章鼎昊李帅宋炜涛陈悦头啊付月月章鼎昊李帅宋炜涛陈悦课堂练习3.判断一个长度为n的队列q为空的条件是（ ） A.head=0 B.tail=0 C.tail=-1 D.head=tailD4. 用python列表模拟队列，并设置队头指针head指向队首元素，队尾指针tail指向队尾元素的下一个位置，则当head=3，tail=6时，队列中元素的个数为（ ） A.3 B.4 C.5 D.6A课堂练习作业本P98p1p44tail+=1qtail= p2tail+=1qtail = p3

8、tail+=1qhead, 出队head+=1qheadtail-head请精简代码课堂练习4作业本P97课堂练习tail+1head!=tail 或其他等价答案head+1课堂练习书P30D课堂练习有如下python 程序段，使用长度为3的列表q模拟队列的出队入队活动：q=1,2,3ys=for i in range(4,10): ys.append(q0) q0=q1 q1=q2 q2=iprint(ys,q)程序运行结束后，列表ys中元素的数量为_。6课堂练习例：信息的加密1. 将字符串各字符依次入队，得到队列。s=input(“请输入字符串：”)que=*100head=0tail=0

9、for i in range(len(s): quetail=si tail+=1 给定一个字符串S1,S2,.Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3.Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串，请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。2. 以 “STRING”为例，该字符串压入队列后先取出队首元素“S”并输出，同时head+1，队首元素变为“T”再取出“T”，加入到队尾，队首变为“R”，队尾变为“T”，h

10、ead和tail均加1重复以上操作，直至队列为空队列que索引01234567891011headtailSTRING取出ST取出RI取出NG取出TI取出GI取出Ihead=tail队列清空用数组（列表）模拟的队列真的清空了么？三、循环队列头啊付月月章鼎昊李帅宋炜涛陈悦head=0tail=6head=6定义的列表是否为空？是否能入队？循环队列： 将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。尝试设计三、循环队列#建队head=tail=0que=*

11、6#入队for i in “头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦“： quetail=i tail+=1#出队while head!=tail: print(quehead) head+=1付月月章鼎昊李帅宋炜涛陈悦头啊#建队head=tail=0que=*6#入队for i in “头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦“： quetail=i tail=(tail+1)%len(que)#出队while ?: print(quehead) head=(head+1)%len(que)三、循环队列import random#建

12、队head,tail=0,0que=0*6#入队While head!=(tail+1)%len(q): qtail=random.randint(1,9) tail=(tail+1)%len(q)#出队while head!=tail: print(quehead) head=(head+1) %len(q)三、循环队列数组中预备一个空闲单元课堂练习C课堂练习已知队列元素的个数为6，则队首指针head和队尾指针tail的值不可能的是（ ） A.head=0，tail=6 B. head=6，tail=0 C. head=3，tail=2 D. head=3，tail=8D10课堂练习书P30课堂练习(head+1)% n或其他等价答案qtail=qheadc=0课堂练习例：信息的加密1. 将字符串各字符依次入队，得到队列。s=input(“请输入字符串：”)que=*100head=0tail=0for i in range(len(s): quetail=si tail+=1 给定一个字符串S1,S2,.Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3.Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn被取出。这些字母按取出的顺