資源簡介

專題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]入隊。]

展開更多......

收起↑