3.2 队列（教学课件）信息技术浙教版2019选择性必修1

第2节 队列（1课时） 第3章 字符串、队列和栈 浙教版（2019） 选修一 队列的概念与特性 01 队列的基本操作 02 学习目录 依据解决问题的需要，恰当的选择数据结构队列。 01 通过项目的实践活动，体验用队列解决问题的基本流程，逐步形成运用队列结构解决问题的思维方式和学科方法。 02 学习目标 PART 01 队列的概念与特性 新课导入 看 看 一 银行取号、食堂排队打饭 新课导入 想 想 一 银行取号系统和叫号系统是怎么实现的，试着剖析其实现原理? 问题一： 分析食堂打饭为什么需要排队，这样做有什么好处? 问题二： 新课导入 排队和取号机能按照客户或患者到达时间的先后顺序，合理地安排办事次序。 这些事件对数据的处理都具有排队的特性，可以使用队列来解决。 什么是队列？ 队列的概念与特性 一 概念 是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 已出队元素 队列元素 队首元素 队尾元素 队尾 队首 队列元素 队列的概念与特性 一 特性 （1）先进先出、后进后出 入队：在队列中插入一个元素的过程 出队：在队列中删除一个元素的过程 先进先出，后进后出 A C B 队列 队列的概念与特性 一 特性 （1）先进先出、后进后出 入队：在队列中插入一个元素的过程 出队：在队列中删除一个元素的过程 先进先出，后进后出 A C B 队列 元素入队顺序和元素出队顺序一致。 出队时，队首元素A优先出队，紧接着是B队尾元素C最后出队。 队列的概念与特性 一 特性 （2）有限序列性 队首元素：只有一个后驱节点 队尾元素：只有一个前驱节点 既有前驱，又有后驱 出队 入队 有限序列性：队列是一种线性表结构，元素的个数也是有限的 a1 a2 a3 …… an 队列的概念与特性 一 2.下列事件执行过程与队列特征不相符的是( ) A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 课堂 练习 答案：C 答案：D 1.幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适( ) A.链表 B.字典 C.字符串 D.队列 队列的基本操作 二 队列按顺序结构存储，可用数组来实现。 添加标题 数组que中存储了一个队列，共有4个元素，队首元素为a1，队尾元素为a4。 队列的存储 在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。 如上图，初始时，head指针变量与tail指针变量均记录下标为0的位置。 数组que的下标 a1 a2 a3 a4 0 1 2 3 队列的基本操作 二 提示：队列一般按顺序结构存储，可以通过数组实现。 head 记录队首元素所在的位置 tail 记录队尾元素所在位置的下一位置 a1 a2 a3 a4 0 1 2 3 4 0 1 2 3 4 tail head head tail 数组que的下标 数组que的下标 队列的head、tail指针变化图 元素a1，a2，a3，a4依次入队后，tail值为4，head值为0。 当a1，a2出队后，head记录下标为2的位置，tail值不变。当a3，a4出队后，head与tail的值均为4，队列为空。 队列的基本操作 二 队列的链式存储称为链队列，为了操作方便，可设置队首指针head记录链表的头节点，队尾指针tail记录链表的队尾节点。 拓展链接 队列的链式存储结构 空链队列： 非空链队列： head head 头节点 head 头节点 A B C D tail 尾节点 队列的链式存储结构 队列的基本操作 二 入队 建队 出队 常用操作 队列的基本操作 二 建队 假设我们现在有A”“B”“C”“D”4个字母，如何进行建队呢？ 需要几个变量？列表长度是多少？ 4 tail head 0 1 2 3 空队列 Python代码 head=0 tail=0 que=[""]*5 思考：为什么列表长度是5，而不是4呢？ 队列的基本操作 二 入队 字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪各元素的入队。 A 4 tail head 0 1 2 3 A B 4 tail head 0 1 2 3 A B C 4 tail head 0 1 2 3 A B C D 4 head 0 1 2 3 tail 队列的基本操作 二 入队 字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪各元素的入队。 入队Python代码如下 que[tail]="A" tail=tail+1 que[tail]="B" tail=tail+1 que[tail]="C" tail=tail+1 que[tail]="D" tail=tail+1 #字母A入队 #tail=1 #字母B入队 #tail=2 #字母C入队 #tail=3 #字母D入队 #tail=4 队列的基本操作 二 出队 出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。 A B C D 4 tail head 0 1 2 3 B C D 4 tail head 0 1 2 3 C D 4 tail head 0 1 2 3 出队Python代码如下 print(que[head]) # 输出A que[head]=“” head=head+1 print(que[head]) # 输出B que[head]=“” head=head+1 print(que[head]) # 输出C que[head]=“” head=head+1 队列的基本操作 二 出队 4 tail head 0 1 2 3 假 溢出 此时head=tail=4，还可以有新元素入队吗？ 队列的基本操作 二 循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。 拓展链接 循环队列 顺序队列的假溢出:随着队首元素出队会慢慢的空出一个个储存单元，但是队尾一直在进，最后导致前面的储存空间未满就队列就满了。 解决办法：将顺序队列做成循环队列！ 队列的基本操作 二 某队列分配的最大空间为5，其最后一个位置上的元素为“E”，队首指针变量head的值为4，队尾指针变量tail的值为5（tail超出了队列的边界），此时，数组中存在空闲位置，但新的元素不能入队。将该队列改为循环队列，则在元素“E”入队后， head的值为4，队尾指针重新指向队首（tail的值为0），当新元素“F”入队时，就加入到队首，然后tail的值变为1。 拓展链接 循环队列 tail超出队列的边界 循环队列 队列的基本操作 二 1.已知队列元素的个数为6，则队首指针 head 和队尾指针 tail 的值不可能的是( ) A.head=0, tail=6 B.head=6,tail=0 C.head=3,tail=2 D.head=3,tail=8 B 队列的基本操作 二 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 拓展链接 Python自带的队列模块 队列的基本操作 二 例题 信息的加密 给定一个字符串S1，S2，…，Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…SnS2；接着把S3取出，S4放到字符串的末尾S2后面……直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串（长度小于等于30），输出该字符串的密串。 队列的基本操作 二 以字符串“STRING”为例 （1） （2） 创建que队列，把字符串“STRING”按序压入队列，tail值为6，head值为0。 加密过程。先取出队首元素“S”，并输出，同时head值加1，记录新的队首元素“T”所在的位置。再取出队首元素“T”，并把该元素加入队尾，head值、tail值均加1。 加密的过程，类似队列的入队、出队操作。先把原字符串中各字符依次入队，得到一个队列，再执行加密的过程：取出队首元素，存到密串中，队列中第二个元素升级为队首元素；再取出队首元素，并把该元素插入队尾。反复操作，直至队列为空，得到密串。 步骤 （3） (3)重复操作(2)，直至队列为空。 队列的基本操作 二 前两个字母的出队、入队过程如右 队列que T R I N G 0 1 2 3 4 5 6 7 tail head 队列que R I N G 1 2 3 4 5 6 7 tail head 队列que R I N G T 0 1 2 3 4 5 6 7 tail head “S”出队 “T”出队 “T”入队 队列的基本操作 二 用Python实现的程序如下： 课堂小练 三 1.用 python 列表模拟循环队列，并设置队首指针head指向队首元素，队尾指针指向队尾元素的下一个位置,则当列表长度 n=10，head=6，tail=3 时，队列中元素的个数为( ) A.5 B.6 C.7 D.8 2.已知队列(4，21，55，66，48，24，35，12，78，5)第 一个进入队列的元素是4，请问第3个出队列的元素是( ) A.35 B.12 C.55 D.5 D C 小结 四 小 结 队列的概念与特性 队列的基本操作 队列 1.建队 2.入队、出队 1.队列的概念 2.队列的特性 ①先进先出、后进后出 ②有限序列性 谢谢观看 第2节 队列 浙教版（2019） 选修一 $$