资源简介

(共20张PPT)
二、 队列及其基本操作
第三章　字符串、队列和栈
知识过关
1. 队列的概念
队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。
2. 队列的特性
(1)先进先出、后进后出。
如图所示,出队时,队首元素A1先出队,接下来是A2、A3、…、An,队尾元素An最后出队。
队列基本操作图
(2)有限序列性。
队列中的元素也是有限的。队列可以是空的,也可以包含多个元素。队列中的所有元素呈线性特征,每个元素只有一个前驱点(队首元素没有前驱点),也只有一个后继点(队尾元素没有后继点)。
3. 队列的存储结构
队列一般按顺序结构存储,可以用数组来实现。设置头指针head和尾指针tail分别记录队首元素的位置和队尾元素的下一个位置。初始时,head指针和tail指针均记录下标为0的位置。队列元素“A”“B”“C”“D”入队后,tail指针指向下标为4的位置。
队列初始化(head=tail)　　 元素入队(tail=tail+1)
4. 队列的基本操作及其实现
(1)建队。
在Python中,用列表(数组)创建队列,刚建队列时,head=tail=0。
(2)入队。
当有新元素入队时,先将元素存储到tail指针指向的位置,然后将tail指针加1,即向队尾方向移动。
(3)出队。
当队列非空时(head!=tail),先读取队首head指针指向的元素,然后head指针加1,即向队尾方向移动,直到head=tail为止。
建队、入队和出队的过程用Python代码模拟如下:
s=input("请输入字符串:")
que=[""]*100
head=0;tail=0　　　　　　　　　 #建队
for i in range(len(s)): #入队操作,从队尾开始
　　que[tail]=s[i] #先进队
　　tail+=1 #然后tail后移一个位置
while head　　print(que[head],end="") #先输出队首元素
head+=1 #然后移动head到下一个位置
5. 循环队列
对于队列的操作,经过多次出队、入队操作后,会出现tail指针已经指向了队列最后一个位置、head指针指向了中间某处位置的情况,此时队尾无法继续进行入队操作,而head指针前又存在空余部分,这种现象叫作队列“假溢出”,如图所示:
解决假溢出的办法就是如果队列满了而前面有空位,就再从头开始,形成头尾相接的循环队列。
我们把队列的这种头尾相接的顺序存储结构称为循环队列,如图所示:
空循环队列和满循环队列分别如图所示:
当队列满时,会留出一个空间,这样就便于区分队列的满与空。
可利用队首和队尾(队首下标为head,队尾下标为tail,队列最大长度为n)指针位置判断循环队列的状态:
代码 描述
head=tail 队列为空
(tail+1)% n=head 队列为满
qsize=(tail－head+n)% n 队列长度
tail=(tail+1)% n 入队
head=(head+1)% n 出队
典例精选
【例1】 (2023·浙江6月选考)列表q长度为20,q[0]至q[4]的值依次为p,r,i,n,t,执行如下程序段后,输出的最后一个字符是(　　)
head,tail= 0,5
while head < tail:
　　if head % 3 == 0:
　　　　print(q[head])
　　else:
　　　　q[tail] = q[head]
　　　　tail += 1
　　head += 1　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
A. t B. n　
C. i D. r
D
【解析】 本题考查单向顺序队列的数组实现。根据队列基本操作可知,程序段的功能是:当队列q非空时(空队列为head =tail),根据头指针的索引位置(head % 3 =0),分别执行“出队”操作或者“出队并入队”操作,再结合题意,本题求解的是最后一个出队元素。用表格法模拟该队列头、尾指针和“出队”操作的变化,如下表所示:
综上所述，D正确。
【例2】 (2023·浙江6月选考)有1个队列,队首到队尾的元素依次为8,3,2,9,5。约定如下:T操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队,则经过
TTTQTTQ系列操作后,队列中队首到队尾的元素依次是(　　)
A. 2,9,5 B. 2,5,8
C. 5,8,2 D. 8,3,2
【解析】 本题考查顺序队列的基本操作。T的操作为出队并入队,Q的操作为出队。TTTQTTQ之后队列内元素依次为:2,5,8。出队的元素依次为9,3。B正确。
B
【例3】 假设以数组a[m]存放循环队列的元素,其头指针和尾指针分别为head和tail,则当前队列中的元素个数是(　　)
A. (tail－head+m)% m　 B. tail－head+1
C. (head－tail+m)% m D. (tail－head)% m
【解析】 本题考查队列的基本操作。循环队列,如果tail> head,元素个数为tail－head,如果tail< head,元素个数为tail－head+m,所以综合可以用(tail－head+m)%m来表示。
A
自我检测
1. 某种特殊的队列 Q,支持以下3个操作:操作Q1,若队列非空,则队首元素出队,并输出;操作Q2,若队列非空,则队首元素出队;操作Q3,一个元素入队;以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。若队列 Q 的初始状态为空,则依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后,下列说法中,正确的是(　　)
A.当前队列中的元素个数为 2
B.输出的元素个数为 2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
【解析】 操作Q3、Q2之后,队列为空。Q3、Q1,队列为空。因此队列中元素个数为1,Q1操作出队并输出元素,输出的元素个数为1。C选项没有可比性。D选项若队列不为空,则Q3、Q2、Q1、Q2输出的结果不一样。
D
2. 在某点餐系统中,利用队列来储存当前正在排队顾客的编号,head指向队首元素,tail指向队尾元素的下一个位置。若tail=head+4,则目前队列中的顾客数是(　　)
A. 0 B. 3
C. 4 D. 5
【解析】 队列初始时为空,head和tail的值都为0。由于tail指向队尾元素的下一个位置,当队列中有1个元素时,tail=head+1,以此类推,队列中的元素个数为4,C正确。
C
3. 对某队列进行操作:初始化时,头指针head和尾指针tail均为0,当进行了5次入队和2次
出队操作后,head指针和tail指针指向的值分别是(　　)
A. 0,5　　 B. 5,2　　
C. 3,5　　 D. 2,5
【解析】 本题考查队列知识。由题意可得,5次入队后,tail指向5,2次出队操作后,head指向2,D正确。
D
4. 有一个队列s,其中指针head 指向队首元素的位置,指针tail指向队尾元素的下一个位置。
下列关于该队列的说法,正确的是(　　)
A.队列中元素个数为tail－head+1
B.新元素入队时,指针head向右移动
C.元素出队时,指针tail向右移动
D.当tail==len(s)时,无法再入队新元素
【解析】 本题考查队列性质和基本操作。tail是指向队尾元素后面的位置,因此队列长度
为tail－head。 当tail值为len(s),队尾元素存储在len(s)－1,因此队列已满。
D
5. 下列有关队列的说法,正确的是(　　)
A.队列是一种先进先出的线性表,插入一端为队首,删除一端为队尾
B.队列的存储结构可用数组实现,也可用链表实现
C.一队列队头指针head,队尾指针tail,则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
【解析】 本题考查队列的性质。A选项队列在队尾插入,在队首删除;C选项队尾指针tail指向队尾元素的下一个位置,所以tail－head表示队列中元素个数;D选项软件连续撤销操作是撤销前一步操作,是栈的应用实例。
B

展开更多......

收起↑