3.2队列 课件(20PPT)2021—2022学年浙教版(2019)信息技术选修1

资源下载
  1. 二一教育资源

3.2队列 课件(20PPT)2021—2022学年浙教版(2019)信息技术选修1

资源简介

(共20张PPT)
知识回顾
有序排队上车的乘客
有序排队接客的出租车
乘客排队时先到的总是从队伍的头部出去(出队)上车,而后到的乘客则必须在队伍的尾部加入(入队)。同时,为了确保有序,人们总是规定不能从队伍的中间部位插队。
CHZX
3.2 队列
高中信息技术 选择性必修一 《数据与数据结构》
昌化中学 应彤鑫
队列的概念与特性
概念
特性
01
概 念:队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首
队列元素:队列中的数据元素。
入 队:在队列中插入一个元素的过程。
出 队:从队列中删除一个元素的过程。
出队
入队
队首元素
队尾元素
队列的概念
duilie de gainian
先进先出、后进后出(FIFO):由队列的定义可知,队列具备“先进先出、后进后出”的特点。如图所示,出队时,对首元素a1优先出队,紧接着是a2,a3,……,an-1 ,队尾元素an最后出队。
出队
入队
队首元素
队尾元素
队列的特性
duilie de texing
有限序列性:队列也是一种线性表结构,元素个数是有限的。
队列可以是空的,也可以包含多个元素。
队列中所有元素呈线性特征,队首元素只有一个后继点,队尾元素只有一个前驱点,其他元素既有一个前驱点,又有一个后继点。
出队
入队
队首元素
队尾元素
队列的特性
duilie de texing
1.幼儿园小朋友们排队玩华护体,轮流爬上去,再轮流滑下来,此过程用那种数据结构描述最合适( )
A.链表
B.字典
C.栈
D.队列
练一练
lianyilian
D
2.下列事件执行过程与队列特征不相符的是( )
A.在汽车加油站排队加油时不允许插队
B.当主机运行速度与打印机的打印速度不匹配时,为打印机设置一个打印数据缓冲区
C.把书叠放成一摞,最底下的书要最后才能拿出来
D.CPU分时系统可以根据用户请求,按顺序快速运行各程序段,实现多用户“同时”工作的假象
练一练
lianyilian
C
队列的基本操作
队列的存储结构
建队
入队
出队
02
队列的存储结构:队列一般按顺序结构存储,可以用数组来实现。设置头指针head记录队首元素位置,尾指针tail队尾元素的下一个位置。初始时,head指针和tail指针均记录下标为0的位置。
队列的基本操作
duilie de jibencaozuo
队列的存储结构:队列一般按顺序结构存储,可以用数组来实现。设置头指针head记录队首元素位置,尾指针tail队尾元素的下一个位置。初始时,head指针和tail指针均记录下标为0的位置。
队列的基本操作
duilie de jibencaozuo
初始状态
数据入队后状态
tail=4
4
数据出队后状态
tail=4
4
队列的链式存储结构:队列的链式存储称为链队列,为了操作方便,可以设置队首指针head记录链表的头结点,队尾指针tail记录链表的队尾节点。
队列的基本操作
duilie de jibencaozuo
3. 判断一个长度为n的队列q为空的条件是( )
A.head==0 B.tail==0 C.tail==-1 D.head==tail
4. 用python列表模拟队列,并设置队头指针head指向队首元素,队尾指针tail指向队尾元素的下一个位置,则当head=3,tail=6时,队列中元素的个数为( )
A.3 B.4 C.5 D.6
练一练
lianyilian
D
A
建队
由于队列以数组形式存储,因此python中用列表创建队列。
例如:有4个字母“A”“B”“C”“D”按顺序入队、出队时,可以创建一个队列que,长度为5,python代码如下所示:
队列的基本操作
duilie de jibencaozuo
head=0
tail=0
que=[“”]*5
入队
字母“A”“B”“C”“D”按顺序入队时,在队列que中,用tail指针变量跟踪各元素的入队
队列的基本操作
duilie de jibencaozuo
0 1 2 3 4
head
tail
初始状态(空队列)
A
0 1 2 3 4
head
tail
“A”入队
head=0
tail=0
que=[“”]*5
que[tail] =“A”
tail+=1
A B
0 1 2 3 4
head
tail
“B”入队
que[tail] =“B”
tail+=1
入队
字母“A”“B”“C”“D”按顺序入队时,在队列que中,用tail指针变量跟踪各元素的入队
队列的基本操作
duilie de jibencaozuo
0 1 2 3 4
head
tail
初始状态(空队列)
head=0
tail=0
que=[“”]*5
A B C D
0 1 2 3 4
head
tail
全部入队
que[tail] =“A”
tail+=1
que[tail] =“B”
tail+=1
que[tail] =“C”
tail+=1
que[tail] =“D”
tail+=1
出队
出队时,排在队首的元素依次出队,head指针变量依次加1,直至head值等于tail值时,队列为空。
队列的基本操作
duilie de jibencaozuo
A B C D
0 1 2 3 4
head
tail
全部出队
while head !=tail:
head+=1
A B C D
0 1 2 3 4
head
tail
初始状态(满队列)
练一练
lianyilian
1.队列存储在数组que[0..n]中,用head表示队首指针,tail表示队尾指针,当元素“x”要进入队列时,入队操作为:___________________________。
2.当队列que(非循环队列)的头指针变量和尾指针变量为head、tail,如何判断队列是否为空?
3.队列是限定在( )进行操作的线性表。
A.队首 B.队尾 C.中间 D.两端
que[tai]='X'
tail=tail+1
对于线性队列,当headD
循环队列:将队列的队首和队尾连接起来,形成逻辑上的环状结构。
当对循环队列中的元素进行入队、出队操作时,队首指针变量和队尾指针变量可以循环指向所有位置,从而有效地解决队列中“有空闲位置却不能入队”的问题。
拓展
tuozhan
5. 已知队列元素的个数为6,则队首指针head和队尾指针tail的值不可能的是( )
A.head=0,tail=6 B. head=6,tail=0
C. head=3,tail=2 D. head=3,tail=8
练一练
lianyilian
D

展开更多......

收起↑

资源预览