資源簡介

(共77張PPT)
課時2　隊　列
第三章　字符串、隊列和棧
1.通過問題解決，理解隊列的概念和特性。2.掌握隊列的基本操作，并能編程實現。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.隊列的概念
先進先出
(1)隊列是一種____________的線性表，允許______的一端稱為隊尾，允許______的一端稱為隊首。
(2)隊列中的數據元素稱為____________。
插入
刪除
隊列元素
2.隊列的特性
(1)___________________________。
(2)_______________。
隊頭指針指向實際隊頭元素的位置，而隊尾指針指向實際隊尾元素所在的后一個位置。
先進先出、后進后出
有限序列性
3.隊列的基本操作
(1)隊列的存儲
①順序存儲
隊列的順序存儲指用一段地址連續的內存單元依次存儲在隊列中的數據元素。
順序存儲的隊列稱為順序隊列，可用數組來實現。
②隊列的鏈式存儲
隊列的鏈式存儲指用一組任意(不要求連續)的內存單元存儲隊列中的數據元素及數據元素間的關系。
鏈式存儲的隊列稱為鏈隊列，用鏈表來實現，一個鏈式隊列由一個頭指針和一個尾指針共同確定。
(2)隊列的操作(建隊、入隊、出隊)的實現
①順序隊列
m＝100　#隊列規模
head＝tail＝0
que＝[″″]*m　#建隊
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入隊操作，輸入#結束
if tail＝＝m：
print(″隊列已滿！″)
else：
que[tail]＝data
tail＋＝1
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
②循環隊列
m＝100　#隊列規模
head＝tail＝0
que＝[″″]*m　　　　 #建隊
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入隊操作，輸入#結束
if (tail＋1)%m＝＝head：
print(″隊列已滿！″)
else：
que[tail]＝data
tail＝(tail＋1)%m
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
③鏈隊列
class Queue()：
def _ _init _ _(self)：
self.queue＝[]
def queue_in(self，data)：
#data插入隊列
self.queue.insert(0，data)
def queue_out(self)：
#取出隊首元素
if len(self.queue)：
　　　　return self.queue.pop()
return ″隊列已空″
4.與隊列有關的Python模塊
Python內建有queue模塊，在這個模塊內可以使用Queue()建立對象，然后可以使用下列方法執行queue的操作。
from queue import Queue
q＝queue()
for i in range(3)：
q.put(i)
while not q.empty()：
print(q.get())
Queue類中定義的方法
方法 功能描述
put() 在隊尾插入數據
get() 在隊首取出數據
qsize() 返回隊列的長度，即隊列中的元素個數
empty() 判斷隊列是否為空，返回值為True或False
full() 判斷隊列是否為滿，返回值為True或False
例題精析
2
例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
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
解析　本題考查隊列性質和操作。根據隊列的特點“先進先出，后進后出”，8 出隊后4入隊(2 次), 10 出隊后5入隊(2 次)，12 出隊后6入隊(2 次)。共 6 次，其結果為 9，4，5，6。
D
例2 小明在使用隊列解決問題的過程中，初始時(空隊列)，隊列的隊首指針head＝0，隊尾指針tail＝0，經過一系列入隊、出隊操作后， head＝4，tail＝7。在不考慮隊列溢出的情況下，小明接下來進行的操作序列為出隊、入隊、出隊、出隊、入隊、出隊，此時head和tail的值分別為(　　)
A.7和8 B.7和9 C.8和9 D.9和10
解析　在這個操作過程中，每次出隊都是成功的，總共出隊4次，入隊2次，所以head和tail的值分別變為8和9。
C
變式訓練　若用一個規模為20的數組來實現隊列，已知當前隊尾指針tail的值為8，隊頭指針head的值為3，進行如下操作：連續刪除2個元素、連續插入5個元素、刪除1個元素，連續插入2個元素。則操作后指針head和tail的值分別為(　　)
A.5和14 B.6和14 C.6和15 D.7和15
解析　本題考查隊列的入隊出隊操作。刪除元素，即進行出隊操作，出隊時將隊首元素刪除，然后隊首指針加1；插入元素，即進行入隊操作，入隊時先將元素插入，然后隊尾指針加1。共刪除3個元素，刪除操作結束后，因此隊頭指針head的值為6，共插好入7個元素，操作后隊尾指針tail的值為15。
C
例3 列表q長度為20，q[0]至q[4]的值依次為'p'，'r'，'i'，'n'，'t'，執行如下程序段后，輸出的最后一個字符為(　　)
D
head，tail＝0，5
while head　if 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出隊。
變式訓練　執行如下程序段后，變量length的值為(　　)
C
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
解析　程序功能實現查找最長不重復的子串，該子串為'engi '。
例4 有如下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
變式訓練　有如下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
解析　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入隊。
C
隨堂檢測
3
1.有一個隊列 S，其中指針 head 指向隊首元素的位置，指針 tail 指向隊尾元素的下一個位置。關于該隊列說法正確的是(　　)
D
解析　本題考查隊列性質和基本操作。tail是指向隊尾元素后面的位置，因此隊列長度為tail－head。 當tail值為len(S)，隊尾元素存儲在len(S)－1，因此隊列已滿。
A.隊列中元素個數為 tail－head＋1
B.新元素入隊時，指針 head 向右移動
C.元素出隊時，指針 tail 向右移動
D.當 tail＝＝len(S)時，無法再入隊新元素
2.有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。
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.某隊列的數據結構如圖所示，head 和 tail 分別是隊列的頭指針和尾指針。
C
解析　題目中隊列的元素執行隊首元素出隊，再從隊尾入隊，接下來隊首元素出隊從隊尾入隊，直至隊列空，輸出的順序為C選項結果。
現對該隊列進行下列操作：①隊首元素出隊后再入隊；②隊首元素出隊并輸出，重復①②操作直到隊列為空。若隊列的數據元素為“Python”，則輸出的順序是(　　)
A.Python B.Ptoynh C.yhntPo D.yhntoP
5.有如下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])
C
程序運行后，輸出的結果是(　　)
A.['a'，'b'，'c'，'d'，'h'] 　B.['a'，'b'，'c'，'d'，'d']
C.['c'，'d'，'b'，'h'，'a'] 　D.['a'，'d'，'d'，'d'，'a']
解析　本題考查隊列基本操作。遍歷列表s，當元素不在隊列中，將該元素入隊，否則將隊首元素出隊(該元素不入隊)。遍歷第2個第3個d時，ab出隊，隊列中有[c，d]，接著bha依次入隊。
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
執行該程序段后，輸出的結果是(　　)
A.bdfyac B.bdfxyz C.abcyac D.yacbdf
解析　本題考查隊列的相關操作。表達式(ord(i)－ord(″a″)＋q[head]) % 26 的功能是將i轉換為在字母表中索引位置，并循環后移q[head]個位置。計算出移動位置后，再轉換為小寫字母。q中元素實現出隊后再入隊，因此分別將a、b、c和x、y、z對應位置字母后稱1、2、3位置。
7.有如下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]
D
tail＝tail＋1
while head　print(que[head]，end＝″″)
　head＝head＋1
解析　遍歷字符串s，當i%2＝＝0條件成立時，將s[i]入隊，否則將s[len(s)－i]入隊。
執行該程序段后，輸出的結果是(　　)
A.ABCDEF B.FEDCBA C.ACEFDB D.AFCDEB
8.有如下程序段：
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
B
運行該程序段后，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不可能產生。
4
鞏固與提升
基礎鞏固
能力提升
一、基礎鞏固
1.下列有關隊列的說法正確的是(　　)
B
解析　本題考查隊列的性質。A選項隊列在隊尾插入，在隊首刪除；C選項隊尾指針tail指向隊尾元素的下一個位置，所以tail－head表示隊列中元素個數；D選項軟件連續撤銷操作是撤銷前一步操作，是棧的應用實例。
A.隊列是一種先進先出的線性表，插入一端為隊首，刪除一端稱隊尾
B.隊列的存儲結構，可用數組實現，也可用鏈表實現
C.一隊列隊頭指針head，隊尾指針tail，則tail－1－head表示隊列中元素個數
D.學生排隊就餐與軟件連續撤消操作都是數據結構“隊列”的應用實例
2.有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。
3.創建一個容量為 3 的隊列，元素 2，3，5，1，3，5，2 依次等待入隊。入隊規則為：
①若當前待入隊元素已經在隊列中，則跳過該元素，否則轉②
②若當前隊列已滿，將隊首元素出隊列，否則轉③
③將當前待入隊元素入隊列
操作完成后，隊列中的元素為(　　)
A.2，3，5，1 B.1，2，3，5
C.2，3，5 D.5，1，2
D
解析　本題考查隊列性質。2，3，5入隊，隊滿。2出隊，1入隊，隊列為3，5，1；3和5在隊列中，跳過該元素。3出隊，才能讓2入隊，隊列中元素為5，1，2。
4.某種特殊的隊列 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輸出的結果不一樣。
5.假設隊列空間足夠，隊列中的元素個數為 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
B
解析　本題考查隊列基本操作。經過4次入隊，5次出隊，因此隊列中共有4個元素。由于隊列空間足夠，因此隊尾指針大于隊首指針。A選項隊尾應大于隊首。B選項隊列中元素個數為11－7＝4，符合題目要求。C選項隊尾應大于隊首。D選項隊列中元素個數為12－9＝3，不符合題目要求。
6.列表q長度為20，q[0]到q[7]的值依次為'a'，'b'，'c'，'a'，'c'，'d'，'d'，'e'，執行如下程序段后，輸出的結果為(　　)
A
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
解析　分析程序段可知，該程序段實現的是一種消消樂游戲，即若新遍歷到的元素和隊首的元素不同或者隊列為空，則將新元素入隊。若新遍歷到的元素和隊首的元素相同，則將所有隊列中的元素清空。因此隊列中最后剩余的元素為 c，d，d，e。
7.有如下程序段：
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
C
　 　　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
解析　本題考查隊列的算法實現。vis是一個標志數組，當其元素值為0時，可以入隊，保證隊列中數據是唯一的。當隊列中元素個數大于等于3時，將進行出隊操作。ans統計入隊次數。輸入x的值1，2入隊，接著1不能入隊，5入隊，當輸入4時，讓1出隊，4入隊。第2個4不能入隊，最后一個1入隊。
8.執行如下程序段后，輸出的結果是(　　)
B
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
解析　本題考查隊列的基本操作。程序的功能是查找隊列中最小值，pre初值為10，每次出隊一個元素，出隊元素與pre比較，記錄其最小值的過程。
9.有如下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
A.18 B.19 C.21 D.22
C
　s＋＝i
　if ansans＝s
　while ik：
s－＝q[head]
head＝head＋1
執行該程序段后，輸入k的值為2，變量ans的值是(　　)
解析　遍歷數組a并累加數組元素值，求隊列的最大值；當遍歷到的當前值小于隊首或是長度大于k，將隊首元素出隊。s的值依次為[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。
10.有如下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)：
B
　　 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]
解析　本題考查隊列的入隊與出隊操作。字符串S中兩個字符為一組，第1個元素t代表入隊或出隊，第2個元素代表n入隊或出隊的次數。A是入隊，D是出隊，若出隊過程中隊空，則中止出隊。
11.有如下程序段：
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
D
　　　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
解析　本題考查隊列的程序實現。在for循環中，當s[i]的值為數字字符時，將s[i]放入隊列中；當s[i]為’，’時，將隊列中的字符出隊并連接。當flag為True時，字符出隊但不連接到tmp中；其余字符忽略不處理。因此當輸入的字符串為“1－500，2023900－，”時，遇到第一個’，’字符，則ans加上100，然后再對于進入隊列中的字符串“2023900”進行計算，故最后的結果為22400。
12.某市舉辦科技嘉年華活動，為了激發學生的參與積極性，舉辦方推出了玩游戲得積分，積分兌換禮物的活動。活動中游戲分為簡單和困難兩種，參與游戲就可以獲得相應的積分，當完成困難游戲時，除了獲得相應積分外，還可獲得一張“積分翻倍卡”，一張“積分翻倍卡”可用于一個簡單游戲，使簡單游戲的積分翻倍。
“積分翻倍卡”使用規則如下：
1)當簡單游戲開始時，如果有“積分翻倍卡”可用，則一定會使用。
2)“積分翻倍卡”需在15分鐘內使用。比如困難游戲完成時間是9：15分，則獲得的“積分翻倍卡”將在9：15分激活，且超過9：30分將失效。
3)如果有多張“積分翻倍卡”，則優先使用最早的“積分翻倍卡”。
某同學的游戲記錄如圖a所示(類型0表示困難游戲，類型1表示簡單游戲)，小明讀取游戲記錄，編寫Python程序計算出該同學游戲的最終得分。程序運行結果如圖b 所示，請回答下列問題：
序號 類型 積分 開始時間 完成時間
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
圖a
(1)若某同學參加游戲的記錄如圖c所示，則他獲得的積分是________分。
(2)定義如下函數 change(t)，參數t為游戲時間，函數功能是將時間t轉換為分鐘并返回。如：t＝″9：20″時，轉換為整數(分鐘)值是560，函數返回值為560。
函數代碼如下，請在劃線處填入合適的語句。
def change(t): #參數t的時間格式為：″小時：分鐘″
m＝t.split(″：″)　　
s＝____________
return s
(3)計算游戲積分的部分Python程序如下，請在劃線處填入合適的代碼。
從Excel文件中讀取游戲過程記錄，存儲在列表s 中，如s＝[[1，0，10，550，565]，[2，1，3，565，568]，...]，s[i]表示第i個游戲記錄，s[i][0]，s[i][1]，s[i][2]，s[i][3]，s[i][4]依次存儲游戲的序號、類型、積分、開始時間，完成時間；當游戲類型s[i][1]值為日時表示困難游戲，為1則表示簡單游戲；
將困難游戲取出存入列表a中，列表 a按游戲完成時間升序排序；
將簡單游戲取出存入列表b中，列表b按游戲開始時間升序排序，代碼略
que＝[－1]*(len(a)＋len(b)＋1)
head＝tail＝0
total＝0
for i in range(len(a)): #累加游戲積分，將“積分翻倍卡”激活時間加入隊列
total＋＝a[i][2]
①____________
tail＋＝1
for i in range(len(b)) ：
　 while head　 print(que[head]∥60，″： ″，que[head] % 60，″時刻生效的″＋″積分翻倍卡過期；″)
　 head＋＝1
　　if head　 print(b[i][3]∥60，″：″，b[i][3]%60，″時刻使用了積分翻倍卡；″)
　③____________
　head＋＝1
　　else：
　total＋＝b[i][2]
print(″總共獲得積分為： ″，total，″分，″，″剩余積分卡有： ″，tail－head，″張。″)
答案　(1)40　(2)int(m[0])*60＋int(m[1])
(3)①que[tail]＝a[i][4]
②que[head]＋15③total＋＝b[i][2]*2或total＝total＋b[i][2]*2
解析　本題考查隊列的基本操作。(1)完成困難游戲獲得積分翻倍卡，一張積分翻倍卡使簡單游戲的積分翻倍，但積分卡在15分鐘內有效，14：47激活卡，15：10已經過期。積分為10＋5*2＋15＋5。(2)將時間按冒號分隔，得到一個列表，列表中有兩個值，分別為m[0]和m[1]。(3)①將積分卡激活時間加入隊列，困難游戲完成時間就是卡激活時間。②遍歷列表b，簡單游戲一開始就可以使用翻倍卡，因此計算翻倍卡的激活時間與當前簡單游戲開始時間的時間差，該時間差大于15分鐘時，卡失效。③使用翻倍卡，積分將翻倍。
13.某文本編輯軟件可以把所做的文本編輯操作記錄下來，并通過撤銷和恢復命令來撤銷一步操作或恢復一步撤銷的操作，也可以通過數字命令一次性撤銷最近的多步文本編輯操作，如圖所示。
設計算法模擬該功能。約定：①操作記錄只存儲文本編輯指令；②存儲步數最多為 5步，存滿后早期的操作記錄將被覆蓋；③程序只顯示操作記錄的可“撤銷”記錄，可 “恢復”記錄不顯示；④一旦有新的文本編輯操作，則清空所有可“恢復”記錄。
人機交互的指令如下(所有操作示例都基于上一個示例結果繼續操作)：
類型 指令 示例 程序輸出結果
文本 編輯 “T1”、“T2”、“T3”、“T4”表示四種文本編輯操作 對文本依次做“ T1 ” 、 “T2”、“T3”、“T4” 操作后，再輸入指令“T2” 請輸入操作指令：T2
指令B可用：指令F不可用
可撤銷記錄：T1/T2/T3/T4/T2/
撤銷 “B”表示撤銷 1 步操作 輸入“B” 結果：撤銷最近一步操作 “T2” 請輸入操作指令：B
指令B可用：指令F可用
可撤銷記錄：T1/T2/T3/T4/
數字“1”～“5”表示撤銷多步操作 輸入“3” 結果：撤銷最近 3 步操作 “T4”、“T3”和“T2” 請輸入操作指令：3
指令B可用：指令F可用
可撤銷記錄：T1/
恢復 “F”表示恢復 1 步撤銷的文本編輯操作 輸入“F” 結果：恢復最近的 1 步文本編輯操作“T2” 請輸入操作指令：F
指令B可用；指令F可用
可撤銷記錄：T1/T2/
文本 編輯 在撤銷或恢復操作之后繼續新的文本編輯操作 輸入“T1” 結果： 可“ 恢復” 記錄 “T3”、“T4”、“T2” 被清空 請輸入操作指令：T1
指令B可用；指令F不可用
可撤銷記錄：T1/T2/T1/
所有指令均可使用多次。每次輸入一個指令后都輸出“F”指令和“B”指令是否可用以及當前可撤銷記錄。所有無效操作指令輸入后均提示“Input Error！”。輸入“#”則結束程序。請回答下列問題：
(1)由題意可知，當依次執行指令“T2”、“T2”、“T1”、“T3”、“T1”、“T4”，則最終可撤銷記錄共有__________個。
(2)模擬實現該功能的 Python 代碼如下，請在劃線處填入合適的代碼。
def printh(head，cur)：
　print(f[flag[0]*2＋flag[1]])
　 s＝″可撤銷記錄：″
　 while head！＝cur＋1:
　s＝s＋hist[head]＋″/″
　①____________
　print(s)
opera＝[″T1″，″T2″，″T3″，″T4″]
f＝{0：″指令 B 不可用；指令 F 不可用″，1：″指令 B 不可用；指令 F 可用″，2：″指令 B 可用；指令 F 不可用″，3：″指令 B 可用；指令 F 可用″}
maxn＝5 #歷史記錄最多存儲的步數
maxsize＝100 #設定最多輸入文本編輯指令 100 次
hist＝[″″]*maxsize
cur＝－1；tail＝0；head＝0
flag＝[0，0] #記錄指令 B 與指令 F 的狀態
while True：
　d＝input(″請輸入操作指令：″)
　if d＝＝″#″： break
　if d in opera：
　if ②____________：
　　　head＝head＋1
　cur＝cur＋1；hist[cur]＝d
　tail＝cur＋1
　flag＝[1，0]
　printh(head，cur)
　　elif ″1″<＝d<＝str((cur－head＋1)):
　 cur＝③____________
　if cur＝＝head－1:
　　　flag[0]＝0
　flag[1]＝1
printh(head，cur)
　　elif d＝＝″F ″and tail！＝cur＋1:
　#恢復功能代碼略
(3)若加框處代碼誤寫為“d＝＝″B″”，會導致某些情況下無法得到符合判斷功能的結果。下列 4 組數據中能測試出這一問題的是__________(多選，填字母)
選項 依次輸入下列操作指令
A “B”
B “T1”、“B”、“B”
C “T1”、“1”、“B”
D “T1”、“T2”、“B”
答案　(1)5　(2)① head＋＝1　②cur－head＋1＝＝maxn或tail＝＝cur＋l and tail－head＝＝maxn　③cur－int(d)　(3)ABC
解析　本題考查隊列的基本操作。(1)存儲步數最多為 5步，存滿后早期的操作記錄將被覆蓋。(2)①head表示隊首，cur表示最后一個元素指針，每輸出一個元素，就要出隊。②當d是文本編輯指令時，存儲步數最多為 5步，超出隊首元素將不能撤消。cur初值為－1，一個元素入隊后，值為0，因此cur表示列隊中最后一個元素，因此隊列總共元素個數為cur＋1－head。③當d為撤消步數時，cur表示撤消后的元素位置，因此cur將減去int(d)的值。(3)A選項cur小于head無法輸出。B選項撤消一步后，效果同A。C選項1表示撤消一步，效果同B。D選項有兩個元素，可以輸出。課時2　隊　列
課時目標
1.通過問題解決，理解隊列的概念和特性。2.掌握隊列的基本操作，并能編程實現。
1.隊列的概念
(1)隊列是一種____________的線性表，允許________的一端稱為隊尾，允許________的一端稱為隊首。
(2)隊列中的數據元素稱為____________。
2.隊列的特性
(1)________________。
(2)______________。
隊頭指針指向實際隊頭元素的位置，而隊尾指針指向實際隊尾元素所在的后一個位置。
3.隊列的基本操作
(1)隊列的存儲
①順序存儲
隊列的順序存儲指用一段地址連續的內存單元依次存儲在隊列中的數據元素。
順序存儲的隊列稱為順序隊列，可用數組來實現。
②隊列的鏈式存儲
隊列的鏈式存儲指用一組任意(不要求連續)的內存單元存儲隊列中的數據元素及數據元素間的關系。
鏈式存儲的隊列稱為鏈隊列，用鏈表來實現，一個鏈式隊列由一個頭指針和一個尾指針共同確定。
(2)隊列的操作(建隊、入隊、出隊)的實現
①順序隊列
m＝100　#隊列規模
head＝tail＝0
que＝[″″]*m　#建隊
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入隊操作，輸入#結束
if tail＝＝m：
print(″隊列已滿！″)
else：
que[tail]＝data
tail＋＝1
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
②循環隊列
m＝100　#隊列規模
head＝tail＝0
que＝[″″]*m　　　　 #建隊
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入隊操作，輸入#結束
if (tail＋1)%m＝＝head：
print(″隊列已滿！″)
else：
que[tail]＝data
tail＝(tail＋1)%m
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
③鏈隊列
class Queue()：
def _ _init _ _(self)：
self.queue＝[]
def queue_in(self，data)：
#data插入隊列
self.queue.insert(0，data)
def queue_out(self)：
#取出隊首元素
if len(self.queue)：
　　　　return self.queue.pop()
return ″隊列已空″
4.與隊列有關的Python模塊
Python內建有queue模塊，在這個模塊內可以使用Queue()建立對象，然后可以使用下列方法執行queue的操作。
from queue import Queue
q＝queue()
for i in range(3)：
q.put(i)
while not q.empty()：
print(q.get())
Queue類中定義的方法
方法 功能描述
put() 在隊尾插入數據
get() 在隊首取出數據
qsize() 返回隊列的長度，即隊列中的元素個數
empty() 判斷隊列是否為空，返回值為True或False
full() 判斷隊列是否為滿，返回值為True或False
例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
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有 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＝0，隊尾指針tail＝0，經過一系列入隊、出隊操作后， head＝4，tail＝7。在不考慮隊列溢出的情況下，小明接下來進行的操作序列為出隊、入隊、出隊、出隊、入隊、出隊，此時head和tail的值分別為(　　)
A.7和8 B.7和9 C.8和9 D.9和10
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　若用一個規模為20的數組來實現隊列，已知當前隊尾指針tail的值為8，隊頭指針head的值為3，進行如下操作：連續刪除2個元素、連續插入5個元素、刪除1個元素，連續插入2個元素。則操作后指針head和tail的值分別為(　　)
A.5和14 B.6和14 C.6和15 D.7和15
例3 列表q長度為20，q[0]至q[4]的值依次為'p'，'r'，'i'，'n'，'t'，執行如下程序段后，輸出的最后一個字符為(　　)
head，tail＝0，5
while head　if head % 3＝＝0：
print(q[head])
else：
q[tail]＝q[head]
tail＋＝1
head＋＝1
A.t B.n C.i D.r
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　執行如下程序段后，變量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
例4 有如下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
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下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.有一個隊列 S，其中指針 head 指向隊首元素的位置，指針 tail 指向隊尾元素的下一個位置。關于該隊列說法正確的是(　　)
A.隊列中元素個數為 tail－head＋1
B.新元素入隊時，指針 head 向右移動
C.元素出隊時，指針 tail 向右移動
D.當 tail＝＝len(S)時，無法再入隊新元素
2.有1個隊列，隊首到隊尾的元素依次為1，2，3，4，5。約定：T操作是指隊列中1個元素出隊后再入隊，Q操作是指隊列中1個元素出隊。則經過TTQTTQTTQ系列操作后，隊列中隊首到隊尾的元素依次為(　　)
A.4，5 B.5，4 C.2，4 D.4，2
3.假設隊列的空間足夠，隊首指針head和隊尾指針tail經過“出隊、入隊、出隊、出隊、入隊、入隊、出隊”這一系列操作后，head＝7，tail＝9。則操作前的head和tail的值分別為(　　)
A.11　12 B.2　5 C.3　6 D.3　5
4.某隊列的數據結構如圖所示，head 和 tail 分別是隊列的頭指針和尾指針。
現對該隊列進行下列操作：①隊首元素出隊后再入隊；②隊首元素出隊并輸出，重復①②操作直到隊列為空。若隊列的數據元素為“Python”，則輸出的順序是(　　)
A.Python B.Ptoynh C.yhntPo D.yhntoP
5.有如下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']
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.有如下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
8.有如下程序段：
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]
課時2　隊　列
知識梳理
1.(1)先進先出　插入　刪除　(2)隊列元素
2.(1)先進先出、后進后出　(2)有限序列性
例題精析
例1　B　[本題考查隊列的基本操作。數組前面入隊，后面出隊。TTT操作結果：9，5，8，3，2。Q后隊列為：5，8，3，2。再TT之后結果為：3，2，5，8。Q后，隊列為：2，5，8。]
變式訓練　D　[本題考查隊列性質和操作。根據隊列的特點“先進先出，后進后出”，8 出隊后4入隊(2 次), 10 出隊后5入隊(2 次)，12 出隊后6入隊(2 次)。共 6 次，其結果為 9，4，5，6。]
例2　C　[在這個操作過程中，每次出隊都是成功的，總共出隊4次，入隊2次，所以head和tail的值分別變為8和9。]
變式訓練　C　[本題考查隊列的入隊出隊操作。刪除元素，即進行出隊操作，出隊時將隊首元素刪除，然后隊首指針加1；插入元素，即進行入隊操作，入隊時先將元素插入，然后隊尾指針加1。共刪除3個元素，刪除操作結束后，因此隊頭指針head的值為6，共插好入7個元素，操作后隊尾指針tail的值為15。]
例3　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出隊。]
變式訓練　C　[程序功能實現查找最長不重復的子串，該子串為'engi '。]
例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入隊。]
隨堂檢測
1.D　[本題考查隊列性質和基本操作。tail是指向隊尾元素后面的位置，因此隊列長度為tail－head。 當tail值為len(S)，隊尾元素存儲在len(S)－1，因此隊列已滿。]
2.C　[隊列的變化情況為12345→34512→4512→1245→245→524→24。]
3.C　[本題考查隊列的性質。入隊3次，出隊4次，在3次入隊前tail應為6，在4次出隊前head應為3。]
4.C　[題目中隊列的元素執行隊首元素出隊，再從隊尾入隊，接下來隊首元素出隊從隊尾入隊，直至隊列空，輸出的順序為C選項結果。]
5.C　[本題考查隊列基本操作。遍歷列表s，當元素不在隊列中，將該元素入隊，否則將隊首元素出隊(該元素不入隊)。遍歷第2個第3個d時，ab出隊，隊列中有[c，d]，接著bha依次入隊。]
6.A　[本題考查隊列的相關操作。表達式(ord(i)－ord(″a″)＋q[head]) % 26 的功能是將i轉換為在字母表中索引位置，并循環后移q[head]個位置。計算出移動位置后，再轉換為小寫字母。q中元素實現出隊后再入隊，因此分別將a、b、c和x、y、z對應位置字母后稱1、2、3位置。]
7.D　[遍歷字符串s，當i%2＝＝0條件成立時，將s[i]入隊，否則將s[len(s)－i]入隊。]
8.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不可能產生。]

展開更多......

收起↑