資源簡介

專題16　棧
學習目標　1.畫出棧的示意圖，理解入棧和出棧的操作；
2.通過出棧順序，推算入棧順序，理解棧的后進先出的基本特性；
3.根據棧的性質，實現棧的算法實現.
棧主要用于計算過程中保存的臨時數據，是一種只能在數組一端進行存取的數據結構，最大特點是數據在存取時，無需查詢，時間復雜度為O(1)，后存的數據先被取出。棧中元素必須滿足先進后出原則。由于棧頂指針top指向棧中最后一個元素的索引位置，因此棧中元素的個數為top＋1，出棧時往往先要讀取棧頂元素，再向下移動指針，入棧時，需先向上移動指針，再存入數據。
(2023年6月浙江省選考)有如下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'，'#']
重難點1　棧的后進先出特性
同隊列一樣，棧也是一種操作受限的線性表，為了減少查詢的時間，僅允許在表的一端進行插入或刪除。進行插入或刪除操作的一端稱為棧頂，位于棧頂位置的元素稱為棧頂元素；相應地，將表的另一端稱為棧底，位于棧底位置的元素為棧底元素。棧具備“先進后出，后進先出”的特點。
例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
變式1 棧S最大長度為3，若元素a，b，c，d依次入棧，則可能的出棧序列為(　　)
A.d，c，b，a B.b，a，d，c
C.c，a，b，d D.c，d，a，b
例2 棧S從棧底到棧頂的元素依次為1，2，3，隊列Q初始為空。約定：U操作是指元素出棧后入隊，H操作是指元素出隊后再入隊。經過UUHU系列操作后，隊列中隊首到隊尾的元素依次為(　　)
A.2，1，3 B.3，1，2
C.1，3，2 D.2，3，1
變式2 隊列Q和棧S的初始值均為空，數字入棧先后順序為1、2、3、4、5。P表示入棧，T表示元素出棧以后入隊。在進行一系列P、T操作后，隊列中從隊首到隊尾的元素依次為2、1、4、5，則對應的P、T操作是(　　)
A.PPTTPPTPT B.PTPTPPPTT
C.PPTTPPPTT D.PPTTPTPPT
重難點2　棧的算法實現
入棧也叫壓棧操作，把數據元素壓入棧頂。與隊列(tail指向隊尾下一個元素的位置)不同的是，棧頂指針指向棧頂元素，每次入棧時，棧頂指針變量top值加1，再給st[top]賦值。出棧時把棧頂元素取出，同時棧頂指針變量top值減1。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
例1 有如下Python程序段：
s＝″abbacabcbbcc″；s1＝″″
st＝[″″]*100；top＝－1
for i in s：
　 if top＝＝－1 or i！＝st[top]:
　 top＋＝1；st[top]＝i
　 else：
　 top＝top－1
while top>＝0：
　 s1＝st[top]＋s1；top－＝1
print(s1)
執行該程序段后，變量s1的值是(　　)
A.″acba″ B.″cbac″ C.″abca″ D.″cabc″
變式1 有如下Python程序段：
from random import randint
a＝[5，3，2，7，4]
i＝0；top＝－1
st＝[0]*5
while i<＝len(a)－1:
　 n＝randint(1，2)　#randint(1，2)隨機生成1或2
　 if n%2＝＝0:
　 top＋＝1
　 st[top]＝a[i]
　 i＋＝1
　　elif top>＝0:
　 top－＝1
print(st)
運行該程序，輸出結果不可能的是(　　)
A.[5，3，2，7，4] B.[4，2，0，0，0]
C.[5，7，4，0，0] D.[3，2，5，7，0]
例2 有如下 Python 程序段：
s＝[0]*10；q＝[0]*10
a＝[6，3，2，4，2，1，5]
n，top，head，tail＝len(a)，0，0，0
s[top]＝a[0]
for i in range(1，n)：
　 while top！＝－1 and a[i]>s[top]:
q[tail]＝s[top]
tail＋＝1
top－＝1
　 top＋＝1
　 s[top]＝a[i]
while head！＝tail：
　 print(q[head]，end＝' ')
　　head＋＝1
程序段運行后， 輸出第3個數字為(　　)
A.1 B.2 C.3 D.4
變式2 有如下Python程序段：
stk＝[5，2，6，3，7]；lst＝[0]*10；top＝len(stk)－1；q，s＝0，0
while top > － 1：
　 s ＋＝ stk[top]
　 if s % a ＝＝ 0：
　 break
　 else：
　　　 lst[q] ＝ stk[top]
　 q ＋＝ 1
　 top －＝ 1
for i in range (q)：
　 top ＋＝ 1；stk[top] ＝ lst[i]
若a為[2, 4]區間的隨機整數，執行該程序段后， stk的值不可能是(　　)
A.[5, 2, 6, 7, 3] B.[5, 2, 6, 3, 7]
C.[5, 2, 7, 6, 3] D.[5, 2, 7, 3, 6]
重難點1　棧的后進先出特性
1.已知棧st中從棧底到棧頂的元素依次為a、b、c，元素d正等待進棧，以下出棧序列不可能的是(　　)
A.c，b，d，a B.c，d，a，b
C.c，d，b，a D.c，b，a，d
2.有1個棧初始為空，其元素入棧順序依次為s，t，r，w，u，y，m，若經過進棧和出棧操作后，棧底至棧頂元素分別為t，w，y，則第3個出棧元素為(　　)
A.m B.w C.u D.s
3.棧S初始狀態為空棧，將序列3，2，5，7，1中元素逐一入棧，當棧空或入棧元素比棧頂元素大時則入棧，否則出棧至符合條件再入棧。序列所有元素入棧完畢后，棧內剩余元素出棧，直至棧空。則出棧的順序是(　　)
A.17523 B.37521 C.37512 D.32751
4.設棧S初始狀態為空，元素A、B、C、D、E、F依次入棧，出棧的序列為D、F、E、C、B、A，則棧S的容量至少應該是(　　)
A.5 B.4 C.3 D.2
5.棧s和隊列q的初始狀態均為空，元素a1、a2、a3、a4、a5、a6依次入棧，再將出棧后的元素依次進入隊列，若入隊的順序為a2、a4、a3、a6、a5、a1，則棧s的容量至少是(　　)
A.2 B.3 C.4 D.5
6.棧初始為空，經過一系列入棧、出棧操作后，棧又為空。元素a，b，c，d，e，f依次入棧，在第2個出棧為元素d的序列中，則第3個出棧的元素個數可能為(　　)
A.2 B.3 C.4 D.5
重難點2　棧的算法實現
1.有如下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]
2.有如下程序段：
s ＝ list(input(″輸入一個字符串s：″))　#list 函數將s轉換為列表
top ＝ －1
a ＝ [0]*100
i ＝ 0
while i < len(s)：
　　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
3.有如下 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
4.有如下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 i執行該程序段，輸入″541－*6＋″后，輸出的是(　　)
A.－9 B.6 C.21 D.23
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 < tail and top > －1:
　 if st[top]＝＝que[head]：
　 head＋＝ 1
　 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']
6.執行下列Python程序代碼：
from random import randint
st ＝ [''] * 10；top ＝ －1；out ＝ ''
s ＝″ABCDE″
while len(s)>0 ：
　 if randint(0，1) ＝＝ 1 ：
　 top ＋＝ 1；st[top] ＝ s[0]
　 s ＝ s[1 : ]
　 elif top ！＝ －1：
　 out ＋＝ st[top]；top－＝ 1
while top ！＝ －1：
　 out ＋＝ st[top]；top－＝ 1
print(out)
輸出的結果不可能的是(　　)
A.CEDAB B.BDECA
C.ABCED D.DCBEA
重難點1　棧的后進先出特性
1.有五個元素的出棧順序依次為1，2，3，4，5。則這五個元素的入棧順序可能是(　　)
A.1，4，5，3，2 B.2，4，3，1，5
C.3，5，4，1，2 D.5，4，1，3，2
2.某棧入棧序列為“A、B、C、D、E”，若第一個出棧的元素為“C”，最后一個出棧的元素為“E”，則可能的出棧序列有(　　)
A.3種 B.4種 C.5種 D.6種
3.用“除二取余”法將十進制轉換為二進制數，用棧的方法操作，需要把得到的余數依次入棧，除盡后再把余數出棧即可。若要將十進制數n(0≤n<64)轉換為二進制數，則設置棧的長度至少為(　　)
A.3　 B.4 C.5 D.6
4.有一個空棧，若元素入棧的順序是a，b，c，d，e，第1個出棧的元素是d，則當所有元素都出棧后，下列說法正確的是(　　)
A.c一定比a，b先出棧
B.最后一個出棧的元素一定是e
C.最后一個出棧的元素一定是a
D.a，b，c出棧的先后順序不確定
5.有一個空棧，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入棧，其中“o”第一個出棧。則當所有元素全部出棧后，下列說法正確的是(　　)
A.出棧的最后一個元素一定為“P”
B.出棧的最后一個元素一定為“n”
C.元素“h”一定比“P”、“y”、“t”先出棧
D.元素“P”、“y”、“t”、“h”、“o”的出棧序列是不確定的
6.棧S初始為空，將1，4，1，1，4，5，2，5，3，2，3依次入棧，當某個元素入棧后，如果此刻棧頂元素和棧中其他元素相同，將這兩個元素間的所有數據出棧(包括這兩個元素)，再繼續后面數據的入棧操作，最后棧中棧頂到棧底的元素依次為(　　)
A.1，4 B.1，4，5，3
C.4，1 D.3，5，2
7.某種表達式可通過棧來求解，方法如下：遍歷表達式，遇到數值則入棧，遇到運算符，則將棧頂兩個數值出棧，用該運算符計算，并將結果入棧。按照該方法直到遍歷完表達式，棧頂元素即為表達式的運算結果。若X代表入棧，Y代表出棧，當利用棧求表達式“123*＋”時，棧的操作序號為(　　)
A.XXXYYYYX B.XXXYYXYYX
C.XXYYXXYY D.XXXXYYYXXYYYX
8.設棧P和隊列Q的初始狀態均為空，元素abcdefg依次進入棧P，若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是cedbgfa，則棧P的容量至少是(　　)
A.2 B.3 C.4 D.5
9.棧S1從棧底到棧頂的元素順序由1，2，3改為3，2，1，可借助初始均為空、長度均為3的棧S2、棧S3出入棧操作來實現，則需要出棧操作的總次數至少是(　　)
A.6 B.7 C.8 D.9
10.利用棧求逆波蘭表達式(表達式由操作數和運算符組成)的方法是：從左往右掃描該表達式，遇到操作數時入 棧；遇到運算符時，把處于棧上方的兩個元素依次出棧，用運算符計算，并把計算結果壓入棧中。如此反復 操作，直至表達式掃描結束。當用該算法求逆波蘭表達式abcd－*e/＋f－的值時 (abcdef 表示不同的操作數)，所使用棧的深度至少為(　　)
A.3 B.4 C.5 D.6
11.有一個隊列和一個棧，其中隊列中隊首到隊尾的元素依次為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
重難點2　棧的算法實現
1.有如下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] < st[top]:
　 top －＝ 1
　 top ＋＝ 1
　 st[top] ＝ a[i]
執行該程序段后，變量top的值為(　　)
A.－1 B.1 C.2 D.3
2.有如下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
3.有如下Python程序段：
lst＝[3, 5, 6, 7, 10, 11, 14, 16]
i＝len(lst)－1
stk＝[0]*len(lst)
top＝－1
while i>＝0：
　 if lst[i]%2＝＝0：
　 top＋＝1
　　　stk[top]＝lst[i]
　 else：
　　　lst[i＋top＋1]＝lst[i]
　 i－＝1
i＝0
while top>－1：
　　lst[i]＝stk[top]
　　top－＝1
　　i＋＝1
執行該程序段后，lst[3]的值是(　　)
A.3 B.6 C.14 D.16
4.用棧的思想編寫進制轉換中的“除二取余法”的Python程序如下：
st＝[－1]*100
top＝－1
n＝int(input(″請輸入一個十進制數″))
while n>0：
　
　 n∥＝2
while top！＝－1：
　 print(st[top]，end＝″″)
　　top－＝1
方框處的代碼由以下三個語句組成：①st[top]＝x ②x＝n%2　③top＋＝1下列語句順序正確的是(　　)
A.①②③ B.①③②
C.②①③ D.②③①
5.有如下Python程序段：
import random
p＝″abcde*″；st＝[]；s＝″″
i＝0
while i<＝5：
　 m＝random.randint(0，1)
　 if m＝＝0：
　 st.append(p[i])
　 i＋＝1
　 elif len(st)>0:
　 s＋＝st.pop()
print(s)
執行上述程序段后，輸出結果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
6.有如下程序段：
s＝[″A″，″B″，″C″，″D″，″E″]
m＝[1，3，2，1，2]
st＝[″″]*4；top＝－1
j＝0
for i in range(len(s))：
　 top＋＝1
　 st[top]＝s[i]
　 while top！＝－1 and ord(st[top])－ord(″A″)＝＝m[j]：
　 top－＝ 1
　 j＋＝1
print(st[：top＋1])
執行該程序段后，輸出內容是(　　)
A.[] B.['A', 'C']
C.['A', 'E'] D.['A', 'C', 'E']
7.有如下Python程序段：
import random
lst ＝['A', 'B'，'C'，'D']
st ＝ [0] * len(lst)
i, top ＝ 0，－1
while i < len(lst)：
　 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
執行該程序段后，lst的值不可能是(　　)
A.[ 'A'，'B'，'C'，'D'] B.['A'，'B'，'A'，'C']
C.[ 'A'，'A'，'C'，'D'] D.['A'，'A'，'C'，'A']
8.有如下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]
9.有如下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]
　 elif top>＝1 and op＝＝1 and s[i]>st[top]：
　 st[top]＝s[i]
　 i＋＝1
while top！＝－1：
　 print(st[top]，end＝″″)
　 top－＝1
執行該程序段后，輸出的結果不可能是(　　)
A.3 B.9 6 2
C.9 6 3 D.9 7 3
10.有如下Python程序段：
import random
st＝[0]*10
top＝－1
for i in range(6)：
　 num＝random.randint(1，6)
　 if top＝＝－1 or num>＝st[top]：
　 top＋＝1
　 st[top]＝num
　 elif num%2＝＝0：
　 top－＝1
　 if top＝＝－1：
　 break
print(st[：top＋1])
運行該程序，輸出的結果不可能是(　　)
A.[] B.[5]
C.[2 2 4 5 5] D.[2 3 4 2]
11.有如下Python程序段：
import random
a＝[1，2，3，4，5]
st＝[0]*len(a)；top＝－1
i＝0；res＝[]
while i　 if random.randint(0，1)！＝0 or top＝＝－1:
　 top＋＝1
　　　st[top]＝a[i]
　 else：
　 res.append(st[top])
　 top－＝1
　 continue
　 i＋＝1
while top！＝－1：
　 res.append(st[top])
　 top－＝1
print(res)
運行上述程序，下列輸出res不可能的是(　　)
A.[3，1，2，4，5] B.[1，5，4，3，2]
C.[3，4，2，1，5] D.[1，3，2，4，5]
12.有如下Python程序段：
tmps ＝ [32，28，26，29]
n ＝ len(tmps); top ＝ －1
ans ＝ [0] * n
stk ＝ [－1] * n
for i in range(n)：
　 t ＝ tmps[i]
　 while top > －1 and t > tmps[stk[top]]:
　 d ＝ stk[top]
　 top －＝ 1
　 ans[d] ＝ i － d
　 top ＋＝ 1
　 stk[top] ＝ i
print(ans)
執行該程序段后，輸出的結果是(　　)
A.[1, 0, 0, 1] B.[1, 1, 0, 0]
C.[0, 2, 1, 0] D.[0, 1, 2, 0]
專題16　棧
學習目標　1.畫出棧的示意圖，理解入棧和出棧的操作；
2.通過出棧順序，推算入棧順序，理解棧的后進先出的基本特性；
3.根據棧的性質，實現棧的算法實現.
棧主要用于計算過程中保存的臨時數據，是一種只能在數組一端進行存取的數據結構，最大特點是數據在存取時，無需查詢，時間復雜度為O(1)，后存的數據先被取出。棧中元素必須滿足先進后出原則。由于棧頂指針top指向棧中最后一個元素的索引位置，因此棧中元素的個數為top＋1，出棧時往往先要讀取棧頂元素，再向下移動指針，入棧時，需先向上移動指針，再存入數據。
(2023年6月浙江省選考)有如下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'，'#']
答案　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均已入棧，選項不符合出棧順序。
重難點1　棧的后進先出特性
同隊列一樣，棧也是一種操作受限的線性表，為了減少查詢的時間，僅允許在表的一端進行插入或刪除。進行插入或刪除操作的一端稱為棧頂，位于棧頂位置的元素稱為棧頂元素；相應地，將表的另一端稱為棧底，位于棧底位置的元素為棧底元素。棧具備“先進后出，后進先出”的特點。
例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
答案　B
變式1 棧S最大長度為3，若元素a，b，c，d依次入棧，則可能的出棧序列為(　　)
A.d，c，b，a B.b，a，d，c
C.c，a，b，d D.c，d，a，b
答案　B
解析　本題考查棧的基本性質。A選項d要入棧，至少需要4個長度。B選項a，b入棧，b，a出棧。c，d入棧，d，c出棧。C和D選項a，b入棧，則b先于a出棧。
例2 棧S從棧底到棧頂的元素依次為1，2，3，隊列Q初始為空。約定：U操作是指元素出棧后入隊，H操作是指元素出隊后再入隊。經過UUHU系列操作后，隊列中隊首到隊尾的元素依次為(　　)
A.2，1，3 B.3，1，2
C.1，3，2 D.2，3，1
思維點撥
明考向 本題考查棧和隊列的基本性質
精點撥 兩次出棧后入隊，隊列的結果為3，2。隊首元素出隊后再入隊，隊列為2，3，最后1入隊
答案　D
變式2 隊列Q和棧S的初始值均為空，數字入棧先后順序為1、2、3、4、5。P表示入棧，T表示元素出棧以后入隊。在進行一系列P、T操作后，隊列中從隊首到隊尾的元素依次為2、1、4、5，則對應的P、T操作是(　　)
A.PPTTPPTPT B.PTPTPPPTT
C.PPTTPPPTT D.PPTTPTPPT
答案　A
解析　本題考查棧和隊列的基本性質。 元素1和2先入棧后再出棧入隊，元素3入棧但不出棧，元素4入棧并出棧，元素5入棧并出棧。
重難點2　棧的算法實現
入棧也叫壓棧操作，把數據元素壓入棧頂。與隊列(tail指向隊尾下一個元素的位置)不同的是，棧頂指針指向棧頂元素，每次入棧時，棧頂指針變量top值加1，再給st[top]賦值。出棧時把棧頂元素取出，同時棧頂指針變量top值減1。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
例1 有如下Python程序段：
s＝″abbacabcbbcc″；s1＝″″
st＝[″″]*100；top＝－1
for i in s：
　 if top＝＝－1 or i！＝st[top]:
　 top＋＝1；st[top]＝i
　 else：
　 top＝top－1
while top>＝0：
　 s1＝st[top]＋s1；top－＝1
print(s1)
執行該程序段后，變量s1的值是(　　)
A.″acba″ B.″cbac″ C.″abca″ D.″cabc″
思維點撥
明考向 本題考查棧的操作
精點撥 對字符串進行遍歷，當top＝＝－1時，讀取第一個字符并入棧，若當前的字符與棧相同，進行出棧操作。若與棧頂不同，重新入棧，前4個字符入棧出棧后，棧中沒有元素，接著cabc分別入棧，b入棧接著出棧，c入棧，并兩次出棧。因此棧中只剩下cab
答案　D
變式1 有如下Python程序段：
from random import randint
a＝[5，3，2，7，4]
i＝0；top＝－1
st＝[0]*5
while i<＝len(a)－1:
　 n＝randint(1，2)　#randint(1，2)隨機生成1或2
　 if n%2＝＝0:
　 top＋＝1
　 st[top]＝a[i]
　 i＋＝1
　　elif top>＝0:
　 top－＝1
print(st)
運行該程序，輸出結果不可能的是(　　)
A.[5，3，2，7，4] B.[4，2，0，0，0]
C.[5，7，4，0，0] D.[3，2，5，7，0]
答案　D
解析　生成隨機n為2時，將a[i]進行入棧操作，同時i增加。若n為1且棧不為空時，進行出棧操作。當最后一個元素4入棧后，不可能同時執行出棧操作，因此元素4必定在棧中。A選項每次生成n的值均為2，依次入棧。B選項最多只有2個元素在棧中，且程序運行后，棧中只有元素4。5入棧后出棧，3和2入棧，再依次出棧，7入棧后出棧，4入棧。C選項符5和3入棧，3出棧，2入棧后出棧，7和4入棧。D選項棧中沒有元素4，因此不可能。
例2 有如下 Python 程序段：
s＝[0]*10；q＝[0]*10
a＝[6，3，2，4，2，1，5]
n，top，head，tail＝len(a)，0，0，0
s[top]＝a[0]
for i in range(1，n)：
　 while top！＝－1 and a[i]>s[top]:
q[tail]＝s[top]
tail＋＝1
top－＝1
　 top＋＝1
　 s[top]＝a[i]
while head！＝tail：
　 print(q[head]，end＝' ')
　　head＋＝1
程序段運行后， 輸出第3個數字為(　　)
A.1 B.2 C.3 D.4
思維點撥
明考向 本題考查棧和隊列的綜合應用
精點撥 程序首先建立兩個長度為10的列表s與q，將a[0]入隊。從索引位1開始向后遍歷列表a，將s列表小于a[i]的值出棧，加入隊列q中。輸出隊列q中的元素，輸出23124
答案　A
變式2 有如下Python程序段：
stk＝[5，2，6，3，7]；lst＝[0]*10；top＝len(stk)－1；q，s＝0，0
while top > － 1：
　 s ＋＝ stk[top]
　 if s % a ＝＝ 0：
　 break
　 else：
　　　 lst[q] ＝ stk[top]
　 q ＋＝ 1
　 top －＝ 1
for i in range (q)：
　 top ＋＝ 1；stk[top] ＝ lst[i]
若a為[2, 4]區間的隨機整數，執行該程序段后， stk的值不可能是(　　)
A.[5, 2, 6, 7, 3] B.[5, 2, 6, 3, 7]
C.[5, 2, 7, 6, 3] D.[5, 2, 7, 3, 6]
答案　C
解析　棧中已經有5個元素，將棧頂元素值累加到s中，如果s是a的倍數，結束循環，否則將棧頂元素添加到lst中，再不斷發出棧，最后把列表lst中元素返回到棧中。當a的值為2時，7和3累加值為10，棧中值為B選項。當a的值為3時，7＋3＋6＋2＝18，列表lst中依次為7，3，6，棧中值為D選項。當a的值為4時，7＋3＋6＝16，列表lst中依次為7，3，棧中值為A選項。C選項3較6先出棧，因此3必定先出隊。
重難點1　棧的后進先出特性
1.已知棧st中從棧底到棧頂的元素依次為a、b、c，元素d正等待進棧，以下出棧序列不可能的是(　　)
A.c，b，d，a B.c，d，a，b
C.c，d，b，a D.c，b，a，d
答案　B
解析　棧中有元素a、b、c，則出棧的順序必定是c、b、a。
2.有1個棧初始為空，其元素入棧順序依次為s，t，r，w，u，y，m，若經過進棧和出棧操作后，棧底至棧頂元素分別為t，w，y，則第3個出棧元素為(　　)
A.m B.w C.u D.s
答案　C
解析　根據棧的特性，在棧中元素后進先出，因此第1個入棧和出棧的元素是s，第3個入棧第2個出棧的元素是r，第5個入棧第3個出棧的元素是u。
3.棧S初始狀態為空棧，將序列3，2，5，7，1中元素逐一入棧，當棧空或入棧元素比棧頂元素大時則入棧，否則出棧至符合條件再入棧。序列所有元素入棧完畢后，棧內剩余元素出棧，直至棧空。則出棧的順序是(　　)
A.17523 B.37521 C.37512 D.32751
答案　B
解析　元素3入棧，3比2大，讓3先出棧，2入棧。接著5和7入棧；1大7小，7，5，2出棧，接入1入棧。
4.設棧S初始狀態為空，元素A、B、C、D、E、F依次入棧，出棧的序列為D、F、E、C、B、A，則棧S的容量至少應該是(　　)
A.5 B.4 C.3 D.2
答案　A
解析　D要出棧，則ABC在棧中，至少要4個，F要出棧，則E在棧中，至少要5個。
5.棧s和隊列q的初始狀態均為空，元素a1、a2、a3、a4、a5、a6依次入棧，再將出棧后的元素依次進入隊列，若入隊的順序為a2、a4、a3、a6、a5、a1，則棧s的容量至少是(　　)
A.2 B.3 C.4 D.5
答案　B
解析　出棧的順序和入隊的順序一致，當a4入棧時，已經出棧1個元素，因此容量至少需3個。當a6入棧時，已經出棧3個元素，因此容量至少需3個。
6.棧初始為空，經過一系列入棧、出棧操作后，棧又為空。元素a，b，c，d，e，f依次入棧，在第2個出棧為元素d的序列中，則第3個出棧的元素個數可能為(　　)
A.2 B.3 C.4 D.5
答案　C
解析　本題考查棧的性質。若第1個出棧的元素為e，則棧中有元素a，b，c，d，第3個出棧的元素為c或f；若第1個出棧的元素為f，則d不可能是第2個出棧的元素。若第1個出棧的元素為a，棧中有元素b，c，d，第3個出棧的元素可能為c或e。若第1個出棧的元素為b，棧中有元素a，c，d，第3個出棧的元素不可能是a。若第1個出棧的元素為c，棧中有元素a，b，c，第3個出棧的元素不可能是b。因此第3個出棧的元素可能是b，c，e，f。
重難點2　棧的算法實現
1.有如下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]
答案　D
解析　對字符串s兩個一組進行遍歷，如果t為A，將n個cnt入棧，如果是p，對n個元素進行出棧。0入棧，0出棧，1、2、3入棧，3和2出棧，4、5入棧，因此從棧底到棧頂分別為1, 4, 5。
2.有如下程序段：
s ＝ list(input(″輸入一個字符串s：″))　#list 函數將s轉換為列表
top ＝ －1
a ＝ [0]*100
i ＝ 0
while i < len(s)：
　　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。
3.有如下 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
答案　 A
解析　本題考查棧的入棧和出棧。把握出入棧的條件，當棧為空(top＝＝－1)時入棧；當a[i]是偶數時，把棧頂中比該數小的輸出棧，自身入棧。21入棧，10入棧，18先讓10出棧，再入棧，18入棧，12入棧。
4.有如下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 i執行該程序段，輸入″541－*6＋″后，輸出的是(　　)
A.－9 B.6 C.21 D.23
答案　C
解析　本題考查棧的入棧和出棧。遍歷s，如果是數字則入棧，如果是操作符，取出棧頂和棧頂下方的數據，并進行運算后將結果保存在st[top－1]，并出棧一個元素。
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 < tail and top > －1:
　 if st[top]＝＝que[head]：
　 head＋＝ 1
　 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']
答案　 A
解析　 第1個循環讓abc依次入隊。當隊列和棧不為空時，如果棧頂元素和隊首元素相同，則進行出隊和出棧操作，否則將棧頂元素出棧并入隊。棧頂和隊首均為″a″，出隊和出棧操作，接著″d″入隊，″d″出棧，接著″c″入隊，″c″出棧，隊列中元素為″bcdc″，接著″b″出隊和出棧。
6.執行下列Python程序代碼：
from random import randint
st ＝ [''] * 10；top ＝ －1；out ＝ ''
s ＝″ABCDE″
while len(s)>0 ：
　 if randint(0，1) ＝＝ 1 ：
　 top ＋＝ 1；st[top] ＝ s[0]
　 s ＝ s[1 : ]
　 elif top ！＝ －1：
　 out ＋＝ st[top]；top－＝ 1
while top ！＝ －1：
　 out ＋＝ st[top]；top－＝ 1
print(out)
輸出的結果不可能的是(　　)
A.CEDAB B.BDECA
C.ABCED D.DCBEA
答案　A
解析　遍歷字符串s，當產生的隨機數為1時，將字符串s第1個字符入棧并去除該字符。若隨機數為0且棧不空，則進行出棧操作，將出棧的字符連接到out中，由于棧的順序為ABCDE，則A選項中，A必須晚于B出棧。
重難點1　棧的后進先出特性
1.有五個元素的出棧順序依次為1，2，3，4，5。則這五個元素的入棧順序可能是(　　)
A.1，4，5，3，2 B.2，4，3，1，5
C.3，5，4，1，2 D.5，4，1，3，2
答案　D
解析　A選項4比5先入棧，則5應先出棧。B選項1要出棧，棧中有元素2，4，3，則4必須先于3出棧。C選項1要出棧，棧中有元素3，5，4，則4必須先于3出棧。D選項5，4，1入棧，接著1出棧，3和2入棧，再依次出棧。
2.某棧入棧序列為“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之后三個位置出棧。
3.用“除二取余”法將十進制轉換為二進制數，用棧的方法操作，需要把得到的余數依次入棧，除盡后再把余數出棧即可。若要將十進制數n(0≤n<64)轉換為二進制數，則設置棧的長度至少為(　　)
A.3　 B.4 C.5 D.6
答案　D
解析　十進制數 n(0≤n＜64)轉換為二進制數，得到最大的是6位二進制數。
4.有一個空棧，若元素入棧的順序是a，b，c，d，e，第1個出棧的元素是d，則當所有元素都出棧后，下列說法正確的是(　　)
A.c一定比a，b先出棧
B.最后一個出棧的元素一定是e
C.最后一個出棧的元素一定是a
D.a，b，c出棧的先后順序不確定
答案　A
解析　d出棧，則棧中有元素a，b，c。因此c一定比a，b先出棧，且a，b，c出棧的先后順序是確定的。e可能是第2個出棧的，也可能是最后一個出棧的。
5.有一個空棧，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入棧，其中“o”第一個出棧。則當所有元素全部出棧后，下列說法正確的是(　　)
A.出棧的最后一個元素一定為“P”
B.出棧的最后一個元素一定為“n”
C.元素“h”一定比“P”、“y”、“t”先出棧
D.元素“P”、“y”、“t”、“h”、“o”的出棧序列是不確定的
答案　C
解析　本題考查棧的性質。o出棧時，n還沒有入棧，因此n可能是最后一個出棧，也可能在其他元素出棧過程中，入棧后再出棧。o出棧時，P，y，t，h均已在棧中，故元素出棧序列是確定的。
6.棧S初始為空，將1，4，1，1，4，5，2，5，3，2，3依次入棧，當某個元素入棧后，如果此刻棧頂元素和棧中其他元素相同，將這兩個元素間的所有數據出棧(包括這兩個元素)，再繼續后面數據的入棧操作，最后棧中棧頂到棧底的元素依次為(　　)
A.1，4 B.1，4，5，3
C.4，1 D.3，5，2
答案　C
解析　元素1，4，1依次入棧后，棧空。元素1，4，5，2，5入棧后，棧中有元素1，4。元素5，2，5入棧，使得這些元素出棧。元素3，2，3入棧，使得這些元素出棧。
7.某種表達式可通過棧來求解，方法如下：遍歷表達式，遇到數值則入棧，遇到運算符，則將棧頂兩個數值出棧，用該運算符計算，并將結果入棧。按照該方法直到遍歷完表達式，棧頂元素即為表達式的運算結果。若X代表入棧，Y代表出棧，當利用棧求表達式“123*＋”時，棧的操作序號為(　　)
A.XXXYYYYX B.XXXYYXYYX
C.XXYYXXYY D.XXXXYYYXXYYYX
答案　B
解析　遇到1，2，3入棧，棧為[1，2，3]，即XXX；遇到*，出棧頂的2個數值計算后再入棧，棧為[1，6]，即YYX；遇到＋，同樣出棧頂的2個數值計算后再入棧，棧為[7]，即YYX。
8.設棧P和隊列Q的初始狀態均為空，元素abcdefg依次進入棧P，若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是cedbgfa，則棧P的容量至少是(　　)
A.2 B.3 C.4 D.5
答案　C
解析　隊列出隊的順序就是元素出棧的順序，元素c出棧，棧中要到3個空間。e出棧，棧中要到4個空間。d和b出棧后，占用2個空間。f和g入棧需4個空間。
9.棧S1從棧底到棧頂的元素順序由1，2，3改為3，2，1，可借助初始均為空、長度均為3的棧S2、棧S3出入棧操作來實現，則需要出棧操作的總次數至少是(　　)
A.6 B.7 C.8 D.9
答案　B
解析　元素3出棧并入棧2，元素1和2出棧并入棧3；元素3從棧2中出來并入棧1，元素1從棧3到棧2，元素2出棧3并入棧1，元素1出棧2并入棧1。
10.利用棧求逆波蘭表達式(表達式由操作數和運算符組成)的方法是：從左往右掃描該表達式，遇到操作數時入 棧；遇到運算符時，把處于棧上方的兩個元素依次出棧，用運算符計算，并把計算結果壓入棧中。如此反復 操作，直至表達式掃描結束。當用該算法求逆波蘭表達式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。
11.有一個隊列和一個棧，其中隊列中隊首到隊尾的元素依次為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。
重難點2　棧的算法實現
1.有如下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] < st[top]:
　 top －＝ 1
　 top ＋＝ 1
　 st[top] ＝ a[i]
執行該程序段后，變量top的值為(　　)
A.－1 B.1 C.2 D.3
答案　C
解析　棧中初始有一個值，從索引位置1開始遍歷，當遍歷到的數比棧頂小時，將棧頂元素出棧，自身入棧。遍歷到1時，讓4和6出棧。7入棧，2使得7出棧，8入棧，6使得8出棧，因此棧中有1、2和6共3個元素，top值為2。
2.有如下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
答案　C
解析　本題考查棧的性質。棧初始值有一個元素s[0]，從索引位置1開始遍歷s，如果s[i]與棧頂元素相同，進行出棧操作，否則進行入棧操作。A選項棧中元素有BAB，top的值為2。B和D選項棧中元素有ABA，top的值為2。C選項棧中元素有A，top的值為0。
3.有如下Python程序段：
lst＝[3, 5, 6, 7, 10, 11, 14, 16]
i＝len(lst)－1
stk＝[0]*len(lst)
top＝－1
while i>＝0：
　 if lst[i]%2＝＝0：
　 top＋＝1
　　　stk[top]＝lst[i]
　 else：
　　　lst[i＋top＋1]＝lst[i]
　 i－＝1
i＝0
while top>－1：
　　lst[i]＝stk[top]
　　top－＝1
　　i＋＝1
執行該程序段后，lst[3]的值是(　　)
A.3 B.6 C.14 D.16
答案　D
解析　本題考查棧的應用。從后往前遍歷列表lst，判斷元素的奇偶性，將偶數入棧、奇數元素往后移動top＋1個位置，其中top＋1是表示棧的元素個數，當前偶數元素個數。再進行出棧操作，覆蓋列表前面的元素。程序執行后，lst元素依次是[6，10，14，16，3，5，7，11]。
4.用棧的思想編寫進制轉換中的“除二取余法”的Python程序如下：
st＝[－1]*100
top＝－1
n＝int(input(″請輸入一個十進制數″))
while n>0：
　
　 n∥＝2
while top！＝－1：
　 print(st[top]，end＝″″)
　　top－＝1
方框處的代碼由以下三個語句組成：①st[top]＝x ②x＝n%2　③top＋＝1下列語句順序正確的是(　　)
A.①②③ B.①③②
C.②①③ D.②③①
答案　D
解析　入棧必先移動top指針，入棧元素為x，先對x進行除2的余數賦值。
5.有如下Python程序段：
import random
p＝″abcde*″；st＝[]；s＝″″
i＝0
while i<＝5：
　 m＝random.randint(0，1)
　 if m＝＝0：
　 st.append(p[i])
　 i＋＝1
　 elif len(st)>0:
　 s＋＝st.pop()
print(s)
執行上述程序段后，輸出結果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
答案　D
解析　若產生的隨機數m值為0，進行入棧操作。否則出棧后并連接到字符串s中。則于最后一個字符*一旦入棧后，i的值為5，結束循環，就不可能出棧。B選項a比b先入棧，出棧順序應相反。D選項abc先入棧，c出棧，d入棧后出棧，最后a出棧。
6.有如下程序段：
s＝[″A″，″B″，″C″，″D″，″E″]
m＝[1，3，2，1，2]
st＝[″″]*4；top＝－1
j＝0
for i in range(len(s))：
　 top＋＝1
　 st[top]＝s[i]
　 while top！＝－1 and ord(st[top])－ord(″A″)＝＝m[j]：
　 top－＝ 1
　 j＋＝1
print(st[：top＋1])
執行該程序段后，輸出內容是(　　)
A.[] B.['A', 'C']
C.['A', 'E'] D.['A', 'C', 'E']
答案　C
解析　遍歷列表s，將每個元素入棧，若當前棧頂元素與ord(″A″)差值為m[j]，則將棧頂元素出棧處理。元素″A″和″B″入棧，″B″與ord(″A″)差值為m[j]為1，″B″出棧，j加1，m[j]值為3，元素″C″和″D″入棧，″D″與ord(″A″)差值為m[j]為3，″D″出棧；j加1，m[j]值為2，棧頂為元素為″C″，″C″出棧，最后″E″入棧。
7.有如下Python程序段：
import random
lst ＝['A', 'B'，'C'，'D']
st ＝ [0] * len(lst)
i, top ＝ 0，－1
while i < len(lst)：
　 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
執行該程序段后，lst的值不可能是(　　)
A.[ 'A'，'B'，'C'，'D'] B.['A'，'B'，'A'，'C']
C.[ 'A'，'A'，'C'，'D'] D.['A'，'A'，'C'，'A']
答案　B
解析　當k的值為0時，進行入棧操作；當k的值為1且棧不為空，進行出棧并替換lst[i]操作。由于i ＋＝ 1操作發生在入棧過程中，因此必須有4個元素出棧，但棧中可能有元素未出棧。A選項當隨機數4次均為0，全部元素均在棧中。C選項隨機數依次為0，1，0，0，有兩個元素在棧中。D選項隨機數依次為0，1，0，1，1，0，A先入棧，出棧后替換B，原B位置上的A再次入棧，最后替換D。B選項當i的值為2時，AB在棧中，應該B先出棧。
8.有如下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]
答案　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依次入棧。
9.有如下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]
　 elif top>＝1 and op＝＝1 and s[i]>st[top]：
　 st[top]＝s[i]
　 i＋＝1
while top！＝－1：
　 print(st[top]，end＝″″)
　 top－＝1
執行該程序段后，輸出的結果不可能是(　　)
A.3 B.9 6 2
C.9 6 3 D.9 7 3
答案　B
解析　本題考查棧的應用。當棧空入棧，因此3肯定在棧中。當op為0且s[i]>st[top]時，s[i]入棧，若產生op的值一直為1，則棧中只有3；入棧的元素比棧中元素大，2小于3，因此2不可能入棧。由于棧中至少有2個元素時，才要進行替換操作，當op為1，棧中只有一個元素，7沒有入棧，則6可能入棧。
10.有如下Python程序段：
import random
st＝[0]*10
top＝－1
for i in range(6)：
　 num＝random.randint(1，6)
　 if top＝＝－1 or num>＝st[top]：
　 top＋＝1
　 st[top]＝num
　 elif num%2＝＝0：
　 top－＝1
　 if top＝＝－1：
　 break
print(st[：top＋1])
運行該程序，輸出的結果不可能是(　　)
A.[] B.[5]
C.[2 2 4 5 5] D.[2 3 4 2]
答案　D
解析　本題主要考查的是棧的基本操作。循環6次，每次先產生一個1到6之間的數num，若num大于等于棧頂，將該數入棧，若num比棧頂元素小且為偶數，將棧頂元素出棧。若棧空，結束程序。A選項產生第一個數，入棧，產生的第二個數比棧頂元素小且為偶數，將棧頂元素出棧，棧空。B選項產生隨機數5，入棧，接著產生2個大于等于5的數，并入棧，再產生2個較小的偶數，讓后面產生的數出棧。C選項一共循環6次，因此不可能是產生了6個數，一個較小偶數讓其中一個數出棧情況，只可能是產生一個比較棧頂小的奇數，如在2后面產生了1，既不入棧，也不出棧。D選項最后一個2不可能入棧。
11.有如下Python程序段：
import random
a＝[1，2，3，4，5]
st＝[0]*len(a)；top＝－1
i＝0；res＝[]
while i　 if random.randint(0，1)！＝0 or top＝＝－1:
　 top＋＝1
　　　st[top]＝a[i]
　 else：
　 res.append(st[top])
　 top－＝1
　 continue
　 i＋＝1
while top！＝－1：
　 res.append(st[top])
　 top－＝1
print(res)
運行上述程序，下列輸出res不可能的是(　　)
A.[3，1，2，4，5] B.[1，5，4，3，2]
C.[3，4，2，1，5] D.[1，3，2，4，5]
答案　A
解析　本題考查棧的應用。棧空或產生隨機數為1，將a[i]入棧，否則出棧并追加到res中，且語句i＋＝1不執行，因此只有5個元素全部出棧后，程序才終止運行。A選項123入棧，3出棧，則2必須在1的前面出棧。
12.有如下Python程序段：
tmps ＝ [32，28，26，29]
n ＝ len(tmps); top ＝ －1
ans ＝ [0] * n
stk ＝ [－1] * n
for i in range(n)：
　 t ＝ tmps[i]
　 while top > －1 and t > tmps[stk[top]]:
　 d ＝ stk[top]
　 top －＝ 1
　 ans[d] ＝ i － d
　 top ＋＝ 1
　 stk[top] ＝ i
print(ans)
執行該程序段后，輸出的結果是(　　)
A.[1, 0, 0, 1] B.[1, 1, 0, 0]
C.[0, 2, 1, 0] D.[0, 1, 2, 0]
答案　C
解析　 本題考查棧的基本操作。遍歷tmps列表，若棧為空，將tmps元素的索引值存入棧中。若棧不空且tmps[i]大于tmps[stk[top]](棧頂元素)，計算i －d的值并保存在ans[d]再將當前元素索引入棧 。(共80張PPT)
第三部分　數據的存儲與邏輯結構
專題16　棧
1.畫出棧的示意圖，理解入棧和出棧的操作；
2.通過出棧順序，推算入棧順序，理解棧的后進先出的基本特性；
3.根據棧的性質，實現棧的算法實現.
目 錄
CONTENTS
體系構建
01
真題再現
02
考點精練
03
當堂檢測
04
課后練習
05
體系構建
1
棧主要用于計算過程中保存的臨時數據，是一種只能在數組一端進行存取的數據結構，最大特點是數據在存取時，無需查詢，時間復雜度為O(1)，后存的數據先被取出。棧中元素必須滿足先進后出原則。由于棧頂指針top指向棧中最后一個元素的索引位置，因此棧中元素的個數為top＋1，出棧時往往先要讀取棧頂元素，再向下移動指針，入棧時，需先向上移動指針，再存入數據。
真題再現
2
執行該程序段后，a的值不可能的是(　　)
A.['A'，'B'，'#'，'#'，'C'，'D'，'#'] B.['#'，'#'，'#'，'#'，'#'，'#'，'#']
C.['#'，'B'，'#'，'#'，'C'，'D'，'A'] D.['#'，'#'，'A'，'B'，'C'，'D'，'#']
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均已入棧，選項不符合出棧順序。
考點精練
3
重難點1　棧的后進先出特性
同隊列一樣，棧也是一種操作受限的線性表，為了減少查詢的時間，僅允許在表的一端進行插入或刪除。進行插入或刪除操作的一端稱為棧頂，位于棧頂位置的元素稱為棧頂元素；相應地，將表的另一端稱為棧底，位于棧底位置的元素為棧底元素。棧具備“先進后出，后進先出”的特點。
例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
B
思維點撥
明考向 本題考查棧的基本性質
精　點　撥 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，若元素a，b，c，d依次入棧，則可能的出棧序列為(　　)
A.d，c，b，a B.b，a，d，c
C.c，a，b，d D.c，d，a，b
B
解析　本題考查棧的基本性質。A選項d要入棧，至少需要4個長度。B選項a，b入棧，b，a出棧。c，d入棧，d，c出棧。C和D選項a，b入棧，則b先于a出棧。
例2 棧S從棧底到棧頂的元素依次為1，2，3，隊列Q初始為空。約定：U操作是指元素出棧后入隊，H操作是指元素出隊后再入隊。經過UUHU系列操作后，隊列中隊首到隊尾的元素依次為(　　)
A.2，1，3 B.3，1，2
C.1，3，2 D.2，3，1
D
思維點撥
明考向 本題考查棧和隊列的基本性質
精點撥 兩次出棧后入隊，隊列的結果為3，2。隊首元素出隊后再入隊，隊列為2，3，最后1入隊
變式2 隊列Q和棧S的初始值均為空，數字入棧先后順序為1、2、3、4、5。P表示入棧，T表示元素出棧以后入隊。在進行一系列P、T操作后，隊列中從隊首到隊尾的元素依次為2、1、4、5，則對應的P、T操作是(　　)
A.PPTTPPTPT B.PTPTPPPTT
C.PPTTPPPTT D.PPTTPTPPT
A
解析　本題考查棧和隊列的基本性質。 元素1和2先入棧后再出棧入隊，元素3入棧但不出棧，元素4入棧并出棧，元素5入棧并出棧。
重難點2　棧的算法實現
入棧也叫壓棧操作，把數據元素壓入棧頂。與隊列(tail指向隊尾下一個元素的位置)不同的是，棧頂指針指向棧頂元素，每次入棧時，棧頂指針變量top值加1，再給st[top]賦值。出棧時把棧頂元素取出，同時棧頂指針變量top值減1。如果棧中沒有元素時，即top＝－1，不能進行出棧操作。
D
思維點撥
明考向 本題考查棧的操作
精點撥 對字符串進行遍歷，當top＝＝－1時，讀取第一個字符并入棧，若當前的字符與棧相同，進行出棧操作。若與棧頂不同，重新入棧，前4個字符入棧出棧后，棧中沒有元素，接著cabc分別入棧，b入棧接著出棧，c入棧，并兩次出棧。因此棧中只剩下cab
D
解析　生成隨機n為2時，將a[i]進行入棧操作，同時i增加。若n為1且棧不為空時，進行出棧操作。當最后一個元素4入棧后，不可能同時執行出棧操作，因此元素4必定在棧中。A選項每次生成n的值均為2，依次入棧。B選項最多只有2個元素在棧中，且程序運行后，棧中只有元素4。5入棧后出棧，3和2入棧，再依次出棧，7入棧后出棧，4入棧。C選項符5和3入棧，3出棧，2入棧后出棧，7和4入棧。D選項棧中沒有元素4，因此不可能。
A
思維點撥
明考向 本題考查棧和隊列的綜合應用
精點撥 程序首先建立兩個長度為10的列表s與q，將a[0]入隊。從索引位1開始向后遍歷列表a，將s列表小于a[i]的值出棧，加入隊列q中。輸出隊列q中的元素，輸出23124
C
解析　棧中已經有5個元素，將棧頂元素值累加到s中，如果s是a的倍數，結束循環，否則將棧頂元素添加到lst中，再不斷發出棧，最后把列表lst中元素返回到棧中。當a的值為2時，7和3累加值為10，棧中值為B選項。當a的值為3時，7＋3＋6＋2＝18，列表lst中依次為7，3，6，棧中值為D選項。當a的值為4時，7＋3＋6＝16，列表lst中依次為7，3，棧中值為A選項。C選項3較6先出棧，因此3必定先出隊。
當堂檢測
4
重難點1　棧的后進先出特性
重難點2　棧的算法實現
B
解析　棧中有元素a、b、c，則出棧的順序必定是c、b、a。
C
解析　根據棧的特性，在棧中元素后進先出，因此第1個入棧和出棧的元素是s，第3個入棧第2個出棧的元素是r，第5個入棧第3個出棧的元素是u。
2.有1個棧初始為空，其元素入棧順序依次為s，t，r，w，u，y，m，若經過進棧和出棧操作后，棧底至棧頂元素分別為t，w，y，則第3個出棧元素為(　　)
A.m B.w C.u D.s
B
解析　元素3入棧，3比2大，讓3先出棧，2入棧。接著5和7入棧；1大7小，7，5，2出棧，接入1入棧。
3.棧S初始狀態為空棧，將序列3，2，5，7，1中元素逐一入棧，當棧空或入棧元素比棧頂元素大時則入棧，否則出棧至符合條件再入棧。序列所有元素入棧完畢后，棧內剩余元素出棧，直至棧空。則出棧的順序是(　　)
A.17523 B.37521 C.37512 D.32751
A
解析　D要出棧，則ABC在棧中，至少要4個，F要出棧，則E在棧中，至少要5個。
4.設棧S初始狀態為空，元素A、B、C、D、E、F依次入棧，出棧的序列為D、F、E、C、B、A，則棧S的容量至少應該是(　　)
A.5 B.4 C.3 D.2
B
解析　出棧的順序和入隊的順序一致，當a4入棧時，已經出棧1個元素，因此容量至少需3個。當a6入棧時，已經出棧3個元素，因此容量至少需3個。
5.棧s和隊列q的初始狀態均為空，元素a1、a2、a3、a4、a5、a6依次入棧，再將出棧后的元素依次進入隊列，若入隊的順序為a2、a4、a3、a6、a5、a1，則棧s的容量至少是(　　)
A.2 B.3 C.4 D.5
C
解析　本題考查棧的性質。若第1個出棧的元素為e，則棧中有元素a，b，c，d，第3個出棧的元素為c或f；若第1個出棧的元素為f，則d不可能是第2個出棧的元素。若第1個出棧的元素為a，棧中有元素b，c，d，第3個出棧的元素可能為c或e。若第1個出棧的元素為b，棧中有元素a，c，d，第3個出棧的元素不可能是a。若第1個出棧的元素為c，棧中有元素a，b，c，第3個出棧的元素不可能是b。因此第3個出棧的元素可能是b，c，e，f。
6.棧初始為空，經過一系列入棧、出棧操作后，棧又為空。元素a，b，c，d，e，f依次入棧，在第2個出棧為元素d的序列中，則第3個出棧的元素個數可能為(　　)
A.2 B.3 C.4 D.5
D
解析　對字符串s兩個一組進行遍歷，如果t為A，將n個cnt入棧，如果是p，對n個元素進行出棧。0入棧，0出棧，1、2、3入棧，3和2出棧，4、5入棧，因此從棧底到棧頂分別為1, 4, 5。
A
解析　本題考查棧的性質和基本操作。遇到'('對應的下標入棧，遇到')'，元素出棧。同時列表元素重新組合，組合原則：二端不動，最內層配對括號內的元素翻轉，同時這對括號拋棄。算法過程：(ed(y(oc))p)→(ed(yco)p)→(edocyp)→pycode。
A
解析　本題考查棧的入棧和出棧。把握出入棧的條件，當棧為空(top＝＝－1)時入棧；當a[i]是偶數時，把棧頂中比該數小的輸出棧，自身入棧。21入棧，10入棧，18先讓10出棧，再入棧，18入棧，12入棧。
4.有如下Python程序段：
C
解析　本題考查棧的入棧和出棧。遍歷s，如果是數字則入棧，如果是操作符，取出棧頂和棧頂下方的數據，并進行運算后將結果保存在st[top－1]，并出棧一個元素。
A
解析　 第1個循環讓abc依次入隊。當隊列和棧不為空時，如果棧頂元素和隊首元素相同，則進行出隊和出棧操作，否則將棧頂元素出棧并入隊。棧頂和隊首均為″a″，出隊和出棧操作，接著″d″入隊，″d″出棧，接著″c″入隊，″c″出棧，隊列中元素為″bcdc″，接著″b″出隊和出棧。
輸出的結果不可能的是(　　)
A.CEDAB B.BDECA
C.ABCED D.DCBEA
A
解析　遍歷字符串s，當產生的隨機數為1時，將字符串s第1個字符入棧并去除該字符。若隨機數為0且棧不空，則進行出棧操作，將出棧的字符連接到out中，由于棧的順序為ABCDE，則A選項中，A必須晚于B出棧。
課后練習
5
重難點1　棧的后進先出特性
重難點2　棧的算法實現
1.有五個元素的出棧順序依次為1，2，3，4，5。則這五個元素的入棧順序可能是(　　)
A.1，4，5，3，2 B.2，4，3，1，5
C.3，5，4，1，2 D.5，4，1，3，2
D
解析　A選項4比5先入棧，則5應先出棧。B選項1要出棧，棧中有元素2，4，3，則4必須先于3出棧。C選項1要出棧，棧中有元素3，5，4，則4必須先于3出棧。D選項5，4，1入棧，接著1出棧，3和2入棧，再依次出棧。
2.某棧入棧序列為“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之后三個位置出棧。
3.用“除二取余”法將十進制轉換為二進制數，用棧的方法操作，需要把得到的余數依次入棧，除盡后再把余數出棧即可。若要將十進制數n(0≤n<64)轉換為二進制數，則設置棧的長度至少為(　　)
A.3　 B.4 C.5 D.6
D
解析　十進制數 n(0≤n＜64)轉換為二進制數，得到最大的是6位二進制數。
4.有一個空棧，若元素入棧的順序是a，b，c，d，e，第1個出棧的元素是d，則當所有元素都出棧后，下列說法正確的是(　　)
A.c一定比a，b先出棧
B.最后一個出棧的元素一定是e
C.最后一個出棧的元素一定是a
D.a，b，c出棧的先后順序不確定
A
解析　d出棧，則棧中有元素a，b，c。因此c一定比a，b先出棧，且a，b，c出棧的先后順序是確定的。e可能是第2個出棧的，也可能是最后一個出棧的。
C
解析　本題考查棧的性質。o出棧時，n還沒有入棧，因此n可能是最后一個出棧，也可能在其他元素出棧過程中，入棧后再出棧。o出棧時，P，y，t，h均已在棧中，故元素出棧序列是確定的。
5.有一個空棧，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入棧，其中“o”第一個出棧。則當所有元素全部出棧后，下列說法正確的是(　　)
A.出棧的最后一個元素一定為“P”
B.出棧的最后一個元素一定為“n”
C.元素“h”一定比“P”、“y”、“t”先出棧
D.元素“P”、“y”、“t”、“h”、“o”的出棧序列是不確定的
6.棧S初始為空，將1，4，1，1，4，5，2，5，3，2，3依次入棧，當某個元素入棧后，如果此刻棧頂元素和棧中其他元素相同，將這兩個元素間的所有數據出棧(包括這兩個元素)，再繼續后面數據的入棧操作，最后棧中棧頂到棧底的元素依次為(　　)
A.1，4 B.1，4，5，3
C.4，1 D.3，5，2
C
解析　元素1，4，1依次入棧后，棧空。元素1，4，5，2，5入棧后，棧中有元素1，4。元素5，2，5入棧，使得這些元素出棧。元素3，2，3入棧，使得這些元素出棧。
7.某種表達式可通過棧來求解，方法如下：遍歷表達式，遇到數值則入棧，遇到運算符，則將棧頂兩個數值出棧，用該運算符計算，并將結果入棧。按照該方法直到遍歷完表達式，棧頂元素即為表達式的運算結果。若X代表入棧，Y代表出棧，當利用棧求表達式“123*＋”時，棧的操作序號為(　　)
A.XXXYYYYX B.XXXYYXYYX
C.XXYYXXYY D.XXXXYYYXXYYYX
B
解析　遇到1，2，3入棧，棧為[1，2，3]，即XXX；遇到*，出棧頂的2個數值計算后再入棧，棧為[1，6]，即YYX；遇到＋，同樣出棧頂的2個數值計算后再入棧，棧為[7]，即YYX。
C
解析　隊列出隊的順序就是元素出棧的順序，元素c出棧，棧中要到3個空間。e出棧，棧中要到4個空間。d和b出棧后，占用2個空間。f和g入棧需4個空間。
8.設棧P和隊列Q的初始狀態均為空，元素abcdefg依次進入棧P，若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是cedbgfa，則棧P的容量至少是(　　)
A.2 B.3 C.4 D.5
9.棧S1從棧底到棧頂的元素順序由1，2，3改為3，2，1，可借助初始均為空、長度均為3的棧S2、棧S3出入棧操作來實現，則需要出棧操作的總次數至少是(　　)
A.6 B.7 C.8 D.9
B
解析　元素3出棧并入棧2，元素1和2出棧并入棧3；元素3從棧2中出來并入棧1，元素1從棧3到棧2，元素2出棧3并入棧1，元素1出棧2并入棧1。
10.利用棧求逆波蘭表達式(表達式由操作數和運算符組成)的方法是：從左往右掃描該表達式，遇到操作數時入 棧；遇到運算符時，把處于棧上方的兩個元素依次出棧，用運算符計算，并把計算結果壓入棧中。如此反復 操作，直至表達式掃描結束。當用該算法求逆波蘭表達式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。
11.有一個隊列和一個棧，其中隊列中隊首到隊尾的元素依次為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。
C
解析　棧中初始有一個值，從索引位置1開始遍歷，當遍歷到的數比棧頂小時，將棧頂元素出棧，自身入棧。遍歷到1時，讓4和6出棧。7入棧，2使得7出棧，8入棧，6使得8出棧，因此棧中有1、2和6共3個元素，top值為2。
C
解析　本題考查棧的性質。棧初始值有一個元素s[0]，從索引位置1開始遍歷s，如果s[i]與棧頂元素相同，進行出棧操作，否則進行入棧操作。A選項棧中元素有BAB，top的值為2。B和D選項棧中元素有ABA，top的值為2。C選項棧中元素有A，top的值為0。
D
解析　本題考查棧的應用。從后往前遍歷列表lst，判斷元素的奇偶性，將偶數入棧、奇數元素往后移動top＋1個位置，其中top＋1是表示棧的元素個數，當前偶數元素個數。再進行出棧操作，覆蓋列表前面的元素。程序執行后，lst元素依次是[6，10，14，16，3，5，7，11]。
解析　入棧必先移動top指針，入棧元素為x，先對x進行除2的余數賦值。
方框處的代碼由以下三個語句組成：①st[top]＝x ②x＝n%2　③top＋＝1下列語句順序正確的是(　　)
A.①②③ B.①③②
C.②①③ D.②③①
D
D
解析　若產生的隨機數m值為0，進行入棧操作。否則出棧后并連接到字符串s中。則于最后一個字符*一旦入棧后，i的值為5，結束循環，就不可能出棧。B選項a比b先入棧，出棧順序應相反。D選項abc先入棧，c出棧，d入棧后出棧，最后a出棧。
解析　遍歷列表s，將每個元素入棧，若當前棧頂元素與ord(″A″)差值為m[j]，則將棧頂元素出棧處理。元素″A″和″B″入棧，″B″與ord(″A″)差值為m[j]為1，″B″出棧，j加1，m[j]值為3，元素″C″和″D″入棧，″D″與ord(″A″)差值為m[j]為3，″D″出棧；j加1，m[j]值為2，棧頂為元素為″C″，″C″出棧，最后″E″入棧。
執行該程序段后，輸出內容是(　　)
A.[] B.['A', 'C']
C.['A', 'E'] D.['A', 'C', 'E']
C
解析　當k的值為0時，進行入棧操作；當k的值為1且棧不為空，進行出棧并替換lst[i]操作。由于i ＋＝ 1操作發生在入棧過程中，因此必須有4個元素出棧，但棧中可能有元素未出棧。A選項當隨機數4次均為0，全部元素均在棧中。C選項隨機數依次為0，1，0，0，有兩個元素在棧中。D選項隨機數依次為0，1，0，1，1，0，A先入棧，出棧后替換B，原B位置上的A再次入棧，最后替換D。B選項當i的值為2時，AB在棧中，應該B先出棧。
執行該程序段后，lst的值不可能是(　　)
A.[ 'A'，'B'，'C'，'D'] B.['A'，'B'，'A'，'C']
C.[ 'A'，'A'，'C'，'D'] D.['A'，'A'，'C'，'A']
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依次入棧。
執行該程序后，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]
B
B
解析　本題考查棧的應用。當棧空入棧，因此3肯定在棧中。當op為0且s[i]>st[top]時，s[i]入棧，若產生op的值一直為1，則棧中只有3；入棧的元素比棧中元素大，2小于3，因此2不可能入棧。由于棧中至少有2個元素時，才要進行替換操作，當op為1，棧中只有一個元素，7沒有入棧，則6可能入棧。
解析　本題主要考查的是棧的基本操作。循環6次，每次先產生一個1到6之間的數num，若num大于等于棧頂，將該數入棧，若num比棧頂元素小且為偶數，將棧頂元素出棧。若棧空，結束程序。A選項產生第一個數，入棧，產生的第二個數比棧頂元素小且為偶數，將棧頂元素出棧，棧空。B選項產生隨機數5，入棧，接著產生2個大于等于5的數，并入棧，再產生2個較小的偶數，讓后面產生的數出棧。C選項一共循環6次，因此不可能是產生了6個數，一個較小偶數讓其中一個數出棧情況，只可能是產生一個比較棧頂小的奇數，如在2后面產生了1，既不入棧，也不出棧。D選項最后一個2不可能入棧。
運行該程序，輸出的結果不可能是(　　)
A.[] B.[5]
C.[2 2 4 5 5] D.[2 3 4 2]
D
解析　本題考查棧的應用。棧空或產生隨機數為1，將a[i]入棧，否則出棧并追加到res中，且語句i＋＝1不執行，因此只有5個元素全部出棧后，程序才終止運行。A選項123入棧，3出棧，則2必須在1的前面出棧。
A
解析　 本題考查棧的基本操作。遍歷tmps列表，若棧為空，將tmps元素的索引值存入棧中。若棧不空且tmps[i]大于tmps[stk[top]](棧頂元素)，計算i －d的值并保存在ans[d]再將當前元素索引入棧 。
執行該程序段后，輸出的結果是(　　)
A.[1, 0, 0, 1] B.[1, 1, 0, 0]
C.[0, 2, 1, 0] D.[0, 1, 2, 0]
C

展開更多......

收起↑