3.2队列 课件-2023—-2024学年浙教版（2019）高中信息技术选修1

第三章 字符串、队列和栈 选修一《数据与数据结构》 3.2 队列的概念、特性与基本操作 1 队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。 队列是什么？ 太抽象了，无法理解 队列是什么？ 队尾 队首 队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。 队列中的数据被称为队列元素 队列元素 先进先出 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 A C B 队列 队列的特性 一、先进先出，后进后出 元素入队顺序和元素出队顺序一致。 二、有限序列性：队列元素个数有限 队列可以为空，也可以包含多个元素，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 A C B 前驱点 后继点 队列 前驱节点 后继节点 链表 A C B 队列 队列的基本操作 自主学习：阅读课本P70-P71，思考如何使用Python完成队列的建队、入队和出队操作呢？ 提示：队列一般按顺序结构存储，可以通过数组实现 a1 a2 a3 a4 0 1 2 3 数组下标 队列存储 队列的基本操作 提示：队列一般按顺序结构存储，可以通过数组实现 a1 a2 a3 a4 0 1 2 3 数组下标 队列存储 head 记录队首元素所在的位置 tail 记录队尾元素所在位置的下一位置 0 1 2 3 4 tail head 空队列 0 1 2 3 4 tail head 入队 队列的基本操作 提示：队列一般按顺序结构存储，可以通过数组实现 a1 a2 a3 a4 0 1 2 3 数组下标 队列存储 0 1 2 3 4 tail head 空队列 a1 0 1 2 3 4 tail head 入队 head 记录队首元素所在的位置 tail 记录队尾元素所在位置的下一位置 队列的基本操作 提示：队列一般按顺序结构存储，可以通过数组实现 a1 a2 a3 a4 0 1 2 3 数组下标 队列存储 0 1 2 3 4 tail head 空队列 a1 a2 0 1 2 3 4 tail head 入队 a1 a2 0 1 2 3 4 tail head 出队 head 记录队首元素所在的位置 tail 记录队尾元素所在位置的下一位置 队列的基本操作 提示：队列一般按顺序结构存储，可以通过数组实现 0 1 2 3 4 tail head 空队列 a1 a2 0 1 2 3 4 tail head 入队 a2 0 1 2 3 4 tail head 出队 head 记录队首元素所在的位置 tail 记录队尾元素所在位置的下一位置 a1 a2 a3 a4 0 1 2 3 数组下标 队列存储 队列的基本操作 0 1 2 3 4 tail head 空队列 a1 a2 0 1 2 3 4 tail head 入队 a2 0 1 2 3 4 tail head 出队 自主学习：阅读课本P70-P71，思考如何使用Python完成队列的建队、入队和出队操作呢？ 假设我们现在有“A”“B”“C”“D”4个字母，如何实现建队、入队、出队呢？ 队列的基本操作-建队 假设我们现在有“A”“B”“C”“D”4个字母，如何进行建队呢？ 思考2个问题：一、需要几个变量？二、列表长度是多少？ 0 1 2 3 4 tail head 空队列 Python源码 head=0 tail=0 que=[“”]* 5 【课后思考】为什么列表长度是5，而不是4呢？ 队列的基本操作-入队 A 0 1 2 3 4 tail head ① A B 0 1 2 3 4 tail head ② A B C 0 1 2 3 4 tail head ③ 入队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 B C