资源简介

专题13　队　列
学业要求 知　识　点 学业水平等级
1.能结合生活中的实例，掌握队列的概念、存储结构及特性 3
2.能结合队列的应用案例，理解队列元素的入队和出队过程 4
知识点一　队列的性质
【知识梳理】
1.队列是一种________、后进后出的线性表，允许插入的一端称为________，允许删除的一端称为________。
2.队列中的数据元素称为队列元素，在队列中插入一个元素称为________，从队列中删除一个元素称为________。
3.________元素只有一个后继，________元素只有一个前驱，其他元素既有一个前驱，又有一个后继。
4.队列一般按顺序结构存储，可以用数组来实现。设置________和________记录队首元素位置和队尾元素的下一个位置。
5.队列元素个数计算方法：tail－head。
【经典案例】
队列是一种在数组两端分别进行存取的数据结构，最大特点是数据在存取时，无需查询，时间复杂度为O(1)，先存取的数据先被取出。队列是一种先进先出、后进后出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列一般按顺序结构存储，可以用数组来实现。
【例1】 有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
听课笔记：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 有一个队列S，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为tail－head＋1
B.新元素入队时，指针head向右移动
C.元素出队时，指针tail向右移动
D.当tail＝＝len(S)时，无法再入队新元素
【例2】 下列有关队列的说法正确的是(　　)
A.队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B.队列的存储结构，可用数组实现，也可用链表实现
C.一队列队头指针head，队尾指针tail，则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤消操作都是数据结构“队列”的应用实例
思维点拨
明考向 本题考查队列的性质
精点拨 A 队列在队尾插入，在队首删除
C 队尾指针tail指向队尾元素的下一个位置，所以tail－head表示队列中元素个数
D 软件连续撤销操作是撤销前一步操作，是栈的应用实例
听课笔记：____________________________________________________________
______________________________________________________________________
【变式2】 假设队列空间足够，队列中的元素个数为5。约定：T为入队操作，Q为出队操作，则经过TTQQTQTQQ一系列操作之后，队首指针head，队尾指针tail的值可能为(　　)
A.head＝11，tail＝7 B.head＝7，tail＝11
C.head＝9，tail＝12 D.head＝12，tail＝9
知识点二　队列的算法实现
【知识梳理】
1.用列表(数组)创建一个n个空间值为0的队列语句：que＝[0]*n；head＝tail＝0。
2.元素x入队时，先将元素存储到________指针指向位置，然后________指针加1，即向队尾方向移动。语句：que[tail]＝x；tail＋＝1。
3.元素出队时，当队列非空时条件____________，先读取队首head指针指向的元素，然后head指针加1，即向队尾方向移动，直到____________为止。语句：x＝que[head]；head＋＝1。
【经典案例】
头指针head记录队首元素位置，队尾指针tail记录队尾元素的下一个位置，队列q的队尾元素值为q[tail－1]。入队时，考虑队列空间是否充足，当条件tail＝＝len(que)成立时，表示空间已满，不能入队。若队列不满，需将x赋值给q[tail]，让其成为新的队尾元素，再移动tail指针。出队时，先要判断队列是否为空，再将q[head]赋值给x，再移动head指针。
【例1】 列表q长度为20，q[0]至q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为(　　)
head，tail＝0，5
while headif head % 3＝＝0：
print(q[head])
else：
q[tail]＝q[head]
tail＋＝1
head＋＝1
A.t B.n
C.i D.r
思维点拨
明考向 本题考查队列的基本操作
精点拨 队列每次出队一个元素，若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】 有如下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
a＝[″x1″，″x2″，″x3″，″x4″，″x5″，″x6″]
k＝3
sq＝[－1]*len(a)
head＝tail＝i＝0
while i0：
op＝random.randint(0，1)
if op＝＝0 and tail－head>0：
if tail－head>k：
　　　 　print(a[sq[tail－1]]，end＝″ ″)
　　　 　tail －＝1
else：
　　　　 print(a[sq[head]]，end＝″ ″)
　　 　　head＋＝1
elif op＝＝1 and isq[tail]＝i
tail＋＝1
i＋＝1
则程序运行后，输出结果可能的是(　　)
A.x1 x4 x6 x2 x3 x5 B.x4 x1 x6 x2 x3 x5
C.x1 x2 x3 x6 x4 x5 D.x6 x5 x4 x3 x1 x2
思维点拨
明考向 本题考查队列基本操作。循环条件之一为遍历所有元素，因此全部元素依次入队，循环条件之二是队不为空，因此所有元素均要出队，要么队首出队，要么队尾输出，因此每个元素只输出一次
精点拨 A x1出队后，当x4出队时，队列中只有x2 x3 x4长度小于等于3，不可能
B 队列中有x1 x2 x3 x4，x4可以出队，队首x1可以出队，x2 x3 x5 x6，x6可以输出，再接着剩余元素出队
C x1 x2 x3前面3个元素依次入队并马上出队，当x6入队时，队列中只有3个元素
D 当x4出队后，队列中剩余x1 x2 x3，要依次出队
听课笔记：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 有Python程序段如下：
import random
q＝[″″]*100；head＝tail＝0；ans＝″″
s＝input()
for i in range(len(s))：
q[tail]＝s[i]；tail＋＝1
while headx＝random.randint(0，1)#随机生成整数 0 或 1
ans＋＝q[head]；head＋＝1
if headq[tail]＝q[head]
tail＋＝1；head＋＝1
print(ans)
当s的输入值为″Hello－world！″时，程序输出的结果不可能是(　　)
A.Hll－wrd！eool B.Hell－wordol!
C.Hlo－ord！elwl D.eHll－wrd！ool
1.下列对队列的描述，不正确的是(　　)
A.队列的特点是先进先出
B.在队列中，允许插入的一端称为队尾，允许删除的一端称为队首
C.刚建立的空队列，队首指针和队尾指针均指向0
D.出队操作时，先将head指针加1，然后再将队首元素出队
2.幼儿园中8个小朋友，依次编号(1－8)玩游戏，按编号顺序排队围成一圈，由编号1号的小朋友开始报数，报数报到3的小朋友出列，下一个编号的小朋友又从1开始报数，一直反复直到剩下最后一人，请问在该问题上采用的适合数据结构和剩下的小朋友的编号是(　　)
A.二叉树7 B.队列7
C.栈4 D.链表4
3.某队列的数据结构如图所示，head和tail分别为队列的头、尾指针。现对该队列进行以下操作：①队首元素出队输出　②队首元素出队再入队，重复①②操作直到队列为空。
若队列数据元素为“CHINA”，则输出顺序是(　　)
A.CIANH B.CIAHN
C.CAHNI D.CHINA
4.小明在使用队列解决问题的过程中，初始时(空队列)，队列的队首指针head＝0，队尾指针tail＝0，经过一系列入队、出队操作后，head＝4，tail＝7。在不考虑队列溢出的情况下，小明接下来进行的操作序列为出队、入队、出队、出队、入队、出队，此时head和tail的值分别为(　　)
A.7　8 B.7　9
C.8　9 D.9　10
5.若用一个规模为20的数组来实现队列，已知当前队尾指针tail的值为8，队首指针head的值为3，进行如下操作：连续删除2个元素、连续插入5个元素、删除1个元素，连续插入2个元素。则操作后指针head和tail的值分别为(　　)
A.5和14 B.6和14
C.6和15 D.7和15
6.有如下Python程序：
q＝[0]*6
q[0]＝1
head＝0；tail＝1
while tailx＝q[head]
if x%2＝＝0：
q[tail]＝x//2
tail＋＝1
else：
q[tail]＝x*2
q[tail＋1]＝x*3
tail＋＝2
head＋＝1
程序运行后，tail－head的值为(　　)
A.3 B.4
C.5 D.6
7.有如下程序段：
s＝input()
head＝0；tail＝0；ans＝0；tmp＝''
q＝['']*100
flag＝True
for i in range(len(s))：
if s[i]＝＝'，'：
while head！＝tail：
　　 　　tmp＋＝q[head]
　　 　　head＋＝1
　　 　　if flag and head　　　 　　　head＋＝1
　　　 　flag＝not flag
ans＋＝int(tmp)
tmp＝''；flag＝True
elif '0'<＝s[i]<＝'9'：
q[tail]＝s[i]
tail＋＝1
若输入s为″1－500，2023900－，″，执行该程序段，变量ans的值为(　　)
A.100 B.22300
C.22351 D.22400
8.有如下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
9.有如下Python程序段：
q＝[1，2，3，4，5，6，7，8，9]
f，r＝0，8
n＝int(input())
while rcur＝q[f]
f＝f＋1
m＝cur % 10
if m＝＝0：
q.append(cur*10＋m)
q.append(cur*10＋m＋1)
r＋＝2
elif m＝＝9：
q.append(cur*10＋m－1)
q.append(cur*10＋m)
r＋＝2
else：
q.append(cur*10＋m－1)
q.append(cur*10＋m)
q.append(cur*10＋m＋1)
r＋＝3
对于该程序，下列说法正确的是(　　)
A.q[12]的值是20
B.若程序输入n的值等于21，则列表q中的元素个数是22个
C.对列表任一元素q[i](9≤i≤r)，其个、十、百、千……等相邻位上的数值相差都不超过1
D.q中元素值递增，且任意相邻两个元素q[i]和q[i＋1](0≤i10.有如下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 headprint(que[head]，end＝″″)
head＝head＋1
执行该程序段后，输出的结果是(　　)
A.ABCDEF B.FEDCBA
C.ACEFDB D.AFCDEB
专题13　队　列
知识点一
知识梳理
1.先进先出　队尾　队首
2.入队　出队
3.队首　队尾
4.头指针head　尾指针tail
经典案例
例1　B
变式1　D　[本题考查队列性质和基本操作。tail是指向队尾元素后面的位置，因此队列长度为tail－head。当tail值为len(S)，队尾元素存储在len(S)－1，因此队列已满。]
例2　B
变式2　B　[本题考查队列基本操作。经过4次入队，5次出队，因此队列中共有4个元素。由于队列空间足够，因此队尾指针大于队首指针。A选项队尾应大于队首。B选项队列中元素个数为11－7＝4，符合题目要求。C选项队尾应大于队首。D选项队列中元素个数为12－9＝3，不符合题目要求。]
知识点二
知识梳理
2.tail　tail
3.head！＝tail　head＝＝tail
经典案例
例1　D
变式1　C　[本题考查队列基本操作。遍历列表s，当元素不在队列中，将该元素入队，否则将队首元素出队(该元素不入队)。遍历第2个第3个d时，ab出队，队列中有['c'，'d']，接着'bha'依次入队。]
例2　B
变式2　D　[本题考查队列基本操作。先将输入的s依次入队，每次出队一个元素，若产生x的值为0，将出队的元素再次入队。根据队列先进先出的特性，先入队的元素必先出队，A选项Hll－wrd！是先出队的，那么eool是中间出队再入队的，因此正确。B选项同A选项。C选项同A选项。D选项第一个必须是H出队。]
当堂过关检测
1.D　[本题考查队列的性质。head指针指向队首，先取出值，再出队。]
2.B　[本题考查数据结构的相关知识。适合的数据结构应为队列，出队的顺序为：3 6 1 5 2 8 4，最后剩下的一人编号为7。]
3.A　[队列的变化情况为CHINA→INAH→AHN→NH→H。]
4.C　[在这个操作过程中，每次出队都是成功的，总共出队4次，入队2次，所以head和tail的值分别变为8和9。]
5.C　[本题考查队列的入队出队操作。删除元素，即进行出队操作，出队时将队首元素删除，然后队首指针加1；插入元素，即进行入队操作，入队时先将元素插入，然后队尾指针加1。共删除3个元素，删除操作结束后，因此队头指针head的值为6，共插入7个元素，操作后队尾指针tail的值为15。]
6.A　[运行结束后q＝[1，2，3，1，6，9]，head＝3，tail＝6。]
7.D　[本题考查队列的程序实现。在for循环中，当s[i]的值为数字字符时，将s[i]放入队列中；当s[i]为'，'时，将队列中的字符出队并连接。当flag为True时，字符出队但不连接到tmp中；其余字符忽略不处理。因此当输入的字符串为″1－500，2023900－，″时，遇到第一个'，'字符，则ans加上100，然后再对于进入队列中的字符串″2023900″进行计算，故最后的结果为22400。]
8.A　[本题考查队列的相关操作。表达式(ord(i)－ord(″a″)＋q[head])%26的功能是将i转换为在字母表中索引位置，并循环后移q[head]个位置。计算出移动位置后，再转换为小写字母。q中元素实现出队后再入队，因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。]
9.C　[本题考查队列的应用。f为队首指针，r为队尾指针。将队首元素取出后，取队首元素的个位数(即语句m＝cur%10)，然后将与个位数m相差±1范围内的两个或三个数连接到cur后面，产生新的数并入队。每次至少有两个元素入队，至多有三个元素入队。A选项模拟出队列的前13个数[1，2，3，4，5，6，7，8，9，10，11，12，21]，q[12]＝21而不是20。B选项当r＝20时循环入队的有3个元素，因此跳出循环时r＝23，队列q中共有24个元素。D选项q中元素初始有序，之后每取一个队首元素时都已以递增的方式加入元素，因此所有元素也是有序的。不是每个相邻元素都是相差为1，如1取出后加入的值是10、11和12，接下来加入的是由2生成的数，分别是21、22、23，其中12和21相差不为1。]
10.D　[遍历字符串s，当i%2＝＝0条件成立时，将s[i]入队，否则将s[len(s)－i]入队。]

展开更多......

收起↑