队列 课件(共20张PPT) 选修一《数据与数据结构》
文档属性
| 名称 | 队列 课件(共20张PPT) 选修一《数据与数据结构》 |  | |
| 格式 | pptx | ||
| 文件大小 | 1.7MB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2024-04-21 19:36:13 | ||
图片预览
文档简介
(共20张PPT)
第三章 字符串、队列和栈
选修一《数据与数据结构》
3.2 队列的概念、特性与基本操作
队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。
队列是什么？
太抽象了，无法理解
队列是什么？
队尾
队首
队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。
队列中的数据被称为队列元素
队列元素
先进先出
队列
队列的特性
一、先进先出，后进后出
元素入队顺序和元素出队顺序一致。
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 D
0
1
2
3
4
tail
head
①
B C D
0
1
2
3
4
tail
head
②
C D
0
1
2
3
4
tail
head
③
出队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
第三章 字符串、队列和栈
选修一《数据与数据结构》
3.2 队列的概念、特性与基本操作
队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。
队列是什么？
太抽象了，无法理解
队列是什么？
队尾
队首
队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。
队列中的数据被称为队列元素
队列元素
先进先出
队列
队列的特性
一、先进先出，后进后出
元素入队顺序和元素出队顺序一致。
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 D
0
1
2
3
4
tail
head
①
B C D
0
1
2
3
4
tail
head
②
C D
0
1
2
3
4
tail
head
③
出队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