資源簡介

(共78張PPT)
課時3　棧
第三章　字符串、隊列和棧
1.通過問題解決，理解棧的概念和特性。2.掌握棧的基本操作，并能編程實現。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.棧的概念
(1)棧也是一種操作受限的線性表，僅允許表的______進行插入或刪除操作。
(2)進行插入或刪除操作的一端稱為______，位于棧頂位置的元素稱為棧頂元素；表的另一端為______，位于棧底位置的元素稱為棧底元素。
一端
棧頂
棧底
2.棧的特性
(1)____________或____________。
(2)_______________。
棧可以是空的，也可以包含多個元素。
3.棧的基本操作
(1)棧的創建
在存儲n個元素的棧時，可以用列表創建一個長度為n的棧。
(2)入棧(push)、出棧(pop)
入棧操作：入棧也叫______操作，把數據元素壓入棧頂，每次入棧時，棧頂指針變量top值______，再給st[top]賦值。
先進后出
后進先出
有限序列性
壓棧
加1
出棧操作：出棧時把棧頂元素取出，同時__________________。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
top值減1
4.使用列表模擬棧操作
a＝[]　#建棧
a.append(″data1″)　#入棧
a.append(″data2″)　#入棧
a.append(″data3″)　#入棧
print(a.pop())　#出棧
print(a.pop())　#出棧
print(a.pop())　#出棧
5.建立stack類并進行棧操作
class Stack()：
def_ _init_ _(self)：　#建棧
self.my_stack＝[]
def push(self，data)：　#入棧
self.my_stack.append(data)
def pop(self)：　#出棧
return self.my_stack.pop()
def size(self)：　#棧空判斷
return len(self.my_stack)
def isEmpty(self)：
return self.my_stack＝＝[]
stack＝Stack()
a＝[″data1″，″data2″，″data3″]
for item in a：　#入棧
stack.push(item)
print(″棧中元素個數為：″，stack.size())
while not stack.isEmpty(): #出棧
print(stack.pop())
例題精析
2
例1 若某棧的容量是 3，即棧內最多只能容納 3 個元素，若其某個出棧序列是a，b，c，d，e，那么它可能的入棧序列是(　　)
A.c，b，a，e，d B.d，c，b，a，e
C.b，c，a，e，d D.a，e，d，c，b
A
解析　A選項c，b，a依次入棧，a，b，c依次出棧，接著e，d入棧后再出棧。B選項a要出棧，d，c，b，a需入棧，棧空間超過3。C選項b先于c入棧，則c需先出棧。D選項a入棧并出棧后，剩余4個元素入棧，超過棧容量。
變式訓練　有1個棧初始為空，其元素入棧順序依次為s，t，r，w，u，y，m，若經過進棧和出棧操作后，棧底至棧頂元素分別為t，w，y，則第3個出棧元素為(　　)
解析　根據棧的特性，在棧中元素后進先出，因此第1個入棧和出棧的元素是s，第3個入棧第2個出棧的元素是r，第5個入棧第3個出棧的元素是u。
C
A.m B.w C.u D.s
例2 公交車上有時候會出現人太多無法擠到后門下車而從前門下車的情況，因此若一個序列在有3個或以下元素時按隊列方式離開序列，但在3個以上元素時按棧方式離開序列，則對于依次進入序列的xl，x2，x3，x4，x5，x6，離開序列的順序可能為(　　)
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小于3個元素按隊列方式出列，x4進入序列時，還有x2，x3，x4共3個元素，按隊列方式出列，也就是x2出列，如果按棧離開，則必須x5進入序列，那就是x5先出。B選項x4按出棧方式離開，剩下x1，x2，x3，因此x1按隊列方式離開。當x5、x6進入序列，x6按出棧方式離開。剩下3個按隊列方式離開。C選項x1，x2，x3按隊列方式離開，則x4，x5，x6進入序列后只能按隊列方式離開。D選項x6先離開，全部元素進入序列，前面3個元素按出棧方式離開，后面3個元素只能是按隊列方式離開。
B
變式訓練　設棧S和隊列Q的初始狀態為空，元素x1、x2、x3、x4、x5、x6依次通過棧S，一個元素出棧后即進入隊列Q，若出隊的順序依次為x2、x4、x3、x6、x5、x1，則棧S的容量至少應該為(　　)
A.2 B.3 C.4 D.5
解析　本題主要考查的是棧和隊列的特點。棧的特點是先進后出，而隊列的特點是先進先出，根據出隊順序可知，出棧的順序依次為x2、x4、x3、x6、x5、x1，在x2出棧前，棧里的元素為x2和x1，共2個元素；在x4出棧前，棧里的元素為x4、x3和x1，共3個元素； 在x3出棧前，棧里的元素為x3和x1，共2個元素； x6出棧前，棧里的元素為x6、x5和x1，共3個元素； 在元素x5出棧前，棧里的元素為x5、x1，共2個元素，因此，棧的最小容量應為3。
B
例3 有如下 Python 程序段：
s＝input(″輸入一個字符串″)
st＝[″″]*6；st[0]＝s[0]
top＝0
for i in range(1，len(s))：
　if top>＝0 and s[i]＝＝st[top]：
　 top－＝1
　else：
　 top＋＝1
　st[top]＝s[i]
print(st[：top＋1])
A.ABABB B.AAABA C.BAABA D.BBABA
解析　本題考查棧的性質。棧初始值有一個元素s[0]，從索引位置1開始遍歷s，如果s[i]與棧頂元素相同，進行出棧操作，否則進行入棧操作。A、B和D選項棧中元素有ABA。C選項棧中元素只有A。
C
變式訓練　有如下 Python 程序段：
st＝[0]*10
cnt，top＝0，－1
s＝input()
for i in range(0，len(s)，2):
　t＝s[i]
　 n＝int(s[i＋1])
　 if t＝＝'A'：
　 for j in range(n):
　 　　top＋＝1
　 　　　st[top]＝cnt
　　　　cnt＋＝1
　　elif t＝＝'P'：
　while top！＝－1 and n>0:
　　　　top－＝1
　　　n－＝1
print(st[0：top＋1])
若輸入 s 的值為″A1P2A3P2A2″，則程序的輸出結果是(　　)
A.[5，6] B.[2，5，6]
C.[4，5] D.[1，4，5]
解析　對字符串s兩個一組進行遍歷，如果t為A，將n個cnt入棧，如果是p，對n個元素進行出棧。0入棧，0出棧，1、2、3入棧，3和2出棧，4、5入棧，因此從棧底到棧頂分別為1，4，5。
D
例4 有如下Python程序段：
import random
a＝['A'，'B'，'#'，'#'，'C'，'D'，'#']
stk＝[0]*len(a)；top＝－1
for i in range(len(a))：
　op＝random.randint(0，1) # 隨機生成0或1
　if op＝＝1 and a[i]！＝ '#'：
　　　top＋＝1；stk[top]＝a[i]
　　　　a[i]＝'#'
　　　elif op＝＝0 and top！＝－1 and a[i]＝＝'#'：
　 　　　a[i]＝stk[top]；top－＝1
A.['A'，'B'，'#'，'#'，'C'，'D'，'#'] B.['#'，'#'，'#'，'#'，'#'，'#'，'#']
C.['#'，'B'，'#'，'#'，'C'，'D'，'A'] D.['#'，'#'，'A'，'B'，'C'，'D'，'#']
解析　本題考查棧的應用。若op＝1，且'#'時要入棧，是字母時，if語句與elif語句都不執行。若op＝0，棧不空且a[i]值為'#'，把棧頂值代替當前元素，且進行出棧操作。A選項，當op的值每次都是0時即可實現；B選項，當op的值每次都是1時即可實現；選項C，當op的值依次是1、0、1、1、0、0、0時即可實現。選項D，a[0]、a[1]值是'#'，表明A、B均已入棧，選項不符合出棧順序。
D
變式訓練　有如下 Python 程序段：
import random
p＝″abcde*″；st＝[″″]*len(p)；s＝″″
top＝－1
i＝0
while i<＝5：
　m＝random.randint(0，1)
　 if m＝＝0：
top＋＝1
st[top]＝p[i]
i＋＝1
　elif len(st)>0:
s＋＝st[top]
top－＝1
print(s)
執行上述程序段后，輸出結果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
解析　若產生的隨機數m值為0，進行入棧操作。否則出棧后并連接到字符串s中。則于最后一個字符*一旦入棧后，i的值為5，結束循環，就不可能出棧。B選項a比b先入棧，出棧順序應相反。D選項abc先入棧，c出棧，d入棧后出棧，最后a出棧。
D
隨堂檢測
3
A.a和c B.a和b C.b和d D.c和d
B
解析　a比b先入棧，因此a在b的后面出棧。
2.用I表示入棧操作，0表示出棧操作，若元素入棧的順序為ABCDE，為了得到ADCEB的出棧順序，則由I和0表示的操作串是(　　)
A.I0III00I00 B.I0II0I00I0
C.IIII00I000 D.I0III0000
A
解析　A入棧、出棧；BCD入棧，DC出棧；E入棧，EB出棧。
3.利用棧求逆波蘭表達式(表達式由操作數和運算符組成)的方法是：從左往右掃描該表達式，遇到操作數時入 棧；遇到運算符時，把處于棧上方的兩個元素依次出棧，用運算符計算，并把計算結果壓入棧中。如此反復 操作，直至表達式掃描結束。當用該算法求逆波蘭表達式abcd－*e/＋f－的值時 (abcdef 表示不同的操作數)，所使用棧的深度至少為(　　)
A.3 B.4 C.5 D.6
B
解析　abcd依次進棧，棧深度為4，遇到“－”，進行c－d操作后，計算結果重新進棧(棧深度為3)，遇到“*”，進行b*(c－d)操作后重新進棧(深度為2)，接著“e”進棧(棧深度為3)最大深度為4。
4.有如下 Python 程序段：
C
st＝[0] * 10
a＝[4，6，1，7，2，8，6]
top＝0; st[top]＝a[0]
for i in range(1，len(a))：
　while top ！＝－1 and a[i]top－＝1
　top＋＝1
　st[top]＝a[i]
執行該程序段后，變量 top 的值為(　　)
A.－1 B.1 C.2 D.3
解析　棧中初始有一個值，從索引位置1開始遍歷，當遍歷到的數比棧頂小時，將棧頂元素出棧，自身入棧。遍歷到1時，讓4和6出棧。7入棧，2使得7出棧，8入棧，6使得8出棧，因此棧中有1、2和6共3個元素，top值為2。
5.有如下Python程序段：
a＝[2，1，5，7，3]
n＝len(a)
s1＝[－1]*n；top1＝－1
s2＝[－1]*n；top2＝－1
for i in range(n)：
　while top1！＝－1 and a[i]　 top2＋＝1；s2[top2]＝s1[top1]；top1－＝1
　top1＋＝1；s1[top1]＝a[i]
while top2！＝－1：
　top1＋＝1；s1[top1]＝s2[top2]；top2－＝1
A
A.top1＝＝5 B.top2＝＝－1
C.s1[0]＝＝1 D.s1[3]＝＝7
解析　本題考查棧的基本應用。遍歷列表a中數據，若棧s1不空，且s1棧頂元素大于等于a[i]時，不斷地將s1中元素出棧，并入棧s2中，將a[i]入棧s1。因此棧s1中元素有1，3，棧s2中有元素[2，7，5]，最后將棧s2中元素出棧并加入到棧s1中，因此棧s1中最終結果為[1，3，5，7，2]。
6.有如下程序段：
s＝list(input(″輸入一個字符串s：″)) # list 函數將s 轉換為列表
top＝－1
a＝[0]*100
i＝0
while i　if s[i]＝＝'('：
　top＋＝1
　　　a[top]＝i
　elif s[i]＝＝')'：
　 st＝a[top]
　 top－＝1
　s＝s[：st]＋s[i－1：st：－1]＋s[i＋1：]
　i－＝2
　i＋＝1
print(″.join(s)) #將s 中元素以字符連接成一個新的字符串
執行該程序段后，輸入“(ed(y(oc))p)”，輸出結果是(　　)
A.pycode B.codepy C.pcodey D.copyde
A
解析　本題考查棧的性質和基本操作。遇到'('對應的下標入棧，遇到')'，元素出棧。同時列表元素重新組合，組合原則：二端不動，最內層配對括號內的元素翻轉，同時這對括號拋棄。算法過程：
(ed(y(oc))p)→(ed(yco)p)→(edocyp)→pycode。
7.有如下 Python 程序段：
import random
q＝[″A″，″B″，″C″，″D″，″#″]
head，tail＝0，4
s＝[0]*5
top＝－1
for i in range(5):
　t＝random.randint(0，1)　　 #隨機生成 0 或 1
　if t＝＝0 and head　top＋＝1；s[top]＝q[head]
　head＋＝1
　elif t＝＝1 and top！＝－1:
　 s[top]＝0；top－＝1
B
解析　本題考查隊列和棧的基本操作。A選項t產生全0時，q中隊列元素依次出隊入棧，最后t＝0且head＝＝tail時，沒有任何操作。B選項D要出棧，ABC都入棧且出棧，執行的次數超過5次。C選項t依次產生1，1，1，1，1時q中隊列元素不出隊也不入棧。D選項t依次產生0，0，1，0，0時AB先后入棧，然后B出棧，最后CD依次入棧。
8.有如下 Python 程序段：
a＝[1，2，3，4，5] ; b＝[3，2，5，1，4]
stack＝[] ; i＝j＝0
while i　stack.append(a[i]) #將 a[i]添加到 stack 末尾
　i＋＝1
　while len(stack)>0 and stack[－1]＝＝b[j]:
　stack.pop() #移除 stack 末尾元素
　j＋＝1
C
執行該程序段后，stack 中的元素個數為(　　)
A.0 B.1 C.2 D.3
解析　stack是一個棧，b是一個隊列。遍歷數組a，將a[i]進行入棧操作，當棧不為空，且棧頂元素與隊首元素相等，不斷地將數據進行出棧和出隊操作。1，2，3入棧，3，2出棧出隊，4，5入棧，5出棧出隊，棧中元素有1和4。
4
鞏固與提升
基礎鞏固
能力提升
1.棧s的最大長度為4，初始已有兩個元素在棧內，棧底為a，棧頂為b，經過一系列入棧、出棧操作，若元素入棧的順序是c，d，e，f，則可能的出棧序列為(　　)
A.c，a，b，e，f，d B.b，d，f，e，c，a
C.a，b，d，c，e，f D.b，e，f，c，d，a
B
解析　A選項和C選項都出現了 a 在 b 前面出棧的情況，因此選項錯誤；D選項f 出棧時棧內的元素為(棧底)c，d(棧頂)，因此不可能 c 出棧，選項錯誤。
2.有一個隊列和一個棧，其中隊列中隊首到隊尾的元素依次為3，15，8，7，棧中棧頂到棧底的元素依次為6，9，12，10。現在有兩種操作，操作S是指隊列中1個元素出隊后入棧，操作Q是棧中1個元素出棧后入隊。則經過QSSQSQQS操作后，隊列中隊首到隊尾的元素依次是(　　)
A.6，15，8，3 B.10，15，8，3
C.3，6，15，7 D.3，10，15，7
A
解析　隊列特征為先進先出，有4次出隊，因此隊列中3，15，8，7全部出隊。Q出棧入隊，因此6先入隊，15和3在棧中，接著15入隊，8出隊入棧，因此后面是8和3。
3.用“除二取余”法將十進制轉換為二進制數，用棧的方法操作，需要把得到的余數依次入棧，除盡后再把余數出棧即可。若要將十進制數n(0≤n<64)轉換為二進制數，則設置棧的長度至少為(　　)
A.3 B.4 C.5 D.6
D
解析　十進制數n(0≤n＜64)轉換為二進制數，得到最大的是6位二進制數。
4.已知棧k的入棧順序為2，7，3，1，6，9，第2個出棧的是6，第5個出棧的是2，則最后出棧的元素是(　　)
A.7 B.3 C.1 D.9
D
解析　2是第1個入棧，當2出棧時，棧為空，只有9入棧再出棧。
5.已知字符“a”的ASCII碼值為97，有如下Python程序段：
que＝[″″]*20
head，tail＝0，0
for i in range(3)：
　que[tail]＝chr(97＋i)
　 tail＋＝1
st＝[″b″，″c″，″d″，″a″]
top＝3
while head－1:
　if st[top]＝＝que[head]：
head＋＝1
A
　else：
que[tail]＝st[top]
tail＋＝1
　top－＝1
print(que[head：tail])
執行該程序段，則輸出的結果是(　　)
A.['c'，'d'，'c'] B.['c'，'c'，'d']
C.['c'，″，'d'] D.['c'，'d']
解析　第1個循環讓abc依次入隊。當隊列和棧不為空時，如果棧頂元素和隊首元素相同，則進行出隊和出棧操作，否則將棧頂元素出棧并入隊。棧頂和隊首均為″a″，出隊和出棧操作，接著″d″入隊，″d″出棧，接著″c″入隊，″c″出棧，隊列中元素為″bcdc″，接著″b″出隊和出棧。
6.用棧的思想編寫進制轉換中的“除二取余法”的Python程序如下：
st＝[－1]*100
top＝－1
n＝int(input(″請輸入一個十進制數″))
while n>0：
n∥＝2
while top！＝－1：
　　print(st[top]，end＝″″)
　　top－＝1
D
方框處的代碼由以下三條語句組成：①st[top]＝x　②x＝n%2　③top＋＝1下列語句順序正確的是(　　)
A.①②③ B.①③② C.②①③ D.②③①
解析　入棧必先移動top指針，入棧元素為x，先對x進行除2的余數賦值。
7.有如下Python程序段：
s＝input(″請輸入一個僅由小寫英文字母組成的字符串：″)
st＝[″″]*len(s)
top＝－1
t＝[－1]*26
for i in range(len(s)):
　id＝ord(s[i])－97
　 if t[id]＝＝－1：
　top＋＝1
　st[top]＝s[i]
　t[id]＝top
　else：
　 first＝t[id]
　while top>＝first and top！＝－1:
　　num＝ord(st[top])－97
　　t[num]＝－1; top－＝1
print(st[：top＋1])
若從鍵盤輸入的值為″hellopython″，則輸出的值為(　　)
A.['o'，'n'] B.['h'，'e'，'n']
C.['h'，'e'，'l'，'o'，'p'，'y'，'t'，'n'] D.['h'，'e'，'o'，'p'，'y'，'t'，'h'，'o'，'n']
A
解析　遍歷字符串s，將每個字母轉換成0～25之間對應的數字。t列表是每個字母出現在棧中位置的桶。若字母不在棧中，將該字母入棧，同時記錄該字母為當前棧頂位置。若該字母已經存在于棧中，將后入棧的字母進行出棧操作，并在桶中作－1的標記。最后一個h讓前面所有字母出棧，因此棧中只有o和n。
8.有如下Python程序段：
import random
s＝[3，2，7，6，9]
st＝[0]*len(s)
top＝－1；i＝0
while i　op＝random.randint(0，1)
　if top＝＝－1 or op＝＝0 and s[i]>st[top]：
　top＋＝1
　st[top]＝s[i]
B
　elif top>＝1 and op＝＝1 and s[i]>st[top－1]：
　st[top]＝s[i]
　i＋＝1
while top！＝－1：
　　　print(st[top]，end＝″ ″)
　　　top－＝1
解析　本題考查棧的應用。當棧空入棧，因此3肯定在棧中。當op為0且s[i]>st[top]時，s[i]入棧，若產生op的值一直為1，則棧中只有3；入棧的元素比棧中元素大，2小于3，因此2不可能入棧，若7沒有入棧，則6可能入棧。
9.如下Python 程序段的功能是判斷一個表達式中的括號(只有小括號)是否匹配，
exp＝input(″請輸入表達式：″)
top＝－1；n＝len(exp)∥2；flag＝True
stack＝[″″]*n
for ch in exp:
　if ch＝＝″(″：
　 if ①____________：
　　　flag＝False；break
top＋＝1；stack[top]＝″(″
　　elif ch＝＝″)″：
　
if top<0：
　　　　flag＝False；break
top－＝1
if ②____________：
　print(″括號匹配″)
else：
　　print(″括號不匹配″)
則劃線處應填入的代碼是(　　)
A.① top>＝n ② flag and top＝＝0
B.① top＝＝n－1 ② flag and top＝＝0
C.① top>＝n ② flag and top＝＝－1
D.① top＝＝n－1 ② flag and top＝＝－1
D
解析　本題考查棧的基本操作。n值為len(exp)∥2，如果是″(″，進行入棧操作，如果棧頂指針為n，若再入棧，則左括號超出總字符串長度的一半，說明左括號的數量大于右括號。否則進行出棧操作，一個右括號匹配一個左括號，若在出棧前，棧為空，說明左括號少了。遍歷完后，用右括號對左括號進行出棧操作，如果棧為空，說明兩者數量相等。
10.某棧入棧序列為“A、B、C、D、E”，若第一個出棧的元素為“C”，最后一個出棧的元素為“E”，則可能的出棧序列有(　　)
A.3種 B.4種 C.5種 D.6種
A
解析　C要出棧，棧中有A和B，E最后一個出棧，因此E最后入棧并馬上出棧，那么D可能在A前面，AB之間和B之后三個位置出棧。
11.有如下 Python 程序：
s1＝[0]*5; s2＝[0]*5; top1＝－1；top2＝－1
a＝[9，2，5，6，1]
for i in range (len(a))：
　while top1！＝－1 and a[i]　 top2＋＝1
　s2[top2]＝s1[top1]
　top1－＝1
　top1＋＝1; s1[top1]＝a[i]
　while top2！＝1：
D
　top1＋＝1
　s1[top1]＝s2[top2]
　top2－＝1
print (s1[top1])
執行程序后的輸出結果是(　　)
A.1 B.5 C.6 D.9
解析　本題考查棧的相關知識。若 a[i]12.有如下 Python 程序段：
import random
lst＝['A'，'B'，'C'，'D']
st＝[0] * len(lst)
i，top＝0，－1
while i　k＝random.randint(0，1)
　 if k＝＝0：
　 top＋＝1
　st[top]＝lst[i]
　i＋＝1
　　elif top！＝－1：
　lst[i]＝st[top]
　top－＝1
B
A.['A'，'B'，'C'，'D'] B.['A'，'B'，'A'，'C']
C.['A'，'A'，'C'，'D'] D.['A'，'A'，'C'，'A']
解析　當k的值為0時，進行入棧操作；當k的值為1且棧不為空，進行出棧并替換lst[i]操作。由于i＋＝1操作發生在入棧過程中，因此必須要有4個元素出棧，但棧中可能有元素未出棧。A選項當隨機數4次均為0，全部元素均在棧中。C選項隨機數依次為0，1，0，0，有兩個元素在棧中。D選項隨機數依次為0，1，0，1，A先入棧，出棧后替換B，原B位置上的A再次入棧，最后替換D。B選項當i的值為2時，AB在棧中，應該B先出棧。
13.有如下 Python 程序段：
a＝{'<'：0，'('：1，'['：2，'{'：3，'>'：4，')'：5，']'：6，
'}'：7}
s1＝input()
s＝[8，0，0，0，0，0，0，0，0]
top＝0；flag＝True
for x in s1：
　 k＝a[x]
　if k<4：
if s[top]　　 flag＝False
　　　break
top＋＝1
s[top]＝k
else：
if s[top]！＝k－4:
　　　flag＝False
　　　break
top－＝1
if flag and top＝＝0:
　print(″YES″)
else：
　　　print(″NO″)
若輸出結果為“NO”，則 s1 輸入的值是(　　)
A.{}[]()<> B.[()]{<>} C.{[<()>]} D.{()[<>]}
C
解析　本題考查棧的操作。遍歷字符串s1并取出在字典中的值k，如果是符號的左半部分，并且棧頂元素大于等于k，將k值入棧。若k大于等于4，且棧頂元素等于k－4，出棧一個元素。當flag為True且棧中只剩下一個元素，輸出YES，否則輸出NO。A選項{在字典中鍵值為3，入棧，}在字典中鍵值為7，滿足條件棧頂元素等于k－4，讓棧頂元素出棧，其他符號均成對，相同方法處理。B選項[和(對應的鍵值分別為2和1，2入棧后，1小于棧頂2，1也入棧，接著)和]讓1和2依次出棧。{鍵值大于<鍵值，相同方法處理。C選項<和(對應的鍵值分別為0和1，當遍歷到(時s[top]14.有如下Python程序段：
import random
s＝″Happy″
stk＝[″″]*len(s)；top＝－1
i＝0；res＝″″
while i　 if random.randint(0，1)＝＝0 or top＝＝－1：
　top＋＝1；stk[top]＝s[i]
　elif s[i]>stk[top]：
　res＋＝stk[top]；top－＝1
　i－＝1
　i＋＝1
while top>＝0：
　res＋＝stk[top]；top－＝1
print(res)
A
解析　分為產生隨機數為0、隨機數為1且s[i]>stk[top]和隨機數為1且s[i]<＝stk[top]三種情況，在第2種情況中，讓較小的元素先出棧，同時i減1。第3種情況既不入棧，也不出棧，因此s中可能有部分元素未入棧。B選項H入棧，a讓H先出棧，a入棧，p讓a入棧，p和p均入棧，y分兩種讓兩個p出棧，最后在while結構中y出棧。C選項產生的隨機數均為0。D選項a讓H出棧，a入棧，隨機數為0，p入棧，第2個p隨機數為1，不入棧。y讓p和a出棧。A選項a不可能讓p出棧。
15.判斷某序列b是否是入棧序列a＝[1，2，3，4，5]的出棧序列，程序如下：
a＝[1，2，3，4，5]
b＝list(map(int，input().split()))
stack＝[]
i＝j＝0
while i　 stack.append(①____________)
　 i＋＝1
　 while len(stack)>0 and ②____________：
　stack.pop()
　j＋＝1
if len(stack)＝＝0 and j＝＝len(a):
　print(b，'是'，a，'的出棧序列')
else：
　　print(b，'不是'，a，'的出棧序列')
劃線處應填寫的語句是(　　)
A.①a[i]　②stack[－1]＝＝a[j]
B.①a[i]　②stack[－1]＝＝b[j]
C.①b[i]　②stack[－1]＝＝b[i]
D.①b[i]　②stack[－1]＝＝a[j]
B
解析　本題考查棧的操作與程序實現。由第6行的添加操作和第9行的刪除操作可以判斷stack用于存儲棧元素。可以通過將a元素不斷入棧，看能否形成和b一樣的出棧序列。第①空應該讓a中的元素入棧，填寫a[i]。而出棧時，需要判定棧頂元素是否和b序列中當前元素是否一致，一致才能出棧，盡可能形成與b一樣的序列。
16.自從學習了不同進制之后，小明設計了一個計算不同進制數的加法器，并用Python編程實現。輸入一個加法算式，加數可以是十進制數、二進制數或者十六進制數，程序的功能是輸出它們的和。例如輸入形如“1010B＋1DH＋109D＝”的加法算式后，執行程序輸出“和是148”的結果。Python程序如下：
s＝input('輸入一個混合進制的加法算式：')
dic＝{'B'：2，'D'：10，'H'：16}
st＝[″]*100
top，i，x，m＝－1，0，0，0
while i　　　if s[i]＝＝'＋' or s[i]＝＝'＝'：
　　　 m＝①____________
　　　top＝top－1
　　　t＝0
　　　while top！＝－1：
　　　if st[top]>＝'A' and st[top]<＝'F'：
　　　　　　　st[top]＝ord(st[top])－ord('A')＋10
　　　else：
　　　　　　st[top]＝int(st[top])
　　　②____________
　　　t＝t＋1
　　　top＝top－1
　else：
　　　③____________
　　　st[top]＝s[i]
　i＝i＋1
print('和是'，x)
(1)將劃線處代碼補充完整。
(2)若輸入”101B＋DH＋100D”，輸出的結果是________。
答案　(1)①dic[st[top]]　 ②x＝x＋st[top]*m**t　 ③ top＝top＋1　(2)118
解析　程序可知st列表中保存著當前加數的每一位。如對于式子“1010B＋1DH＋109D＝”，當讀到第一個加號時，st列表的值為[‘1’，‘0’，’1’，’0’，’B’]，讀到第二加號時，st的值是[‘1’，‘D’，‘H’]，讀到最后’＝’號時，st的值是[‘1’，‘0’，‘9’，‘D’]。①st列表的最后一位是進制編號，讀取st最后一位，通過字典dic得到進制值。②使用權值法把st列表中保存的進制數轉化為十進制數。③讀取到加數的每一位數字，都保存在st列表中的相應位置。(2)由于式子中的最后一位不是’＋’或者’＝’， 所以st列表中的最后一個數字沒有加上。
17.某種密碼設計方法如下：給定兩個數組，數組元素由數字 1～9 組成，從中選出 k(k 小于等于兩個數組長度之和)個數字拼接成一個新的數，同一數組中取出的數字保持其在原數組中的相對順序，每個數組中至少有 1 個數被選中，滿足該條件的最大數即為密碼，程序運行界面如圖所示。
請輸入數組1：3　4　6　5　7　8
請輸入數組2：9　1　2　5　8　3　4
請輸入k：6
密碼為：987834
請回答下列問題：
(1)程序部分代碼如下，請在劃線處填入正確的代碼。
def select_num(nums，k):
　stack＝[0]*len(nums)；top＝－1；cnt＝len(nums)－k
　for num in nums:
　 while cnt>0 and top！＝－1 and stack[top]　　　top－＝1；cnt－＝1
　top＋＝1
　①____________
　while cnt>0：
num1＝input(″請輸入數組 1：″)
num2＝input(″請輸入數組 2：″)
num1＝list(map(int，num1.split(″ ″)))
num2＝list(map(int，num2.split(″ ″)))
k＝int(input(″請輸入 k：″))
②____________
for i in range(1，k):
　a＝select_num(num1，i)
　③____________
　c＝merge(a，b)
　if c>m：
m＝c
print(″密碼為：″＋str(m))
(2)加框處的程序代碼有誤，請改正。
答案　(1)①stack[top]＝num　②m＝0
③b＝select_num(num2，k－i)
(2)i解析　本題考查棧和數據的歸并。(1)①函數select_num的功能是在數字串nums取出的數字位置不變的k個長度子串。cnt初值為len(nums)－k，即需要去除的數字個數，遍歷數字串nums并將數字入棧，若當前的數字比棧頂數字大，則需將棧中數字出棧，讓棧中形成一個遞減的系列，每出棧一個cnt減1，當cnt值為0時，則不再出棧。②對m賦初值0。③主程序外循環i的值從1循環到k，采用枚舉的思想，分別從一個數組num1中選出1到k－1個數字，則從另一個數組2中選出k－1到1個數字，所以第③空應填入b＝select_num(num2，k－i)。(2)自定義函數merge(a，b)用于將a、b兩個數組的值合并按順序合并成最大數，變量 i、j分別指向ab兩個數組中待合并區間的初始位置，根據if j＝＝len(b) or i＝b[j]可知當只剩下a列表中的數據未處理或者a數組的值大于b數組的值則c＋＝a[i]，否則當 i＝＝len(a) or j課時目標
1.通過問題解決，理解棧的概念和特性。2.掌握棧的基本操作，并能編程實現。
1.棧的概念
(1)棧也是一種操作受限的線性表，僅允許表的________進行插入或刪除操作。
(2)進行插入或刪除操作的一端稱為________，位于棧頂位置的元素稱為棧頂元素；表的另一端為______，位于棧底位置的元素稱為棧底元素。
2.棧的特性
(1)____________或____________。
(2)____________。
棧可以是空的，也可以包含多個元素。
3.棧的基本操作
(1)棧的創建
在存儲n個元素的棧時，可以用列表創建一個長度為n的棧。
(2)入棧(push)、出棧(pop)
入棧操作：入棧也叫________操作，把數據元素壓入棧頂，每次入棧時，棧頂指針變量top值________，再給st[top]賦值。
出棧操作：出棧時把棧頂元素取出，同時____________。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
4.使用列表模擬棧操作
a＝[]　#建棧
a.append(″data1″)　#入棧
a.append(″data2″)　#入棧
a.append(″data3″)　#入棧
print(a.pop())　#出棧
print(a.pop())　#出棧
print(a.pop())　#出棧
5.建立stack類并進行棧操作
class Stack()：
def_ _init_ _(self)：　#建棧
self.my_stack＝[]
def push(self，data)：　#入棧
self.my_stack.append(data)
def pop(self)：　#出棧
return self.my_stack.pop()
def size(self)：　#棧空判斷
return len(self.my_stack)
def isEmpty(self)：
return self.my_stack＝＝[]
stack＝Stack()
a＝[″data1″，″data2″，″data3″]
for item in a：　#入棧
stack.push(item)
print(″棧中元素個數為：″，stack.size())
while not stack.isEmpty(): #出棧
print(stack.pop())
例1 若某棧的容量是 3，即棧內最多只能容納 3 個元素，若其某個出棧序列是a，b，c，d，e，那么它可能的入棧序列是(　　)
A.c，b，a，e，d B.d，c，b，a，e
C.b，c，a，e，d D.a，e，d，c，b
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有1個棧初始為空，其元素入棧順序依次為s，t，r，w，u，y，m，若經過進棧和出棧操作后，棧底至棧頂元素分別為t，w，y，則第3個出棧元素為(　　)
A.m B.w C.u D.s
例2 公交車上有時候會出現人太多無法擠到后門下車而從前門下車的情況，因此若一個序列在有3個或以下元素時按隊列方式離開序列，但在3個以上元素時按棧方式離開序列，則對于依次進入序列的xl，x2，x3，x4，x5，x6，離開序列的順序可能為(　　)
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
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　設棧S和隊列Q的初始狀態為空，元素x1、x2、x3、x4、x5、x6依次通過棧S，一個元素出棧后即進入隊列Q，若出隊的順序依次為x2、x4、x3、x6、x5、x1，則棧S的容量至少應該為(　　)
A.2 B.3 C.4 D.5
例3 有如下 Python 程序段：
s＝input(″輸入一個字符串″)
st＝[″″]*6；st[0]＝s[0]
top＝0
for i in range(1，len(s))：
　if top>＝0 and s[i]＝＝st[top]：
　 top－＝1
　else：
　 top＋＝1
　st[top]＝s[i]
print(st[：top＋1])
運行程序段，輸入以下字符串，運行后的值與其它三項不同的是(　　)
A.ABABB B.AAABA C.BAABA D.BBABA
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下 Python 程序段：
st＝[0]*10
cnt，top＝0，－1
s＝input()
for i in range(0，len(s)，2):
　t＝s[i]
　 n＝int(s[i＋1])
　 if t＝＝'A'：
　 for j in range(n):
　 　　top＋＝1
　 　　　st[top]＝cnt
　　　　cnt＋＝1
　　elif t＝＝'P'：
　while top！＝－1 and n>0:
　　　　top－＝1
　　　n－＝1
print(st[0：top＋1])
若輸入 s 的值為″A1P2A3P2A2″，則程序的輸出結果是(　　)
A.[5，6] B.[2，5，6]
C.[4，5] D.[1，4，5]
例4 有如下Python程序段：
import random
a＝['A'，'B'，'#'，'#'，'C'，'D'，'#']
stk＝[0]*len(a)；top＝－1
for i in range(len(a))：
　op＝random.randint(0，1) # 隨機生成0或1
　if op＝＝1 and a[i]！＝ '#'：
　　　top＋＝1；stk[top]＝a[i]
　　　　a[i]＝'#'
　　　elif op＝＝0 and top！＝－1 and a[i]＝＝'#'：
　 　　　a[i]＝stk[top]；top－＝1
執行該程序段后，a的值不可能的是(　　)
A.['A'，'B'，'#'，'#'，'C'，'D'，'#']
B.['#'，'#'，'#'，'#'，'#'，'#'，'#']
C.['#'，'B'，'#'，'#'，'C'，'D'，'A']
D.['#'，'#'，'A'，'B'，'C'，'D'，'#']
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下 Python 程序段：
import random
p＝″abcde*″；st＝[″″]*len(p)；s＝″″
top＝－1
i＝0
while i<＝5：
　m＝random.randint(0，1)
　 if m＝＝0：
top＋＝1
st[top]＝p[i]
i＋＝1
　elif len(st)>0:
s＋＝st[top]
top－＝1
print(s)
執行上述程序段后，輸出結果可能的是(　　)
A.a* B.cdabe C.abcde* D.cdba
1.若已知元素的入棧順序是a, b, c, d，其出棧序列為Q1, Q2, Q3, Q4，則Q2, Q4不可能是(　　)
A.a和c B.a和b C.b和d D.c和d
2.用I表示入棧操作，0表示出棧操作，若元素入棧的順序為ABCDE，為了得到ADCEB的出棧順序，則由I和0表示的操作串是(　　)
A.I0III00I00 B.I0II0I00I0 C.IIII00I000 D.I0III0000
3.利用棧求逆波蘭表達式(表達式由操作數和運算符組成)的方法是：從左往右掃描該表達式，遇到操作數時入 棧；遇到運算符時，把處于棧上方的兩個元素依次出棧，用運算符計算，并把計算結果壓入棧中。如此反復 操作，直至表達式掃描結束。當用該算法求逆波蘭表達式abcd－*e/＋f－的值時 (abcdef 表示不同的操作數)，所使用棧的深度至少為(　　)
A.3 B.4 C.5 D.6
4.有如下 Python 程序段：
st＝[0] * 10
a＝[4，6，1，7，2，8，6]
top＝0; st[top]＝a[0]
for i in range(1，len(a))：
　while top ！＝－1 and a[i]top－＝1
　top＋＝1
　st[top]＝a[i]
執行該程序段后，變量 top 的值為(　　)
A.－1 B.1 C.2 D.3
5.有如下Python程序段：
a＝[2，1，5，7，3]
n＝len(a)
s1＝[－1]*n；top1＝－1
s2＝[－1]*n；top2＝－1
for i in range(n)：
　while top1！＝－1 and a[i]　 top2＋＝1；s2[top2]＝s1[top1]；top1－＝1
　top1＋＝1；s1[top1]＝a[i]
while top2！＝－1：
　top1＋＝1；s1[top1]＝s2[top2]；top2－＝1
運行該程序段后，下列表達式不成立的是 (　　)
A.top1＝＝5 B.top2＝＝－1
C.s1[0]＝＝1 D.s1[3]＝＝7
6.有如下程序段：
s＝list(input(″輸入一個字符串s：″)) # list 函數將s 轉換為列表
top＝－1
a＝[0]*100
i＝0
while i　if s[i]＝＝'('：
　top＋＝1
　　　a[top]＝i
　elif s[i]＝＝')'：
　 st＝a[top]
　 top－＝1
　s＝s[：st]＋s[i－1：st：－1]＋s[i＋1：]
　i－＝2
　i＋＝1
print(″.join(s)) #將s 中元素以字符連接成一個新的字符串
執行該程序段后，輸入“(ed(y(oc))p)”，輸出結果是(　　)
A.pycode B.codepy C.pcodey D.copyde
7.有如下 Python 程序段：
import random
q＝[″A″，″B″，″C″，″D″，″#″]
head，tail＝0，4
s＝[0]*5
top＝－1
for i in range(5):
　t＝random.randint(0，1)　　 #隨機生成 0 或 1
　if t＝＝0 and head　top＋＝1；s[top]＝q[head]
　head＋＝1
　elif t＝＝1 and top！＝－1:
　 s[top]＝0；top－＝1
執行該程序后，s 的值不可能的是(　　)
A.['A'，'B'，'C'，'D'，0] 　　 B.['D'，0，0，0，0]
C.[0，0，0，0，0] 　 　D.['A'，'C'，'D'，0，0]
8.有如下 Python 程序段：
a＝[1，2，3，4，5] ; b＝[3，2，5，1，4]
stack＝[] ; i＝j＝0
while i　stack.append(a[i]) #將 a[i]添加到 stack 末尾
　i＋＝1
　while len(stack)>0 and stack[－1]＝＝b[j]:
　stack.pop() #移除 stack 末尾元素
　j＋＝1
執行該程序段后，stack 中的元素個數為(　　)
A.0 B.1 C.2 D.3
課時3　棧
知識梳理
1.(1)一端　(2)棧頂　棧底
2.(1)先進后出　后進先出　(2)有限序列性
3.(2)壓棧　加1　top值減1
例題精析
例1　A　[A選項c，b，a依次入棧，a，b，c依次出棧，接著e，d入棧后再出棧。B選項a要出棧，d，c，b，a需入棧，棧空間超過3。C選項b先于c入棧，則c需先出棧。D選項a入棧并出棧后，剩余4個元素入棧，超過棧容量。]
變式訓練　C　[根據棧的特性，在棧中元素后進先出，因此第1個入棧和出棧的元素是s，第3個入棧第2個出棧的元素是r，第5個入棧第3個出棧的元素是u。]
例2　B　[A選項x1小于3個元素按隊列方式出列，x4進入序列時，還有x2，x3，x4共3個元素，按隊列方式出列，也就是x2出列，如果按棧離開，則必須x5進入序列，那就是x5先出。B選項x4按出棧方式離開，剩下x1，x2，x3，因此x1按隊列方式離開。當x5、x6進入序列，x6按出棧方式離開。剩下3個按隊列方式離開。C選項x1，x2，x3按隊列方式離開，則x4，x5，x6進入序列后只能按隊列方式離開。D選項x6先離開，全部元素進入序列，前面3個元素按出棧方式離開，后面3個元素只能是按隊列方式離開。]
變式訓練　B　[本題主要考查的是棧和隊列的特點。棧的特點是先進后出，而隊列的特點是先進先出，根據出隊順序可知，出棧的順序依次為x2、x4、x3、x6、x5、x1，在x2出棧前，棧里的元素為x2和x1，共2個元素；在x4出棧前，棧里的元素為x4、x3和x1，共3個元素； 在x3出棧前，棧里的元素為x3和x1，共2個元素； x6出棧前，棧里的元素為x6、x5和x1，共3個元素； 在元素x5出棧前，棧里的元素為x5、x1，共2個元素，因此，棧的最小容量應為3。]
例3　C　[本題考查棧的性質。棧初始值有一個元素s[0]，從索引位置1開始遍歷s，如果s[i]與棧頂元素相同，進行出棧操作，否則進行入棧操作。A、B和D選項棧中元素有ABA。C選項棧中元素只有A。]
變式訓練　D　[對字符串s兩個一組進行遍歷，如果t為A，將n個cnt入棧，如果是p，對n個元素進行出棧。0入棧，0出棧，1、2、3入棧，3和2出棧，4、5入棧，因此從棧底到棧頂分別為1，4，5。]
例4　D　[本題考查棧的應用。若op＝1，且'#'時要入棧，是字母時，if語句與elif語句都不執行。若op＝0，棧不空且a[i]值為'#'，把棧頂值代替當前元素，且進行出棧操作。A選項，當op的值每次都是0時即可實現；B選項，當op的值每次都是1時即可實現；選項C，當op的值依次是1、0、1、1、0、0、0時即可實現。選項D，a[0]、a[1]值是'#'，表明A、B均已入棧，選項不符合出棧順序。]
變式訓練　D　[若產生的隨機數m值為0，進行入棧操作。否則出棧后并連接到字符串s中。則于最后一個字符*一旦入棧后，i的值為5，結束循環，就不可能出棧。B選項a比b先入棧，出棧順序應相反。D選項abc先入棧，c出棧，d入棧后出棧，最后a出棧。]
隨堂檢測
1.B　[a比b先入棧，因此a在b的后面出棧。]
2.A　[A入棧、出棧；BCD入棧，DC出棧；E入棧，EB出棧。]
3.B　[abcd依次進棧，棧深度為4，遇到“－”，進行c－d操作后，計算結果重新進棧(棧深度為3)，遇到“*”，進行b*(c－d)操作后重新進棧(深度為2)，接著“e”進棧(棧深度為3)最大深度為4。]
4.C　[棧中初始有一個值，從索引位置1開始遍歷，當遍歷到的數比棧頂小時，將棧頂元素出棧，自身入棧。遍歷到1時，讓4和6出棧。7入棧，2使得7出棧，8入棧，6使得8出棧，因此棧中有1、2和6共3個元素，top值為2。]
5.A　[本題考查棧的基本應用。遍歷列表a中數據，若棧s1不空，且s1棧頂元素大于等于a[i]時，不斷地將s1中元素出棧，并入棧s2中，將a[i]入棧s1。因此棧s1中元素有1，3，棧s2中有元素[2，7，5]，最后將棧s2中元素出棧并加入到棧s1中，因此棧s1中最終結果為[1，3，5，7，2]。]
6.A　[本題考查棧的性質和基本操作。遇到'('對應的下標入棧，遇到')'，元素出棧。同時列表元素重新組合，組合原則：二端不動，最內層配對括號內的元素翻轉，同時這對括號拋棄。算法過程：(ed(y(oc))p)→(ed(yco)p)→(edocyp)→pycode。]
7.B　[本題考查隊列和棧的基本操作。A選項t產生全0時，q中隊列元素依次出隊入棧，最后t＝0且head＝＝tail時，沒有任何操作。B選項D要出棧，ABC都入棧且出棧，執行的次數超過5次。C選項t依次產生1，1，1，1，1時q中隊列元素不出隊也不入棧。D選項t依次產生0，0，1，0，0時AB先后入棧，然后B出棧，最后CD依次入棧。]
8.C　[stack是一個棧，b是一個隊列。遍歷數組a，將a[i]進行入棧操作，當棧不為空，且棧頂元素與隊首元素相等，不斷地將數據進行出棧和出隊操作。1，2，3入棧，3，2出棧出隊，4，5入棧，5出棧出隊，棧中元素有1和4。]

展開更多......

收起↑