资源简介

专题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种情况。]

展开更多......

收起↑