資源簡介

專題14　棧
學業要求 知　識　點 學業水平等級
1.能結合生活中的實例，掌握棧的概念、存儲結構及特性 3
2.能結合棧的應用案例，理解棧的入棧和出棧的過程 4
知識點一　棧的性質
【知識梳理】
1.同隊列一樣，棧也是一種操作受限的線性表，僅允許在表的一端進行________或________。
2.進行插入或刪除操作的一端稱為________，位于棧頂位置的元素稱為棧頂元素；相應地，將表的另一端稱為棧底，位于棧底位置的元素為棧底元素。
3.棧具備“________________”的特點。
【經典案例】
棧(stack)又名堆棧，它是一種操作受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
【例1】 棧s的最大長度為3，初始為空，經過一系列入棧、出棧操作，若元素入棧的順序是a，b，c，d，e，f，則可能的出棧序列為(　　)
A.f，e，d，c，b，a B.c，b，a，f，e，d
C.c，a，b，d，e，f D.c，e，d，b，a，f
思維點撥
明考向 本題考查棧的基本性質
精點撥 A f要出棧，則必須有6個元素在棧中，而棧的最大長度為3
B c要出棧，則abc均在棧中，接著b和a出棧，棧空。f要出棧，則def均在棧中，接著e和b出棧
C a比b先入棧，則a應在b的后面出棧
D c出棧后，棧中有元素a和b，接著d和e入棧，棧的長度大于3
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 假設棧S的最大長度為3，其初始狀態和終止狀態均為空，經過一系列入棧和出棧的操作，若元素最后的出棧序列為F，E，D，C，B，A，則可能的入棧順序為(　　)
A.ABCDEF B.ACDFEB
C.BEFACD D.BFDECA
【例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
思維點撥
精點撥 隊列特征為先進先出，有4次出隊，因此隊列中3，15，8，7全部出隊。Q出棧入隊，因此6先入隊，15和3在棧中，接著15入隊，8出隊入棧，因此后面是8和3
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 棧q初始有三個值，經過一系列入棧，出棧操作后，棧為空，若元素出棧的順序是1，2，3，4，5，6，7，則棧q初始的情況可能是(　　)
A.[1，2，3] B.[7，5，6]
C.[6，3，1] D.[4，7，2]
知識點二　棧的算法實現
【知識梳理】
1.建立一個空棧st時，需先給分配空間，設置棧頂指針top，相應的語句分別為st＝[0]*n；________。
2.判斷棧st是否空的標志是________。
3.棧st中元素個數為________。
4.入棧也叫壓棧操作，把數據元素壓入棧頂。與隊列(tail指向隊尾下一個元素的位置)不同，棧頂指針指向棧頂元素，每次入棧時，棧頂指針變量top值________，再給st[top]賦值。
5.出棧時把棧頂元素取出，同時棧頂指針變量top值________。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
【經典案例】
棧主要用于計算過程中保存的臨時數據，是一種只能在數組一端進行存取的數據結構，最大特點是數據在存取時，無需查詢，時間復雜度為O(1)，后存的數據先被取出。入棧也叫壓棧操作，把數據元素壓入棧頂。與隊列(tail指向隊尾下一個元素的位置)不同，棧頂指針指向棧頂元素，每次入棧時，棧頂指針變量top值加1，再給st[top]賦值。出棧時把棧頂元素取出，同時棧頂指針變量top值減1。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
【例1】 有如下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'，'#']
思維點撥
明考向 本題考查棧的應用。若op＝1，且a[i]！＝'#'時要入棧，是字母時，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均已入棧，選項不符合出棧順序
聽課筆記：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 有如下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.{()[<>]}
【例2】 中綴表達式變為后綴表達式：
首先需要分配2個棧，一個作為臨時存儲運算符的棧st1(含左右小括號)，一個作為存放結果(逆波蘭式)的棧st2。對中綴表達式中各個字符進行遍歷，算法描述如下：
1)如果是操作符，且不是“)”符號，按秩序入st1棧；否則將st1棧元素出棧，并入st2棧，直到“(”為止；
2)如果是數字，按秩序入st2棧；接著要判斷st1棧中棧頂元素的情況：
如果st1棧元素個數大于等于2且棧頂元素操作符的優先級高于棧頂元素下方的元素，則st1棧元素出棧，并入st2棧；
3)將st1棧剩余元素出棧，并入st2棧。
程序運行的結果如圖所示：
中綴表達式：6＋(8－2*2/4)*3*2/3 后綴表達式：6822*4/－3*2*3/＋
(1)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
(2)程序中加框處代碼有錯，請改正。
s＝″6＋(8－2*2/4)*3*2/3″
st1＝[″″]*len(s)
st2＝[″″]*len(s)
print(″中綴表達式：″，s)
top1＝－1
top2＝－1
zd＝{″＋″：1，″－″：1，″*″：2，″/″：2，″(″：3，″)″：3}
for i in s：
if ①________：
top2＋＝1
st2[top2]＝i
if top1>0 and st1[top1]！＝″(″ and
②________：
　　 　　top2＋＝1
　　 　　st2[top2]＝st1[top1]
　　 　　top1－＝1
elif ：
　 top1＋＝1
　 st1[top1]＝i
else：
while st1[top1]！＝″(″：
　　　 　top2＋＝1
　　　 　st2[top2]＝st1[top1]
　　 　　top1－＝1
③________
while top1>＝0：
top2＋＝1
st2[top2]＝st1[top1]
top1－＝1
s1＝″″
while top2>＝0：
s1＝st2[top2]＋s1
top2－＝1
print(″后綴表達式：″，s1)
思維點撥
明考向 本題考查棧的性質
精點撥 (1)①中直接入棧s2，因此肯定是數字。②數字入棧后，如果s1棧元素個數大于等于2且棧頂元素操作符的優先級高于棧頂元素下方的元素，則s1棧元素出棧，并入s2棧；③當循環while st1[top1]！＝″(″：結束后，s1當前棧頂為″(″，需舍去。(2)條件應判斷為如果是操作符，且不是“)”符號，直接入s1棧。
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 在數學運算表達式中，運算符總是置于與相關的兩個運算對象之間，在計算結束后要考慮括號、運算符號的優先性。為了程序實現的方便，波蘭邏輯學家J.Lukasiewicz提出了另一種表示法，將運算符置于其運算對象之后，沒有括號，不用考慮運算符號的優先性。這種表達式稱為后綴表達式，又叫逆波蘭表達式，如表達式“682－2*3÷＋”是“6＋(8－2)*2÷3”的逆波蘭表達式。
如下Python程序段實現了對逆波蘭表達式的計算(假定逆波蘭表達式中的運算對象均為一位數的正整數，且運算符只有加減乘除)。請補全劃線處代碼。
st＝[0]*100
top＝－1
s＝input(″請輸入逆波蘭表達式：″)
i＝0
while iif ″0″<＝s[i]<＝″9″：
top＋＝1
st[top]＝①________
else：
x＝st[top]
②________
y＝st[top]
if s[i]＝＝″＋″：
　　 　　st[top]＝x＋y
elif s[i]＝＝″－″：
　　 　　③________
elif s[i]＝＝″*″：
　　 　　st[top]＝x*y
else：
　　　 　st[top]＝int(y/x)
i＝i＋1
1.某棧入棧序列為“A、B、C、D、E”，若第一個出棧的元素為“C”，最后一個出棧的元素為“E”，則可能的出棧序列有(　　)
A.3種 B.4種
C.5種 D.6種
2.有一空棧S，對待進棧的數據元素序列a，b，c，d，e，f依次進棧、進棧、出棧、進棧、進棧、出棧的操作，操作完成后，棧S的棧頂元素是(　　)
A.c B.d
C.e D.f
3.若出棧順序為bceda，則入棧順序不可能是(　　)
A.abcde B.bceda
C.dabec D.cbade
4.有四個元素A，B，C，D按順序入棧。約定：P操作是指一個元素入棧，O操作是指一個元素出棧。經過一系列操作后，四個元素的出棧順序為C，D，B，A，則經過的操作是(　　)
A.PPPOOPOO B.PPPOPOOO
C.PPOOPPOO D.PPPPOOOO
5.若元素入棧的順序是1，2，3，4，5，6，不允許連續三次入棧，則可能的出棧序列為(　　)
A.2，3，5，1，6，4 B.1，2，3，6，5，4
C.2，4，3，1，6，5 D.2，5，4，6，3，1
6.現有棧S和隊列Q，初始狀態均為空，現將數據元素a1，a2，a3，a4，a5，a6依次進入隊列Q，再將出隊的元素依次進入棧S，若出棧的順序為a2，a4，a3，a6，a5，a1，則棧S的容量至少應該為(　　)
A.2 B.3
C.4 D.5
7.使用鍵盤輸入“ac←booo←←un←t”，其中“←”表示一次撤銷操作(刪除前一個字母)。模擬輸入過程，合適的數據結構和最后的單詞分別是(　　)
A.棧about B.棧account
C.隊列about D.隊列account
8.有一字符串″ABCDEF″，各字符按序進入一個棧中，其中字符D第一個出棧，直到字符全部出棧過程，下列說法正確的是(　　)
A.字符F一定是最后出棧
B.字符A不可能第三個出棧
C.字符E一定比字符F后出棧
D.字符E不可能比字符A先出棧
9.有1個空棧，數據“8，9，3，2，4”按順序依次入棧。約定：A操作是指一個數入棧，P操作是指一個數出棧。進行APAAAPPA系列棧操作后，棧中元素從棧底到棧頂依次為(　　)
A.9 4 B.8 3 2
C.9 3 2 D.8 4
10.一個底端封閉的圓柱形乒乓球收納筒，最多可容納4個乒乓球，筒的直徑只允許一個球進出。初始時筒內自底向上已存有1，2號球，然后依次放入4個球，順序為3，4，5，6號，則取出所有乒乓球的順序可能是(　　)
A.2，6，5，4，3，1 B.3，2，1，6，4，5
C.3，2，1，6，5，4 D.5，4，3，2，1，6
11.由元素1，2，3，4，5，6，7，8依次入棧、出棧，要求每次出棧之前至少有兩次連續入棧操作，出棧時可以出棧一個元素，也可以出棧多個元素直至棧空，則數據出棧序列可能是(　　)
A.3，4，2，5，7，6，1，8 B.2，4，3，1，8，7，6，5
C.5，7，6，4，8，3，2，1 D.4，3，5，2，1，6，8，7
12.利用棧求逆波蘭表達式的值時，若棧只有兩個存儲單元，下列表達式中，不會發生溢出的是(　　)
A.ABC*－D－ B.ABCD－*－
C.AB－C*D－ D.AB－CD－*
13.有如下Python程序段：
s＝input(″輸入一個字符串″)
a＝[″″]*6；a[0]＝s[0]
top＝0
for i in range(1，len(s))：
if top>＝0 and s[i]＝＝a[top]：
top－＝1
else：
top＋＝1
a[top]＝s[i]
運行程序段，輸入以下字符串，運行后變量top的值與其它三項不同的是(　　)
A.AABAB B.AAABA
C.BAABA D.BBABA
14.判斷某序列b是否是入棧序列a＝[1，2，3，4，5]的出棧序列，程序如下：
a＝[1，2，3，4，5]
b＝list(map(int，input().split()))
stack＝[]
i＝j＝0
while istack.append(①________)
i＋＝1
while len(stack)>0 and ②________：
stack.pop()
j＋＝1
if len(stack)＝＝0 and i＝＝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]
15.有如下Python程序段：
a＝[21，5，10，9，18，10，5，18，12，11]
n＝len(a)
st＝[0]*n；top＝－1
for i in range(n)：
if top＝＝－1：
top＋＝1
st[top]＝a[i]
else：
if a[i]%2＝＝0：
　 　　　while top>－1 and a[i]>st[top]：
　　 　　　　top－＝1
　　　 　top＋＝1
　 　　　st[top]＝a[i]
while top>－1：
print(st[top]，end＝″ ″)
top－＝1
執行該程序段后，輸出結果為(　　)
A.12 18 18 21 B.18 18 12
C.21 18 18 12 D.11 12 18 18 21
16.有如下Python程序段：
def js(x，y，fh)：
jg＝0
if fh＝＝″＋″：
jg＝y＋x
elif fh＝＝″－″：
　　　　 jg＝y－x
elif fh＝＝″*″：
jg＝y*x
else：
if x！＝0：
　　　 　jg＝y//x
return jg
s＝input()
top，i＝－1，0；st＝[0]*len(s)
while iif ″0″<＝s[i]<＝″9″：
top＋＝1
st[top]＝int(s[i])
else：
x，y＝st[top]，st[top－1]
z＝js(x，y，s[i])
st[top－1]＝z
top－＝1
i＋＝1
print(st[top])
執行該程序段，輸入″541－*6＋″后，輸出的是(　　)
A.－9 B.6
C.21 D.23
17.有如下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]
18.有如下Python程序段：
res＝[]
for i in range(len(a))：
if len(res)＝＝0 or a[i]>res[－1]：
res.append(a[i])
elif len(res)＝＝1：
res[0]＝a[i]
elif len(res)>1 and a[i]>res[－2]：
res[－1]＝a[i]
print(len(res))
執行程序段后，輸出結果為 4，則列表a的值可能為(　　)
A.[0，2，8，7，10] B.[9，6，1，0，7]
C.[3，5，7，8，9] D.[6，1，9，3，8]
19.有如下Python程序段：
import random
s＝[3，2，7，6，9]
st＝[0]*len(s)
top＝－1；i＝0
while iop＝random.randint(0，1)
if top＝＝－1 or op＝＝0 and s[i]>st[top]：
top＋＝1
st[top]＝s[i]
elif op＝＝1 and s[i]>st[top]：
st[top]＝s[i]
i＋＝1
while top！＝－1：
print(st[top]，end＝″ ″)
top－＝1
(1)執行該程序段后，輸出的結果可能是(　　)
A.3 B.9 7 2
C.9 6 3 D.9 7
(2)執行該程序段后，輸出的結果可能性的數量是(　　)
A.3 B.4
C.5 D.7
專題14　棧
知識點一
知識梳理
1.插入　刪除　2.棧頂　3.先進后出，后進先出
經典案例
例1　B
變式1　D　[本題考查棧的基本操作。A選項棧中最大長度為3，需要的長度為6；B選項中若要實現FEDCBA，則需要的棧長度為4；C選項出棧序列中DC均在BA之前，若要實現DC出棧，則接下去出棧順序為AB，無法實現。D選項BF入棧，F出棧，DE入棧，E出棧，D出棧，棧中有元素B，C入棧后接著出棧，B出棧，最后A入棧后出棧。]
例2　A
變式2　C　[棧先進后出，棧頂的元素一定先出，出棧順序為1，2，3，4，5，6，7，則初始的情況一定是降序。A選項1第1個出棧，不可能在棧底，B選項5先于6出棧，因此5應后于6入棧。C選項符合先進后出原則。D選項4先于2出棧，不可能在2的前面入棧。]
知識點二
知識梳理
1.top＝－1　2.top＝＝－1　3.top＋1　4.加1 5.減1
經典案例
例1　D
變式1　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]例2　(1)①″0″<＝i<＝″9″　②zd[st1[top1]]>zd[st1[top1－1]]　③top1－＝1　(2)i in zd and i！＝″)″
變式2　①int(s[i])　②top－＝1　③st[top]＝y－x
解析　本題算法利用棧實現對逆波蘭式的計算。當遇到運算對象時進行進棧操作，遇到運算符時從棧中取出兩個運算對象，運算結果再入棧，重復此操作，直到逆波蘭式結束，最后輸出棧頂元素。①處要將對應的數字符表達式的數值進行入棧操作。②讀取一個數，要作出棧操作。③處將減法運算的結果進行入棧操作。
當堂過關檢測
1.A　[C要出棧，棧中有A和B，E最后一個出棧，因此E最后入棧并馬上出棧，那么D可能在A前面，AB之間和B之后三個位置出棧。]
2.A　[a、b進，b出，c、d進，d出，棧頂為c。]
3.C　[C選項a在d的后面入棧，應在d的前面出棧。]
4.B　[本題考查棧的性質。棧是一種先進后出的數據結構，C要出棧，則A，B，C分別入棧，D入棧后再出棧，最后將棧中B和A分別出棧。]
5.C　[本題考查棧的相關知識。A選項數字5先出棧，數字1，2，3，4在棧中，故4要先于1出棧。B選項數字6出棧時，4，5，6依次入棧，不能續三次入棧。D選項數字5出棧，3，4，5依次入棧。]
6.B　[本題考查棧的性質。a4要出棧必先入棧，a1，a3，a4(a2入棧且已出棧)至少要3個空間。a2，a4，a3出棧后，棧中只有a1，接著a5，a6入棧，因此棧至少3個空間。]
7.A　[本題考查棧和隊列的特性。撤銷操作刪除前一個字母，即后輸入的字母先刪除，符合棧后進先出的特性。依次刪除c，刪除2個o，刪除n，最后的單詞為about。]
8.B　[本題考查棧的性質。字符D第一個出棧，棧中有ABC，因此A至少第4個出棧。]
9.A　[8進8出，9，3，2進，2，3出棧，4入棧。]
10.C　[本題考查棧的基本性質。棧中元素必須滿足先進后出原則。A選項2出棧，接著6要出棧，則棧中有1，3，4，5，6共5個球。B選項6若要出棧，4和5還在棧中，出棧順序是5和4。C選項3進，3，2，1出棧，棧空，4，5，6入棧后再出棧。D選項5要出棧，則棧中元素依次為1，2，3，4，5，棧溢出。]
11.B　[本題考查棧的性質。A選項1、2、3入棧，3出棧，4入棧，4出棧，出棧前至少有兩次連續入棧，4出棧時只有一次入棧；B選項1、2入棧，2出棧，3、4入棧，4、3出棧，5、6、7、8入棧，8、7、6、5出棧，符合要求；C選項1、2、3、4、5入棧，5出棧，6、7入棧，7、6、4出棧，8入棧，8出棧，8出棧時只有一次入棧；D選項1、2、3、4入棧，4、3出棧，5入棧，5出棧，5出棧時只有一次入棧。]
12.C　[本題考查棧的應用。數字入棧，遇到操作符時，彈出棧頂的兩個數字，再將計算結果壓回棧。A、B選項ABC、ABCD入棧，數字大于2。C選項AB入棧，再出棧，A－B計算結果入棧，C入棧，2元素出棧，棧空，(A－B)*C結果入棧，D入棧，(A－B)*C－D結果入棧。D選項AB入棧，再出棧，A－B計算結果入棧，C入棧，D入棧，棧中有3個元素。]
13.C　[本題考查字符串操作的相關知識。觀察代碼，t初值為0，a[t]為第1個字符，從第2個字符開始判斷：若與a(t)相同且t>＝0，則t＝t－1；若與a(t)不同或t<0，則t＝t＋1，a(t)跟蹤新字符依據算法，ABD選項t值變化：－1，0，1，2，而C選項t值變化：1，0，－1，0，可見C選項與其余三項不同，選C。]
14.B　[本題考查棧的操作與程序實現。由第6行的添加操作和第9行的刪除操作可以判斷stack用于存儲棧元素。可以通過將a元素不斷入棧，看能否形成和b一樣的出棧序列。第①空應該讓a中的元素入棧，填寫a[i]。而出棧時，需要判定棧頂元素是否和b序列中當前元素是否一致，一致才能出棧，盡可能形成與b一樣的序列。]
15.A　[本題考查棧的入棧和出棧。把握出入棧的條件，當棧為空(top＝＝－1)時入棧；當a[i]是偶數時，把棧頂中比該數小的數出棧，自身入棧。21入棧，10入棧，18先讓10出棧，再入棧，18入棧，12入棧。]
16.C　[本題考查棧的入棧和出棧。遍歷s，如果是數字則入棧，如果是操作符，取出棧頂和棧頂下方的數據，并進行運算后將結果保存在st[top－1]，并出棧一個元素。]
17.D　[對字符串s兩個一組進行遍歷，如果t為A，將n個cnt入棧，如果是p，對n個元素進行出棧。0入棧，0出棧，1、2、3入棧，3和2出棧，4、5入棧，因此從棧底到棧頂分別為1，4，5。]
18.A　[遍歷數組a，如果棧空或當前元素a[i]大于棧頂元素，入棧。如果棧中只有一個元素，將當前元素a[i]替換棧頂元素。當棧中元素個數大于1且將當前元素a[i]大于res[－2]，將當前元素a[i]替換棧頂元素。]
19.(1)D　[本題考查棧的操作。第1個數據3肯定入棧，但后面大的數，不是入棧就是要替換棧頂元素值。A選項后面比3大的數據入棧或替換。B選項2不可能入棧。C選項7勢必要入棧或替換3，因此6就不可能入棧。]
(2)B　[3肯定入棧，2不能入棧，7要么入棧，要么替換3，因此當前棧頂為7，6就不能入棧，同理9要么入棧，要么替換3，要么替換7，因此共有['973'，'97'，'93'，'9']這4種情況。]

展開更多......

收起↑