资源简介

专题15　队　列
学习目标　1.通过生活实例，理解队列的性质和作用；
2.在理解队首和队尾指针的功能上，掌握队列和循环队列元素个数的计算方法；
3.在理解队首和队尾指针的功能上，掌握建队、入队和出队的操作过程.
栈和队列主要用于计算过程中保存的临时数据，为了更好地检索到需要的数据，需要复杂的存储机制，这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。队列是一种在数组两端分别进行存取的数据结构，最大特点是数据在存取时，无需查询，时间复杂度为O(1)，先存取的数据先被取出。队列是一种先进先出、后进后出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列一般按顺序结构存储，可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。在Python中，用列表(数组)创建队列，元素入队时，先将元素存储到tail指针指向位置，然后tail指针加1，即向队尾方向移动。元素出队时，当队列非空时条件head！＝tail，先读取队首head指针指向的元素，然后head指针加1，即向队尾方向移动，直到head＝＝tail为止。
(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
重难点1　队列的特性
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。先进先出是队列的特性，若元素出队后将入队，那么入队后的元素还是维持原来的顺序。建队时，指针head和tail均指向0，head加1表示出队，tail加1表示入队。判断队列是否空的条件是head！＝tail，判断队列中元素的数量为tail－head。
例题 有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
变式 有1个队列，队首到队尾的元素依次为 8，10，12，9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为(　　)
A.2，3 B.6，2，3 C.9，4，5 D.9，4，5，6
重难点2　队列的算法实现
头指针head记录队首元素位置，队尾指针tail记录队尾元素的下一个位置，队列q的队尾元素值为q[tail－1]。入队时，需将x赋值给q[tail]，让其成为新的队尾元素，再移动tail指针。出队时，需先将q[head]赋值给x，再移动head指针。
例1 执行下列Python程序段，输出结果为(　　)
data ＝ [1, 2, 3, 1, 2, 3]
que ＝ [0] * 10
head ＝ tail ＝ 0
for i in range(len(data)) ：
　 if data[i] % 2 ！＝ 0 :
　 que[tail] ＝ data[i]
　 tail ＋＝ 1
　 elif tail － head > 1 ：
　 que[tail－1] ＋＝ que[head]
　 head ＋＝ 1
print(que[head : tail])
A.[3, 2, 1] B.[1, 2, 3]
C.[1, 3, 1] D.[3, 2, 3]
变式1 有如下Python程序段：
s＝″abcdddbha″
que＝[″″]*10
head＝tail＝0
for i in range(len(s))：
　 if s[i] not in que[head：tail]:
　 que[tail]＝s[i]
　 tail＋＝1
　 else：
　 head＋＝1
print(que[head：tail])
程序运行后，输出的结果是(　　)
A.['a'，'b'，'c'，'d'，'h']
B.['a'，'b'，'c'，'d'，'d']
C.['c'，'d'，'b'，'h'，'a']
D.['a'，'d'，'d'，'d'，'a']
例2 有如下Python程序段：
import random
q＝[0]*8
head，tail＝0，4
for i in range(4)：
　 k＝random.randint(0，10)
　 if k%2＝＝0：
　 q[tail]＝k%5
　 tail＋＝1
　 else：
　 head＋＝1
while head　 print(q[head]，end＝″″)
　 head＋＝1
程序运行后，输出结果可能为(　　)
A.0 0 0 0 2 3 0 6 B.0 1 2 3 4
C.0 0 0 0 D.2 4
变式2 有如下Python程序段：
import random
que＝[0]*10
head＝0；tail＝5　#定义队列的首尾指针
for i in range(5)：
　 k＝random.randint(0, 10)
　 if k%2＝＝0：
　 head＋＝1
　 else：
　 que[tail]＝i%3
　 tail＋＝1
while head　 print(que[head], end＝″″)
　　head＋＝1
运行如下程序段后，输出结果不可能是(　　)
A.0 0 0 2 B.0 0 1 2
C.0 1 0 2 D.0 0
重难点1　队列的特性
1.有一个队列S，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为tail－head＋1
B.新元素入队时，指针head向右移动
C.元素出队时，指针tail向右移动
D.当tail的值为len(S)时，无法再入队新元素
2.某队列经过“出队”“入队”操作后，队首指针head＝2，队尾指针tail＝6，则该队列中剩余的元素个数是(　　)
A.2 B.4 C.5 D.6
3.有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.1 B.1，3 C.3，4 D.3
4.若用一个规模为20的数组来实现队列，已知当前队尾指针tail的值为8，队头指针head的值为3，进行如下操作：连续删除2个元素、连续插入5个元素、删除1个元素，连续插入2个元素。则操作后指针head和tail的值分别为(　　)
A.5和14 B.6和14
C.6和15 D.7和15
5.队列q中队首至队尾元素依次为“A，B，C，D，E，F”，约定：S为出队操作，U为出队再入队操作，若要使队列q队首至队尾元素依次为“B，D，E”，下列操作可实现的是(　　)
A.USUSSU B.SUSUUS
C.SSSUUU D.SUUSUS
6.某种特殊的队列 Q，支持以下3个操作：操作Q1，若队列非空，队首元素出队，并输出；操作Q2，若队列非空，队首元素出队；操作Q3，一个元素入队；以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空，依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后，下列说法正确的是(　　)
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
重难点2　队列的算法实现
1.执行如下程序段后，变量length的值为(　　)
s＝″engineer″
q＝[″″]*len(s)
head，tail＝0，0
length＝0
for x in s：
　 while x in q[head：tail]：
　 head＋＝1
　 q[tail]＝x
　 tail＋＝1
　 if tail－head>length：
　 length＝tail－head
A.2 B.3 C.4 D.5
2.有如下Python程序段：
s＝″ABCDEF″
head＝0；tail＝0
que＝[″″]*100
for i in range(len(s))：
　 if i%2＝＝0：
　 que[tail]＝s[i]
　 else：
　 que[tail]＝s[len(s)－i]
　 tail＝tail＋1
while head　 print(que[head]，end＝″″)
　 head＝head＋1
执行该程序段后，输出的结果是(　　)
A.ABCDEF B.FEDCBA
C.ACEFDB D.AFCDEB
3.有如下Python程序，
a＝[13, 12, 12, 15, 26, 23, 36]
que＝[0]*len(a)
head＝tail＝0
for x in a：
　 while head　　　 if x　　　 tail－＝1
　　　 else：
　　　 break
　　que[tail]＝x
　　tail＋＝1
print(que[head：tail])
执行后，程序输出结果为(　　)
A.12 15 26 36 B.12 15 23 26
C.12 12 15 23 36 D.12 13 15 23 36
4.列表q长度为20，q[0]到q[7]的值依次为'a'，'b'，'c'，'a'，'c'，'d'，'d'，'e'，执行如下程序段后，输出的结果为(　　)
head＝tail＝0
for i in range(8)：
　 if q[i]＝＝q[head] and head！＝tail:
　 tail＋＝1
　 head＝tail
　 else：
　 tail＋＝1
print(q[head：tail])
A.cdde B.acdde C.eddc D.e
5.有如下Python程序：
a＝[4，2，5，1，9]
que＝[0]*7
head，tail＝0，0
que[tail]＝a[0]
tail＋＝1
for i in range(1，len(a)):
　 if a[i]>que[tail－1]:
　 que[tail]＝a[i]
　 tail＋＝1；head＋＝1
　 elif a[i]　 que[tail]＝a[i]
　 tail＋＝1
print(que[head：tail])
执行以上程序段后，输出结果是(　　)
A.4，7 B.5，1，9
C.2，5，1，9 D.4，7，2，5，1，9
6.有如下程序段：
m＝3；n＝7
head＝tail＝0；ans＝0
vis＝[0]*10；q＝[0]*10
for i in range(n)：
　 x＝int(input())
　 if (vis[x]＝＝0):
　 ans＋＝1
　 if tail－head>＝m:
　　　　vis[q[head]]＝0
　　　　head＋＝1
　 q[tail]＝x
　 tail＋＝1
　 vis[x]＝1
print(ans)
运行该程序段，依次输入x的值：1，2，1，5，4，4，1。则程序运行完成后ans的值是(　　)
A.3 B.4 C.5 D.6
重难点1　队列的特性
1.下列有关队列的说法正确的是(　　)
A.队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B.队列的存储结构，可用数组实现，也可用链表实现
C.一队列队头指针head，队尾指针tail, 则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
2.在该系统中，可以利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置，若tail＝head＋3，则现在排队的顾客数量为(　　)
A.2 B.3 C.4 D.5
3.假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　　)
A.11　12 B.2　5
C.3　6 D.3　5
4.有2个队列a和b，队首到队尾的元素依次分别为“5，7，9”和“6，4，8”。约定：T操作是指队列a中1个元素先出队，若大于队列b的队首元素则再入b队列，否则不入；Q操作是指队列b中1个元素先出队，若大于队列b的队尾元素则再入b队列，否则不入。则经过TTQQQQT系列操作后，队列b中的元素个数为(　　)
A.1 B.2 C.3 D.4
5.某队列的数据结构如图所示，head和tail分别是队列的头指针和尾指针。现对该队列进行下列操作：①队首元素出队后再入队；②队首元素出队并输出，重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　　)
A.Python B.Ptoynh
C.yhntPo D.yhntoP
6.约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后，队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5 C.4　5 D.4　6
7.有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.4，5 B.5，4 C.2，4 D.4，2
8.队列Q从队首到队尾的元素依次为3，1，2，栈S初始为空。约定以下操作：H操作是指元素出队后再入队，T操作是指元素出队后入栈，P操作是指元素出栈。经过一系列操作后，最终出栈顺序为1，2，3，以下操作不可能的是(　　)
A.TTPTPP B.HTTTPPP
C.THTTPPP D.HTPTPTP
9.假设高铁站的售票窗口平均每分钟过来一个人购票，每人的购票时间平均约为2分钟，某车站在中午时段开了一个售票窗口，12：01：00的时候有1个人刚开始购票，3个人在等待，那么12：11：00时队伍中等待购票的人数为(　　)
A.7 B.8 C.9 D.10
重难点2　队列的算法实现
1.有如下Python程序段：
Q＝[0]*10
cnt，head，tail ＝ 0，0，0
S＝input()
for i in range(0，9，2)：
　 t ＝ S[i]
　 n ＝ int(S[i＋1])
　 if t ＝＝ 'A'：
　 for j in range(n)：
　　　　Q[tail] ＝ cnt
　　　　tail ＋＝ 1
　　　　cnt ＋＝ 1
　elif t ＝＝″D″：
　 while head ！＝ tail and n > 0：
　　　　 head ＋＝ 1
　　　　 n －＝ 1
print(Q[head : tail])
若输入S的值为″A2D1A1D3A2″，则程序的输出结果是(　　)
A.[3，4，5] B.[3，4] C.[4，5] D.[4]
2.执行如下程序段后，输出的结果是(　　)
q＝[6，8，9，7，4，5，2，3]
pre＝10
head，tail＝0，len(q)
while head！＝tail：
　 if pre>q[head]:
　 pre＝q[head]
　print(q[head]，end＝' ')
　 head＋＝1
A.6 8 9 B.6 4 2
C.6 5 3 D.6
3.有如下Python程序段：
que ＝ ['A', 'B', 'C', 'D', 'E']
for i in range(10):
　 que.append(－1)
n ＝ 5; head ＝ 0; tail ＝ 5
for i in range(n)：
　 print(que[head], end＝' ')
　 head ＋＝ 1
　 for j in range(i)：
　 que[tail] ＝ que[head]
　 tail ＋＝ 1
　 head ＋＝ 1
执行该程序段后，显示的结果是(　　)
A.ACBED B.ABDCE
C.ABDEC D.ACBDE
4.某 Python 程序如下：
que＝[0]*7
a＝[2，3，5，1，3，5，2]
head＝0 ；tail＝0
for i in a：
　 if tail－head＝＝3:
　 head＋＝1
　 elif i not in que[head：tail]:
　 que[tail]＝i
　 tail＋＝1
print(que[head：tail])
执行上述程序后，输出的结果为(　　)
A.[2, 3, 5, 1] B.[3, 5, 2]
C.[2, 3, 5] D.[5, 1, 2]
5.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″输入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
　 q[tail]＝i
　 tail＝tail＋1
　 s＋＝i
　 if ans　 ans＝s
　 while ik：
　 s－＝q[head]
　 head＝head＋1
执行该程序段后，输入k的值为2，变量ans的值是(　　)
A.18 B.19 C.21 D.22
6.有如下 Python 程序段：
s ＝″abcxyz″
q ＝ [1，2，3] ＋ [0] * 10
head , tail ＝ 0 , 3
res ＝″″
for i in s：
　 c ＝ chr((ord(i) － ord(″a″) ＋ q[head]) % 26 ＋ ord(″a″))
　 res ＋＝ c
　 q[tail] ＝ q[head]
　 head ＝ head ＋ 1
　 tail ＝ tail ＋ 1
print(res)
执行该程序段后，输出的结果是(　　)
A.bdfyac B.bdfxyz
C.abcyac D.yacbdf
7.有如下程序段：
import random
q＝[0]*6
head＝tail＝0
for i in range(6):
　 x＝random.randint(0，1)
　 if x＝＝1：
　 q[tail]＝random.randint(1，10)
　 elif head！＝tail and q[tail－1]>q[head]:
　 q[tail]＝q[head]
　 head＋＝1
　 tail＋＝1
运行该程序段后，q的值可能是(　　)
A.[5，3，8，6，0，1] B.[5，3，0，1，0，2]
C.[2，0，3，0，4，0] D.[0，9，0，10，0，5]
8.有如下Python 程序段：
import random
q＝[0]*5
head，tail＝0，0
for i in range(5)：
　 if random.randint(0，i)%2＝＝0：
　 q[tail]＝random.randint(1，9)　#随机生成1到9之间的整数
　 elif head　 q[tail]＝q[head]
　 head ＋＝1
　 tail ＋＝1
print(q)
执行该程序段后，列表q 的值不可能是(　　)
A.[1，0，1，0，9] B.[5，4，3，2，1]
C.[5，8，3，0，0] D.[5，5，6，0，6]
9.有如下Python程序段：
import random
a＝[8，10，2，7，11，9，16]
c＝[0]*len(a)
head＝0；tail＝0
for i in range(len(a)):
　 t＝random.randint(0，1)
　 if tail－head<2 or t＝＝0：
　 c[tail]＝a[i]
　　　tail＝tail＋1
　 elif a[i]>c[head]：
　　　head＝head＋1
print(c[head：tail])
执行该程序段后，输出的内容不可能是(　　)
A.[10，9，16] B.[8，10，11，9，16]
C.[8，10，2，9] D.[10，7，16]
10.有如下Python程序段：
from random import randint
s＝″14257″；q＝[″″]*10; ans＝″″
head＝tail＝0
for i in s：
　 q[tail]＝i
　 tail＋＝1
for i in range(len(s))：
　 t＝randint(0, 1)
　 if t＝＝0：
　 q[tail]＝q[head]
　 tail＋＝1
　 head＋＝1
while tail>head：
　 ans＋＝q[head]
　　head＋＝1
print(ans)
运行该程序段，则输出的值不可能的是(　　)
A.5 B.41 C.457 D.14257
11.有如下Python程序段：
que＝[1，5，3，2，7]＋[0]*100　#构建列表que, 形如[1，5，3，2，7，0，0，0，…]
head＝0；tail＝5
st＝[0]*len(que)　#构建栈st
top＝－1
while　head！＝tail：
　 while top！＝－ 1 and que[head]>st[top]：
　 que[tail]＝st[top]
　　　tail＋＝1
　　　top－＝1
　 top＋＝1
　 st[top]＝que[head]
　 head＋＝1
执行该程序段后，栈st从栈顶到栈底的元素依次为(　　)
A.7，5，3，2，1 B.1，2，3，5，7
C.0，1，2，3，5，7 D.7，5，3，2，1，0
专题15　队　列
学习目标　1.通过生活实例，理解队列的性质和作用；
2.在理解队首和队尾指针的功能上，掌握队列和循环队列元素个数的计算方法；
3.在理解队首和队尾指针的功能上，掌握建队、入队和出队的操作过程.
栈和队列主要用于计算过程中保存的临时数据，为了更好地检索到需要的数据，需要复杂的存储机制，这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。队列是一种在数组两端分别进行存取的数据结构，最大特点是数据在存取时，无需查询，时间复杂度为O(1)，先存取的数据先被取出。队列是一种先进先出、后进后出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列一般按顺序结构存储，可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。在Python中，用列表(数组)创建队列，元素入队时，先将元素存储到tail指针指向位置，然后tail指针加1，即向队尾方向移动。元素出队时，当队列非空时条件head！＝tail，先读取队首head指针指向的元素，然后head指针加1，即向队尾方向移动，直到head＝＝tail为止。
(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
解析　本题考查队列的基本操作。队列每次出队一个元素，若head是3的倍数时，输出队首元素，否则将队首元素入队，p出队并输出，r和i出队后入队，队列中元素依次为ntri，head值为3；n出队并输出，t和r出队后入队，队列中元素依次为itr，head值为6；i出队并输出，t和r出队后入队，队列中元素依次为tr，head值为9；t出队，队列中只剩下元素r，r连续两次出队后再入队，当head为12时，r出队。
重难点1　队列的特性
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。先进先出是队列的特性，若元素出队后将入队，那么入队后的元素还是维持原来的顺序。建队时，指针head和tail均指向0，head加1表示出队，tail加1表示入队。判断队列是否空的条件是head！＝tail，判断队列中元素的数量为tail－head。
例题 有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
思维点拨
明考向 本题考查队列的基本操作
精点拨 数组前面入队，后面出队。TTT操作结果：9，5，8，3，2。Q后队列为：5，8，3，2。再TT之后结果为：3，2，5，8。Q后，队列为：2，5，8
答案　B
变式 有1个队列，队首到队尾的元素依次为 8，10，12，9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为(　　)
A.2，3 B.6，2，3 C.9，4，5 D.9，4，5，6
答案　D
解析　本题考查队列性质和操作。根据队列的特点“先进先出，后进后出”，8出队后4入队(2次)，10出队后5入队(2次)，12出队后6入队(2次)。共6次，其结果为9，4，5，6。
重难点2　队列的算法实现
头指针head记录队首元素位置，队尾指针tail记录队尾元素的下一个位置，队列q的队尾元素值为q[tail－1]。入队时，需将x赋值给q[tail]，让其成为新的队尾元素，再移动tail指针。出队时，需先将q[head]赋值给x，再移动head指针。
例1 执行下列Python程序段，输出结果为(　　)
data ＝ [1, 2, 3, 1, 2, 3]
que ＝ [0] * 10
head ＝ tail ＝ 0
for i in range(len(data)) ：
　 if data[i] % 2 ！＝ 0 :
　 que[tail] ＝ data[i]
　 tail ＋＝ 1
　 elif tail － head > 1 ：
　 que[tail－1] ＋＝ que[head]
　 head ＋＝ 1
print(que[head : tail])
A.[3, 2, 1] B.[1, 2, 3]
C.[1, 3, 1] D.[3, 2, 3]
思维点拨
明考向 本题考查队列的算法实现
精点拨 遍历data数组，如果data[i]是奇数，入队。data[i]是偶数且队列中至少有2个元素时，队首元素出队且累加到que[tail － 1]元素。遍历到1时，1入队；遍历到2时，队列只有1个元素。遍历到3时，3入队；遍历到1时，1入队；遍历到1时，1出队且累加到队尾，队列为[3，2] ；遍历到3时，3入队
答案　D
变式1 有如下Python程序段：
s＝″abcdddbha″
que＝[″″]*10
head＝tail＝0
for i in range(len(s))：
　 if s[i] not in que[head：tail]:
　 que[tail]＝s[i]
　 tail＋＝1
　 else：
　 head＋＝1
print(que[head：tail])
程序运行后，输出的结果是(　　)
A.['a'，'b'，'c'，'d'，'h']
B.['a'，'b'，'c'，'d'，'d']
C.['c'，'d'，'b'，'h'，'a']
D.['a'，'d'，'d'，'d'，'a']
答案　C
解析　本题考查队列基本操作。遍历列表s，当元素不在队列中，将该元素入队，否则将队首元素出队(该元素不入队)。遍历第2个第3个d时，ab出队，队列中有[c，d]，接着bha依次入队。
例2 有如下Python程序段：
import random
q＝[0]*8
head，tail＝0，4
for i in range(4)：
　 k＝random.randint(0，10)
　 if k%2＝＝0：
　 q[tail]＝k%5
　 tail＋＝1
　 else：
　 head＋＝1
while head　 print(q[head]，end＝″″)
　 head＋＝1
程序运行后，输出结果可能为(　　)
A.0 0 0 0 2 3 0 6 B.0 1 2 3 4
C.0 0 0 0 D.2 4
思维点拨
明考向 本题考查队列的算法实现。队列中初始化4个元素，值均为0。程序一共循环4次，当产生的随机数k为偶数时，将k%5入队，否则出队一个元素
精　点　拨 A 队列中共有8个元素，因此共入队4个元素，但入队的元素值k%5必须小于5
B 队列中共有5个元素，说明入队比出队多一次，设入队x次，出队y次，有表达式x＋y＝4和x－y＝1成立，两者相加得到x不为整数
C 说明入队和出队各2次，两面2个0为后面入队的元素
D 表达式x＋y＝4和x－y＝－2成立，入队1个元素4，出队2个0，但2不可能存在于原队列中
答案　C
变式2 有如下Python程序段：
import random
que＝[0]*10
head＝0；tail＝5　#定义队列的首尾指针
for i in range(5)：
　 k＝random.randint(0, 10)
　 if k%2＝＝0：
　 head＋＝1
　 else：
　 que[tail]＝i%3
　 tail＋＝1
while head　 print(que[head], end＝″″)
　　head＋＝1
运行如下程序段后，输出结果不可能是(　　)
A.0 0 0 2 B.0 0 1 2
C.0 1 0 2 D.0 0
答案　C
解析　本题考查队列的算法实现。i%3的值依次为0，1，2，0，1，队列的特性是先进先出，前5个零以后面入队的数字之前出队。5次操作后，前三项队列中有4个元素，说明出队比入队多1次。A选项0和2入队。B选项1和2入队。C选项1和2入队，但原始队列中没有1。D选项队列中剩余2个元素，出队加入队次数为5，出队比入队多3次，因此出队4次，入队1次，最后一个0入队。
重难点1　队列的特性
1.有一个队列S，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为tail－head＋1
B.新元素入队时，指针head向右移动
C.元素出队时，指针tail向右移动
D.当tail的值为len(S)时，无法再入队新元素
答案　D
解析　本题考查队列性质和基本操作。tail是指向队尾元素后面的位置，因此队列长度为tail－head。 当tail值为len(S)，队尾元素存储在len(S)－1，因此队列已满。
2.某队列经过“出队”“入队”操作后，队首指针head＝2，队尾指针tail＝6，则该队列中剩余的元素个数是(　　)
A.2 B.4 C.5 D.6
答案　B
解析　本题考查队列的基本知识。队列中元素个数＝tail－head＝4。
3.有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.1 B.1，3 C.3，4 D.3
答案　D
解析　元素1，2入队，1出队后入队，队列为2，1。2出队，1出队后入队，3入队，1出队，因此队列中只有元素3。
4.若用一个规模为20的数组来实现队列，已知当前队尾指针tail的值为8，队头指针head的值为3，进行如下操作：连续删除2个元素、连续插入5个元素、删除1个元素，连续插入2个元素。则操作后指针head和tail的值分别为(　　)
A.5和14 B.6和14
C.6和15 D.7和15
答案　C
解析　本题考查队列的入队出队操作。删除元素，即进行出队操作，出队时将队首元素删除，然后队首指针加1；插入元素，即进行入队操作，入队时先将元素插入，然后队尾指针加1。共删除3个元素，删除操作结束后，因此队头指针head的值为6，共插入7个元素，操作后队尾指针tail的值为15。
5.队列q中队首至队尾元素依次为“A，B，C，D，E，F”，约定：S为出队操作，U为出队再入队操作，若要使队列q队首至队尾元素依次为“B，D，E”，下列操作可实现的是(　　)
A.USUSSU B.SUSUUS
C.SSSUUU D.SUUSUS
答案　B
解析　元素A出队，元素B出队后入队，元素C出队，元素D和E出队后入队，元素F出队。
6.某种特殊的队列 Q，支持以下3个操作：操作Q1，若队列非空，队首元素出队，并输出；操作Q2，若队列非空，队首元素出队；操作Q3，一个元素入队；以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空，依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后，下列说法正确的是(　　)
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
答案　D
解析　操作Q3、Q2之后，队列为空。Q3、Q1，队列为空。因此队列中元素个数为1，Q1操作出队并输出元素，输出的元素个数为1。C选项没有可比性。D选项若队列不为空，则Q3、Q2、Q1、Q2输出的结果不一样。
重难点2　队列的算法实现
1.执行如下程序段后，变量length的值为(　　)
s＝″engineer″
q＝[″″]*len(s)
head，tail＝0，0
length＝0
for x in s：
　 while x in q[head：tail]：
　 head＋＝1
　 q[tail]＝x
　 tail＋＝1
　 if tail－head>length：
　 length＝tail－head
A.2 B.3 C.4 D.5
答案　C
解析　程序功能实现查找最长不重复的子串，该子串为'engi'。
2.有如下Python程序段：
s＝″ABCDEF″
head＝0；tail＝0
que＝[″″]*100
for i in range(len(s))：
　 if i%2＝＝0：
　 que[tail]＝s[i]
　 else：
　 que[tail]＝s[len(s)－i]
　 tail＝tail＋1
while head　 print(que[head]，end＝″″)
　 head＝head＋1
执行该程序段后，输出的结果是(　　)
A.ABCDEF B.FEDCBA
C.ACEFDB D.AFCDEB
答案　D
解析　遍历字符串s，当i%2＝＝0条件成立时，将s[i]入队，否则将s[len(s)－i]入队。
3.有如下Python程序，
a＝[13, 12, 12, 15, 26, 23, 36]
que＝[0]*len(a)
head＝tail＝0
for x in a：
　 while head　　　 if x　　　 tail－＝1
　　　 else：
　　　 break
　　que[tail]＝x
　　tail＋＝1
print(que[head：tail])
执行后，程序输出结果为(　　)
A.12 15 26 36 B.12 15 23 26
C.12 12 15 23 36 D.12 13 15 23 36
答案　C
解析　遍历数组a，若队列不空，且x比队尾元素小，队尾元素不断地出队，再让x入队。整个过程描述为13入队后出队，12，12，15，26依次入队，26出队，23, 36入队。
4.列表q长度为20，q[0]到q[7]的值依次为'a'，'b'，'c'，'a'，'c'，'d'，'d'，'e'，执行如下程序段后，输出的结果为(　　)
head＝tail＝0
for i in range(8)：
　 if q[i]＝＝q[head] and head！＝tail:
　 tail＋＝1
　 head＝tail
　 else：
　 tail＋＝1
print(q[head：tail])
A.cdde B.acdde C.eddc D.e
答案　A
解析　分析程序段可知，该程序段实现的是一种消消乐游戏，即若新遍历到的元素和队首的元素不同或者队列为空，则将新元素入队。若新遍历到的元素和队首的元素相同，则将所有队列中的元素清空。因此队列中最后剩余的元素为 c，d，d，e。
5.有如下Python程序：
a＝[4，2，5，1，9]
que＝[0]*7
head，tail＝0，0
que[tail]＝a[0]
tail＋＝1
for i in range(1，len(a)):
　 if a[i]>que[tail－1]:
　 que[tail]＝a[i]
　 tail＋＝1；head＋＝1
　 elif a[i]　 que[tail]＝a[i]
　 tail＋＝1
print(que[head：tail])
执行以上程序段后，输出结果是(　　)
A.4，7 B.5，1，9
C.2，5，1，9 D.4，7，2，5，1，9
答案　B
解析　队列中初始1个元素，值为4。遍历列表a中位置1到len(a)－1的元素，若遍历的元素值比队尾元素大，则将队首出队后再将a[i]入队。若遍历的元素值小于队首，直接将a[i]入队。队列中元素变化情况为[4, 2]、[2, 5]、[2, 5, 1]、[5, 1, 9]。
6.有如下程序段：
m＝3；n＝7
head＝tail＝0；ans＝0
vis＝[0]*10；q＝[0]*10
for i in range(n)：
　 x＝int(input())
　 if (vis[x]＝＝0):
　 ans＋＝1
　 if tail－head>＝m:
　　　　vis[q[head]]＝0
　　　　head＋＝1
　 q[tail]＝x
　 tail＋＝1
　 vis[x]＝1
print(ans)
运行该程序段，依次输入x的值：1，2，1，5，4，4，1。则程序运行完成后ans的值是(　　)
A.3 B.4 C.5 D.6
答案　C
解析　本题考查队列的算法实现。vis是一个标志数组，当其元素值为0时，可以入队，保证队列中数据是唯一的。当队列中元素个数大于等于3时，将进行出队操作。ans统计入队次数。输入x的值1，2入队，接着1不能入队，5入队，当输入4时，让1出队，4入队。第2个4不能入队，最后一个1入队。
重难点1　队列的特性
1.下列有关队列的说法正确的是(　　)
A.队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B.队列的存储结构，可用数组实现，也可用链表实现
C.一队列队头指针head，队尾指针tail, 则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
答案　B
解析　本题考查队列的性质。A选项队列在队尾插入，在队首删除；C选项队尾指针tail指向队尾元素的下一个位置，所以tail－head表示队列中元素个数；D选项软件连续撤销操作是撤销前一步操作，是栈的应用实例。
2.在该系统中，可以利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置，若tail＝head＋3，则现在排队的顾客数量为(　　)
A.2 B.3 C.4 D.5
答案　B
解析　队列的长度计算公式为tail－head，因此队列有3人排队。
3.假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　　)
A.11　12 B.2　5
C.3　6 D.3　5
答案　C
解析　本题考查队列的性质。入队3次，出队4次，在3次入队前tail应为6，在4次出队前head应为3。
4.有2个队列a和b，队首到队尾的元素依次分别为“5，7，9”和“6，4，8”。约定：T操作是指队列a中1个元素先出队，若大于队列b的队首元素则再入b队列，否则不入；Q操作是指队列b中1个元素先出队，若大于队列b的队尾元素则再入b队列，否则不入。则经过TTQQQQT系列操作后，队列b中的元素个数为(　　)
A.1 B.2 C.3 D.4
答案　B
解析　5和7出队，由于7大于6，则7入队列b。6，4，8依次出队，8大于7，队列b中有7，8。第4个Q表示7出队后不入队。最后队列a中9出队入，入队列b，队列b有元素8和9。
5.某队列的数据结构如图所示，head和tail分别是队列的头指针和尾指针。现对该队列进行下列操作：①队首元素出队后再入队；②队首元素出队并输出，重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　　)
A.Python B.Ptoynh
C.yhntPo D.yhntoP
答案　C
解析　题目中队列的元素执行队首元素出队，再从队尾入队，接下来队首元素出队从队尾入队，直至队列空，输出的顺序为C选项结果。
6.约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后，队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5 C.4　5 D.4　6
答案　D
解析　本题考查队列的基本操作。T操作既有入队，又有出队，因此共有6次入队，4次出队，每次出队和入队，指针分别加1。
7.有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.4，5 B.5，4 C.2，4 D.4，2
答案　C
解析　队列的变化情况为12345→34512→4512→1245→245→524→24。
8.队列Q从队首到队尾的元素依次为3，1，2，栈S初始为空。约定以下操作：H操作是指元素出队后再入队，T操作是指元素出队后入栈，P操作是指元素出栈。经过一系列操作后，最终出栈顺序为1，2，3，以下操作不可能的是(　　)
A.TTPTPP B.HTTTPPP
C.THTTPPP D.HTPTPTP
答案　B
解析　B选项先出队后入队，队列中为1，2，3，再依次入栈，出栈的顺序为3，2，1。
9.假设高铁站的售票窗口平均每分钟过来一个人购票，每人的购票时间平均约为2分钟，某车站在中午时段开了一个售票窗口，12：01：00的时候有1个人刚开始购票，3个人在等待，那么12：11：00时队伍中等待购票的人数为(　　)
A.7 B.8 C.9 D.10
答案　C
解析　根据题目描述，10分钟过来了10个人购票，总共14人，其间4人结束购票，所以队伍还有10人，1人在购票，9人在等待。
重难点2　队列的算法实现
1.有如下Python程序段：
Q＝[0]*10
cnt，head，tail ＝ 0，0，0
S＝input()
for i in range(0，9，2)：
　 t ＝ S[i]
　 n ＝ int(S[i＋1])
　 if t ＝＝ 'A'：
　 for j in range(n)：
　　　　Q[tail] ＝ cnt
　　　　tail ＋＝ 1
　　　　cnt ＋＝ 1
　elif t ＝＝″D″：
　 while head ！＝ tail and n > 0：
　　　　 head ＋＝ 1
　　　　 n －＝ 1
print(Q[head : tail])
若输入S的值为″A2D1A1D3A2″，则程序的输出结果是(　　)
A.[3，4，5] B.[3，4] C.[4，5] D.[4]
答案　B
解析　本题考查队列的入队与出队操作。字符串S中两个字符为一组，第1个元素t代表入队或出队，第2个元素代表n入队或出队的次数。A是入队，D是出队，若出队过程中队空，则中止出队。
2.执行如下程序段后，输出的结果是(　　)
q＝[6，8，9，7，4，5，2，3]
pre＝10
head，tail＝0，len(q)
while head！＝tail：
　 if pre>q[head]:
　 pre＝q[head]
　print(q[head]，end＝' ')
　 head＋＝1
A.6 8 9 B.6 4 2
C.6 5 3 D.6
答案　B
解析　本题考查队列的基本操作。程序的功能是查找队列中最小值，pre初值为10，每次出队一个元素，出队元素也pre比较，记录其最小值的过程。
3.有如下Python程序段：
que ＝ ['A', 'B', 'C', 'D', 'E']
for i in range(10):
　 que.append(－1)
n ＝ 5; head ＝ 0; tail ＝ 5
for i in range(n)：
　 print(que[head], end＝' ')
　 head ＋＝ 1
　 for j in range(i)：
　 que[tail] ＝ que[head]
　 tail ＋＝ 1
　 head ＋＝ 1
执行该程序段后，显示的结果是(　　)
A.ACBED B.ABDCE
C.ABDEC D.ACBDE
答案　C
解析　本题考查队列的基本操作。外循环5次，每次先出队一个元素，内循环分别循环0，1，2，3，4次，每次循环将队列元素出队并入队到最后。当i为0时，A出队，不循环移动。i为1时，B出队，C后移，队列中为DEC。 i为2时，D出队，EC后移，队列中为EC。i为3时，E出队，C后移3次，队列中为C。最后C出队。
4.某 Python 程序如下：
que＝[0]*7
a＝[2，3，5，1，3，5，2]
head＝0 ；tail＝0
for i in a：
　 if tail－head＝＝3:
　 head＋＝1
　 elif i not in que[head：tail]:
　 que[tail]＝i
　 tail＋＝1
print(que[head：tail])
执行上述程序后，输出的结果为(　　)
A.[2, 3, 5, 1] B.[3, 5, 2]
C.[2, 3, 5] D.[5, 1, 2]
答案　B
解析　本题考查队列的基本操作。当i的值为2，3，5时，i均不在队列中，因此入列3次，tail＝3，当i的值为1时，条件tail－head＝＝3成立，因此进行出队(队首指向2)操作，队列中值依次为[3, 5]，当i的值为3，5，不符合条件，当i的值为2时，入队。
5.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″输入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
　 q[tail]＝i
　 tail＝tail＋1
　 s＋＝i
　 if ans　 ans＝s
　 while ik：
　 s－＝q[head]
　 head＝head＋1
执行该程序段后，输入k的值为2，变量ans的值是(　　)
A.18 B.19 C.21 D.22
答案　C
解析　遍历数组a并累加数组元素值，求队列的最大值；当遍历到的当前值小于队首或是长度大于k，将队首元素出队。s的值依次为[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。
6.有如下 Python 程序段：
s ＝″abcxyz″
q ＝ [1，2，3] ＋ [0] * 10
head , tail ＝ 0 , 3
res ＝″″
for i in s：
　 c ＝ chr((ord(i) － ord(″a″) ＋ q[head]) % 26 ＋ ord(″a″))
　 res ＋＝ c
　 q[tail] ＝ q[head]
　 head ＝ head ＋ 1
　 tail ＝ tail ＋ 1
print(res)
执行该程序段后，输出的结果是(　　)
A.bdfyac B.bdfxyz
C.abcyac D.yacbdf
答案　A
解析　本题考查队列的相关操作。表达式(ord(i) － ord(″a″) ＋ q[head]) % 26 的功能是将i转换为在字母表中索引位置，并循环后移q[head]个位置。计算出移动位置后，再转换为小写字母。q中元素实现出队后再入队，因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。
7.有如下程序段：
import random
q＝[0]*6
head＝tail＝0
for i in range(6):
　 x＝random.randint(0，1)
　 if x＝＝1：
　 q[tail]＝random.randint(1，10)
　 elif head！＝tail and q[tail－1]>q[head]:
　 q[tail]＝q[head]
　 head＋＝1
　 tail＋＝1
运行该程序段后，q的值可能是(　　)
A.[5，3，8，6，0，1] B.[5，3，0，1，0，2]
C.[2，0，3，0，4，0] D.[0，9，0，10，0，5]
答案　B
解析　本题考查队列的算法实现。循环6次，当随机数x的值为1时，在队尾生成一个1到10之间的随机数；当x为0时，若队列不为空且队尾大于队首，则将队首出入后再入队尾。因此入队的数据有3种可能性，还有一种可能性是没有新数据入队，tail直接往后移动。A选项若x为1，0不可能产生。若x为0，此时队列不为空，队首值为5，队尾值为6，满足队尾大于队首，5出队后入队。B选项5大于3，5大于1，因此可以不出队。C选项2大于3，因此2要出队后再入队。D选项由于0小于9，0也队后入队，队首为9，由于9小于10，因此最后一个0不可能产生。
8.有如下Python 程序段：
import random
q＝[0]*5
head，tail＝0，0
for i in range(5)：
　 if random.randint(0，i)%2＝＝0：
　 q[tail]＝random.randint(1，9)　#随机生成1到9之间的整数
　 elif head　 q[tail]＝q[head]
　 head ＋＝1
　 tail ＋＝1
print(q)
执行该程序段后，列表q 的值不可能是(　　)
A.[1，0，1，0，9] B.[5，4，3，2，1]
C.[5，8，3，0，0] D.[5，5，6，0，6]
答案　C
解析　循环5次，每次循环有3种可能，一是当i为偶数时，入队一个[1，9] 之间的整数要么，二是当i为奇数时，且q[tail－1]9.有如下Python程序段：
import random
a＝[8，10，2，7，11，9，16]
c＝[0]*len(a)
head＝0；tail＝0
for i in range(len(a)):
　 t＝random.randint(0，1)
　 if tail－head<2 or t＝＝0：
　 c[tail]＝a[i]
　　　tail＝tail＋1
　 elif a[i]>c[head]：
　　　head＝head＋1
print(c[head：tail])
执行该程序段后，输出的内容不可能是(　　)
A.[10，9，16] B.[8，10，11，9，16]
C.[8，10，2，9] D.[10，7，16]
答案　C
解析　若队列中数据元素小于2或者t的值为0，则将a[i]入队，否则当a[i]大于c[head]时出队，a中元素既可以不入队，也可以不出队(t为1，且a[i]小于等于c[head])。A选项8，10入队，2和7可以不入队，11让8出队，队列中只剩下1个元素，9入队，接着t的值为0，16入队。B选项8，10入队后，接着t的值依次为1，1，0，0，0。C选项队首为8，当遍历到11时，要么让8出队，要么产生的t为0，11入队，因此C不可能。D选项11让队首8出队，当遍历到16时，产生的t为0，16入队。
10.有如下Python程序段：
from random import randint
s＝″14257″；q＝[″″]*10; ans＝″″
head＝tail＝0
for i in s：
　 q[tail]＝i
　 tail＋＝1
for i in range(len(s))：
　 t＝randint(0, 1)
　 if t＝＝0：
　 q[tail]＝q[head]
　 tail＋＝1
　 head＋＝1
while tail>head：
　 ans＋＝q[head]
　　head＋＝1
print(ans)
运行该程序段，则输出的值不可能的是(　　)
A.5 B.41 C.457 D.14257
答案　B
解析　本题考查队列的性质。语句q[tail]＝q[head]表示将队首出队，再入队，中间也可能有元素出队，最后输出队列中元素。队列的特性是先进先出，无论有多少元素全部出队后，部分数据再入队，在队列的位置还是按原来的次序排列，因此选项B不可能。
11.有如下Python程序段：
que＝[1，5，3，2，7]＋[0]*100　#构建列表que, 形如[1，5，3，2，7，0，0，0，…]
head＝0；tail＝5
st＝[0]*len(que)　#构建栈st
top＝－1
while　head！＝tail：
　 while top！＝－ 1 and que[head]>st[top]：
　 que[tail]＝st[top]
　　　tail＋＝1
　　　top－＝1
　 top＋＝1
　 st[top]＝que[head]
　 head＋＝1
执行该程序段后，栈st从栈顶到栈底的元素依次为(　　)
A.7，5，3，2，1 B.1，2，3，5，7
C.0，1，2，3，5，7 D.7，5，3，2，1，0
答案　B
解析　程序功能是利用队列将栈中的元素进行升序排列。若栈不为空，当队首元素大于栈顶元素的值时，将栈中元素入队并出栈，否则将队首元素入栈并将队首进行出队操作。(共71张PPT)
专题15　队列
第三部分　数据的存储与逻辑结构
1.通过生活实例，理解队列的性质和作用；
2.在理解队首和队尾指针的功能上，掌握队列和循环队列元素个数的计算方法；
3.在理解队首和队尾指针的功能上，掌握建队、入队和出队的操作过程.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
栈和队列主要用于计算过程中保存的临时数据，为了更好地检索到需要的数据，需要复杂的存储机制，这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。队列是一种在数组两端分别进行存取的数据结构，最大特点是数据在存取时，无需查询，时间复杂度为O(1)，先存取的数据先被取出。队列是一种先进先出、后进后出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列一般按顺序结构存储，可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。在Python中，用列表(数组)创建队列，元素入队时，先将元素存储到tail指针指向位置，然后tail指针加1，即向队尾方向移动。元素出队时，当队列非空时条件head！＝tail，先读取队首head指针指向的元素，然后head指针加1，即向队尾方向移动，直到head＝＝tail为止。
真题再现
2
D
解析　本题考查队列的基本操作。队列每次出队一个元素，若head是3的倍数时，输出队首元素，否则将队首元素入队，p出队并输出，r和i出队后入队，队列中元素依次为ntri，head值为3；n出队并输出，t和r出队后入队，队列中元素依次为itr，head值为6；i出队并输出，t和r出队后入队，队列中元素依次为tr，head值为9；t出队，队列中只剩下元素r，r连续两次出队后再入队，当head为12时，r出队。
考点精练
3
重难点1　队列的特性
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。先进先出是队列的特性，若元素出队后将入队，那么入队后的元素还是维持原来的顺序。建队时，指针head和tail均指向0，head加1表示出队，tail加1表示入队。判断队列是否空的条件是head！＝tail，判断队列中元素的数量为tail－head。
例题 有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
B
思维点拨
明考向 本题考查队列的基本操作
精点拨 数组前面入队，后面出队。TTT操作结果：9，5，8，3，2。Q后队列为：5，8，3，2。再TT之后结果为：3，2，5，8。Q后，队列为：2，5，8
变式 有1个队列，队首到队尾的元素依次为 8，10，12，9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为(　　)
A.2，3 B.6，2，3 C.9，4，5 D.9，4，5，6
D
解析　本题考查队列性质和操作。根据队列的特点“先进先出，后进后出”，8出队后4入队(2次)，10出队后5入队(2次)，12出队后6入队(2次)。共6次，其结果为9，4，5，6。
重难点2　队列的算法实现
头指针head记录队首元素位置，队尾指针tail记录队尾元素的下一个位置，队列q的队尾元素值为q[tail－1]。入队时，需将x赋值给q[tail]，让其成为新的队尾元素，再移动tail指针。出队时，需先将q[head]赋值给x，再移动head指针。
D
思维点拨
明考向 本题考查队列的算法实现
精点拨 遍历data数组，如果data[i]是奇数，入队。data[i]是偶数且队列中至少有2个元素时，队首元素出队且累加到que[tail － 1]元素。遍历到1时，1入队；遍历到2时，队列只有1个元素。遍历到3时，3入队；遍历到1时，1入队；遍历到1时，1出队且累加到队尾，队列为[3，2] ；遍历到3时，3入队
程序运行后，输出的结果是(　　)
A.['a'，'b'，'c'，'d'，'h']
B.['a'，'b'，'c'，'d'，'d']
C.['c'，'d'，'b'，'h'，'a']
D.['a'，'d'，'d'，'d'，'a']
C
解析　本题考查队列基本操作。遍历列表s，当元素不在队列中，将该元素入队，否则将队首元素出队(该元素不入队)。遍历第2个第3个d时，ab出队，队列中有[c，d]，接着bha依次入队。
程序运行后，输出结果可能为(　　)
A.0 0 0 0 2 3 0 6 B.0 1 2 3 4
C.0 0 0 0 D.2 4
C
思维点拨
明考向 本题考查队列的算法实现。队列中初始化4个元素，值均为0。程序一共循环4次，当产生的随机数k为偶数时，将k%5入队，否则出队一个元素
精　点　拨 A 队列中共有8个元素，因此共入队4个元素，但入队的元素值k%5必须小于5
B 队列中共有5个元素，说明入队比出队多一次，设入队x次，出队y次，有表达式x＋y＝4和x－y＝1成立，两者相加得到x不为整数
C 说明入队和出队各2次，两面2个0为后面入队的元素
D 表达式x＋y＝4和x－y＝－2成立，入队1个元素4，出队2个0，但2不可能存在于原队列中
C
解析　本题考查队列的算法实现。i%3的值依次为0，1，2，0，1，队列的特性是先进先出，前5个零以后面入队的数字之前出队。5次操作后，前三项队列中有4个元素，说明出队比入队多1次。A选项0和2入队。B选项1和2入队。C选项1和2入队，但原始队列中没有1。D选项队列中剩余2个元素，出队加入队次数为5，出队比入队多3次，因此出队4次，入队1次，最后一个0入队。
当堂检测
4
重难点1　队列的特性
重难点2　队列的算法实现
1.有一个队列S，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为tail－head＋1
B.新元素入队时，指针head向右移动
C.元素出队时，指针tail向右移动
D.当tail的值为len(S)时，无法再入队新元素
D
解析　本题考查队列性质和基本操作。tail是指向队尾元素后面的位置，因此队列长度为tail－head。 当tail值为len(S)，队尾元素存储在len(S)－1，因此队列已满。
B
解析　本题考查队列的基本知识。队列中元素个数＝tail－head＝4。
2.某队列经过“出队”“入队”操作后，队首指针head＝2，队尾指针tail＝6，则该队列中剩余的元素个数是(　　)
A.2 B.4 C.5 D.6
D
解析　元素1，2入队，1出队后入队，队列为2，1。2出队，1出队后入队，3入队，1出队，因此队列中只有元素3。
3.有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.1 B.1，3 C.3，4 D.3
C
解析　本题考查队列的入队出队操作。删除元素，即进行出队操作，出队时将队首元素删除，然后队首指针加1；插入元素，即进行入队操作，入队时先将元素插入，然后队尾指针加1。共删除3个元素，删除操作结束后，因此队头指针head的值为6，共插入7个元素，操作后队尾指针tail的值为15。
4.若用一个规模为20的数组来实现队列，已知当前队尾指针tail的值为8，队头指针head的值为3，进行如下操作：连续删除2个元素、连续插入5个元素、删除1个元素，连续插入2个元素。则操作后指针head和tail的值分别为(　　)
A.5和14 B.6和14
C.6和15 D.7和15
B
解析　元素A出队，元素B出队后入队，元素C出队，元素D和E出队后入队，元素F出队。
5.队列q中队首至队尾元素依次为“A，B，C，D，E，F”，约定：S为出队操作，U为出队再入队操作，若要使队列q队首至队尾元素依次为“B，D，E”，下列操作可实现的是(　　)
A.USUSSU B.SUSUUS
C.SSSUUU D.SUUSUS
D
解析　操作Q3、Q2之后，队列为空。Q3、Q1，队列为空。因此队列中元素个数为1，Q1操作出队并输出元素，输出的元素个数为1。C选项没有可比性。D选项若队列不为空，则Q3、Q2、Q1、Q2输出的结果不一样。
6.某种特殊的队列 Q，支持以下3个操作：操作Q1，若队列非空，队首元素出队，并输出；操作Q2，若队列非空，队首元素出队；操作Q3，一个元素入队；以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空，依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后，下列说法正确的是(　　)
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
C
解析　程序功能实现查找最长不重复的子串，该子串为'engi'。
执行该程序段后，输出的结果是(　　)
A.ABCDEF B.FEDCBA
C.ACEFDB D.AFCDEB
解析　遍历字符串s，当i%2＝＝0条件成立时，将s[i]入队，否则将s[len(s)－i]入队。
D
执行后，程序输出结果为(　　)
A.12 15 26 36 B.12 15 23 26
C.12 12 15 23 36 D.12 13 15 23 36
C
解析　遍历数组a，若队列不空，且x比队尾元素小，队尾元素不断地出队，再让x入队。整个过程描述为13入队后出队，12，12，15，26依次入队，26出队，23, 36入队。
A
解析　分析程序段可知，该程序段实现的是一种消消乐游戏，即若新遍历到的元素和队首的元素不同或者队列为空，则将新元素入队。若新遍历到的元素和队首的元素相同，则将所有队列中的元素清空。因此队列中最后剩余的元素为 c，d，d，e。
B
解析　队列中初始1个元素，值为4。遍历列表a中位置1到len(a)－1的元素，若遍历的元素值比队尾元素大，则将队首出队后再将a[i]入队。若遍历的元素值小于队首，直接将a[i]入队。队列中元素变化情况为[4, 2]、[2, 5]、[2, 5, 1]、[5, 1, 9]。
C
解析　本题考查队列的算法实现。vis是一个标志数组，当其元素值为0时，可以入队，保证队列中数据是唯一的。当队列中元素个数大于等于3时，将进行出队操作。ans统计入队次数。输入x的值1，2入队，接着1不能入队，5入队，当输入4时，让1出队，4入队。第2个4不能入队，最后一个1入队。
课后练习
5
重难点1　队列的特性
重难点2　队列的算法实现
1.下列有关队列的说法正确的是(　　)
A.队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B.队列的存储结构，可用数组实现，也可用链表实现
C.一队列队头指针head，队尾指针tail, 则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
B
解析　本题考查队列的性质。A选项队列在队尾插入，在队首删除；C选项队尾指针tail指向队尾元素的下一个位置，所以tail－head表示队列中元素个数；D选项软件连续撤销操作是撤销前一步操作，是栈的应用实例。
2.在该系统中，可以利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置，若tail＝head＋3，则现在排队的顾客数量为(　　)
A.2 B.3 C.4 D.5
B
解析　队列的长度计算公式为tail－head，因此队列有3人排队。
3.假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　　)
A.11　12 B.2　5
C.3　6 D.3　5
C
解析　本题考查队列的性质。入队3次，出队4次，在3次入队前tail应为6，在4次出队前head应为3。
4.有2个队列a和b，队首到队尾的元素依次分别为“5，7，9”和“6，4，8”。约定：T操作是指队列a中1个元素先出队，若大于队列b的队首元素则再入b队列，否则不入；Q操作是指队列b中1个元素先出队，若大于队列b的队尾元素则再入b队列，否则不入。则经过TTQQQQT系列操作后，队列b中的元素个数为(　　)
A.1 B.2 C.3 D.4
B
解析　5和7出队，由于7大于6，则7入队列b。6，4，8依次出队，8大于7，队列b中有7，8。第4个Q表示7出队后不入队。最后队列a中9出队入，入队列b，队列b有元素8和9。
C
解析　题目中队列的元素执行队首元素出队，再从队尾入队，接下来队首元素出队从队尾入队，直至队列空，输出的顺序为C选项结果。
5.某队列的数据结构如图所示，head和tail分别是队列的头指针和尾指针。现对该队列进行下列操作：①队首元素出队后再入队；②队首元素出队并输出，重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　　)
A.Python B.Ptoynh
C.yhntPo D.yhntoP
6.约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后，队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5 C.4　5 D.4　6
D
解析　本题考查队列的基本操作。T操作既有入队，又有出队，因此共有6次入队，4次出队，每次出队和入队，指针分别加1。
7.有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.4，5 B.5，4 C.2，4 D.4，2
C
解析　队列的变化情况为12345→34512→4512→1245→245→524→24。
B
解析　B选项先出队后入队，队列中为1，2，3，再依次入栈，出栈的顺序为3，2，1。
9.假设高铁站的售票窗口平均每分钟过来一个人购票，每人的购票时间平均约为2分钟，某车站在中午时段开了一个售票窗口，12：01：00的时候有1个人刚开始购票，3个人在等待，那么12：11：00时队伍中等待购票的人数为(　　)
A.7 B.8 C.9 D.10
C
解析　根据题目描述，10分钟过来了10个人购票，总共14人，其间4人结束购票，所以队伍还有10人，1人在购票，9人在等待。
B
解析　本题考查队列的入队与出队操作。字符串S中两个字符为一组，第1个元素t代表入队或出队，第2个元素代表n入队或出队的次数。A是入队，D是出队，若出队过程中队空，则中止出队。
B
解析　本题考查队列的基本操作。程序的功能是查找队列中最小值，pre初值为10，每次出队一个元素，出队元素也pre比较，记录其最小值的过程。
执行该程序段后，显示的结果是(　　)
A.ACBED B.ABDCE
C.ABDEC D.ACBDE
C
解析　本题考查队列的基本操作。外循环5次，每次先出队一个元素，内循环分别循环0，1，2，3，4次，每次循环将队列元素出队并入队到最后。当i为0时，A出队，不循环移动。i为1时，B出队，C后移，队列中为DEC。 i为2时，D出队，EC后移，队列中为EC。i为3时，E出队，C后移3次，队列中为C。最后C出队。
B
解析　本题考查队列的基本操作。当i的值为2，3，5时，i均不在队列中，因此入列3次，tail＝3，当i的值为1时，条件tail－head＝＝3成立，因此进行出队(队首指向2)操作，队列中值依次为[3, 5]，当i的值为3，5，不符合条件，当i的值为2时，入队。
解析　遍历数组a并累加数组元素值，求队列的最大值；当遍历到的当前值小于队首或是长度大于k，将队首元素出队。s的值依次为[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。
C
执行该程序段后，输出的结果是(　　)
A.bdfyac B.bdfxyz
C.abcyac D.yacbdf
A
解析　本题考查队列的相关操作。表达式(ord(i) － ord(″a″) ＋ q[head]) % 26 的功能是将i转换为在字母表中索引位置，并循环后移q[head]个位置。计算出移动位置后，再转换为小写字母。q中元素实现出队后再入队，因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。
运行该程序段后，q的值可能是(　　)
A.[5，3，8，6，0，1] B.[5，3，0，1，0，2]
C.[2，0，3，0，4，0] D.[0，9，0，10，0，5]
解析　本题考查队列的算法实现。循环6次，当随机数x的值为1时，在队尾生成一个1到10之间的随机数；当x为0时，若队列不为空且队尾大于队首，则将队首出入后再入队尾。因此入队的数据有3种可能性，还有一种可能性是没有新数据入队，tail直接往后移动。A选项若x为1，0不可能产生。若x为0，此时队列不为空，队首值为5，队尾值为6，满足队尾大于队首，5出队后入队。B选项5大于3，5大于1，因此可以不出队。C选项2大于3，因此2要出队后再入队。D选项由于0小于9，0也队后入队，队首为9，由于9小于10，因此最后一个0不可能产生。
B
解析　循环5次，每次循环有3种可能，一是当i为偶数时，入队一个[1，9] 之间的整数要么，二是当i为奇数时，且q[tail－1]C
解析　若队列中数据元素小于2或者t的值为0，则将a[i]入队，否则当a[i]大于c[head]时出队，a中元素既可以不入队，也可以不出队(t为1，且a[i]小于等于c[head])。A选项8，10入队，2和7可以不入队，11让8出队，队列中只剩下1个元素，9入队，接着t的值为0，16入队。B选项8，10入队后，接着t的值依次为1，1，0，0，0。C选项队首为8，当遍历到11时，要么让8出队，要么产生的t为0，11入队，因此C不可能。D选项11让队首8出队，当遍历到16时，产生的t为0，16入队。
C
B
解析　本题考查队列的性质。语句q[tail]＝q[head]表示将队首出队，再入队，中间也可能有元素出队，最后输出队列中元素。队列的特性是先进先出，无论有多少元素全部出队后，部分数据再入队，在队列的位置还是按原来的次序排列，因此选项B不可能。
B
解析　程序功能是利用队列将栈中的元素进行升序排列。若栈不为空，当队首元素大于栈顶元素的值时，将栈中元素入队并出栈，否则将队首元素入栈并将队首进行出队操作。

展开更多......

收起↑