资源简介
专题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
展开更多......
收起↑
