資源簡介

專題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
解析　程序功能是利用隊列將棧中的元素進行升序排列。若棧不為空，當隊首元素大于棧頂元素的值時，將棧中元素入隊并出棧，否則將隊首元素入棧并將隊首進行出隊操作。

展開更多......

收起↑