资源简介

(共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

展开更多......

收起↑