资源简介

课时25　栈
【学业要求】
知识点 学业水平等级
1.能结合生活中的实例,掌握栈的概念、存储结构及特性。 3
2.能结合栈的应用案例,理解栈的入栈和出栈的过程。 4
　　栈作为一种重要的数据结构,在生活中很多应用的实例,他是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。2023年6月卷和2024年6月卷均考查了在栈中元素先进后出的性质。在2023年1月卷中,利用随机函数,用算法模拟了入栈和出栈的过程。
1.(2024年6月浙江选考)栈初始为空,经过一系列入栈、出栈操作后,栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”,则所有可能的出栈序列中,以“旦”结尾的序列个数为(　　)
A.3 B.4
C.5 D.6
答案　C
解析　本题考查栈的性质。“旦”要结尾,“生”必定是入栈后马上出栈。剩下“净末丑”3个元素按先进后出的顺序进行组合,“净”先出栈,有“净末丑、净丑末”2种组合。“末”先出栈,有“末净丑、末丑净”2种组合。“丑”先出栈,“净末”在栈中,只有“丑末净”一种组合,因此共有5种组合。
2.(2023年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.同队列一样,栈也是一种操作受限的线性表,仅允许在表的一端进行数据　　　　或　　　　。
2.进行插入或删除操作的一端称为　　　　,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称为　　　　,位于栈底位置的元素为栈底元素。
3.栈具备“　　　　　　,后进先出”的特点。
4.建立n个元素的空栈st时,需先给分配空间,设置栈顶指针top,相应的语句分别为st=[0]*n;　　　　　　。
5.判断栈st是否空的标志是　　　　。
6.栈st中元素个数为　　　　。
7.入栈也叫压栈操作,把数据元素压入栈顶。与队列(tail指向队尾下一个元素的位置)不同的时,栈顶指针指向栈顶元素,每次入栈时,栈顶指针变量top值　　　　,再给st[top]赋值。
8.出栈时把栈顶元素取出,同时栈顶指针变量top值　　　　。如果栈中没有元素时,即top值为-1时,不能进行出栈操作。
自我校对:1.插入　删除　2.栈顶　栈底　3.先进后出　
4.top=-1　5.top==-1　6.top+1　7.加1　8.减1
【典例1】 栈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
【变式1】 栈s的最大长度为3,初始为空,经过一系列入栈、出栈操作,若元素出栈的顺序是e,c,b,a,d,则可能的入栈序列为(　　)
A.a,b,c,d,e B.a,e,c,b,d
C.e,b,a,c,d D.d,e,a,b,c
答案　B
解析　A选项元素e要出栈,栈的空间至少需要5个长度。B选项元素a入栈,元素e,c,b分别入栈后马上出栈,元素a出栈,元素d入栈后出栈,只需2个空间。C选项元素c出栈时,b,a在栈中,a要先出栈。D选项元素d,e入栈,e出栈,a,b,c入栈,栈的空间至少需要4个。
【典例2】 (2023年1月浙江选考)有后缀表达式“13+2*3+2*”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈顶元素是(　　)
A.21 B.22
C.23 D.24
思维点拨
明考向 本题考查栈和后缀表达式应用
精点拨 将后缀表达式“13+2*3+2*”转换为中缀表达式后为“((1+3)*2+3)*2”,计算结果为22
答案　B
【变式2】 栈S的初始状态为空,元素入栈顺序依次为:z,h,e,j,i,a,n,g,若经过若干进栈和出栈操作后,栈底至栈顶元素依次为:z,a,g,则第4个出栈元素不可能为(　　)
A.h B.e
C.i D.n
答案　D
解析　元素z是第1个入栈且没有出栈,a在栈中,说明h,e,j,i,a经历了入栈且全部出栈,这4个元素均有可能是第4个出栈的,元素n肯定是第5个出栈的。
【典例3】 有如下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,且'#'时要入栈,是字母时,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
【变式3】 有如下Python程序段:
from random import randint
q=["A","B","C","D","E","0"]
head=0;tail=5;top=-1
s=["0"]*5
for i in range(5):
　 t=randint(0,1)　#随机生成 0或1
　 if t==0 and head　　　top+=1; s[top]=q[head]
　 elif t==1 and top!=-1:
　　　s[top]="0"; top-=1
　 head+=1
执行该程序段后,s的值可能是(　　)
A.['B','E','0','0','0']
B.['A','D','0','0','0']
C.['B','D','0','0','0']
D.['A','C','0','0','0']
答案　A
解析　本题考查栈的应用。当随机数为0且队不空时,从队列中取元素入栈;随机数为1且栈不为空时,栈顶元素修改为0且出栈。A选项产生t的值依次为1,0,0,1,0时,元素A不入栈也不出栈,B和C入栈,遍历到D时,C出栈,将s[1]修改为0,最后E入栈。B选项产生前4个t的值依次为0,0,1,0时,可得到[A,D,0,0,0],此时队列和栈均不可能为空,若最后一次操作为入栈,s为[A,D,E,0,0],最后一次操作为出栈,s为[A,0,0,0,0],即栈中要么有1个元素,要么有3个元素。C选项B入栈后,在下一轮循环中,若t为0,则C入栈,若t为1则B出栈,因此元素B和D不可能同时在栈中。D选项同理元素A和C不可能同时在栈中。
　　栈具备“先进后出,后进先出”的特点,当某个元素出栈后,比他先入栈的元素要么在栈中,要么已经出栈。栈也是一种操作受限的线性表,为了减少查询的时间,仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称为栈底,位于栈底位置的元素为栈底元素。与队列(tail指向队尾下一个元素的位置)不同的是,栈顶指针指向栈顶元素,每次入栈时,栈顶指针变量top值加1,再给st[top]赋值。出栈时把栈顶元素取出,同时栈顶指针变量top值减1。如果栈中没有元素时,即top=-1,不能进行出栈操作。
1.栈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入栈,使得这些元素出栈。
2.设栈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个。
3.队列Q从队首到队尾的元素依次为1,2,3,4,5,栈S初始为空。对队列Q中的数据进行操作:队列Q连续出队两次并顺序入栈S,然后栈S出栈一次后再入队Q。重复该操作,过程中若列Q为空则结束。结束后栈S从栈底到栈顶的元素依次为(　　)
A.2,4,1,5,3 B.1,3,5,4,2
C.2,4,5,3,1 D.1,3,5,2,4
答案　B
解析　元素1,2出队后入栈,元素2出栈并入队。元素3,4出队后入栈,元素4出栈并入队。此时队列中有元素5,2,4,栈S从栈底到栈顶的元素1,3。元素5,2出队后入栈,元素2出栈并入队。元素4,2出队后入栈,队列空结束程序。
4.元素30,97,32,75,99入栈的顺序为30,97,32,75,99,如果最先出栈的是32,那么最后出栈的不可能的是(　　)
A.30 B.97
C.75 D.99
答案　B
解析　元素32已出栈,则30,97必定在栈中,因此97肯定比30先出栈。
5.栈S和队列Q的初始状态为空,有d1至d6六个数据,每个数据按照进栈、出栈、入队、出队的顺序操作。已知进栈顺序依次为d1、d2、d3、d4、d5、d6,出队顺序依次为d2、d4、d3、d6、d5、d1,则栈S的大小至少要能存储个数是(　　)
A.2 B.3
C.4 D.5
答案　B
解析　出队顺序与出栈的顺序是一致的。d3是第1个出栈,d4要出栈,栈中有元素d1、d3、d4,需3个空间。
6.队列Q从队首到队尾的元素依次是1,2,3,栈S初始为空。约定:P操作是指Q中1个元素出队后入栈,J操作是指Q中1个元素出队后再入队。经过JPJPP系列操作后,栈S中栈顶到栈底的元素依次为(　　)
A.2,1,3 B.1,3,2
C.3,1,2 D.2,3,1
答案　C
解析　元素1出队后入队,元素2出队后入栈,元素3出队后入队,因此1和3依次入栈。
7.有如下Python程序段:
from random import randint
st=[""]*4;ys="ABCD";cz=[1,1,1,1]
x=randint(0,3)　#随机生成0、1、2、3
cz[x]=0
top=-1;pos=0
for i in range(len(cz)):
　 if cz[i]==0 and top>-1:
　　　top=top-1
　 elif cz[i]==1:
　　　top=top+1;st[top]=ys[pos]
　　　pos=pos+1
print(st[:top+1])
执行该程序段后,输出结果不可能的是(　　)
A.['A','B'] B.['B','D']
C.['B','C'] D.['A','B','C']
答案　B
解析　若产生x的值为0,没有出栈,入栈'A','B','C'共3个元素。产生x值为1,'A'入栈再出栈,接着入栈'B'和'C'共['B','C']2个元素。产生x值为2,'A'和'B'入栈,'B'出栈,'C'入栈,共['A','C']2个元素。产生x值为3,'A','B','C'入栈,'C'出栈,共['A','B']2个元素。
8.有如下程序段:
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"入栈。
9.有如下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
答案　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]。
1.栈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入栈。
2.用“除二取余”法将十进制转换为二进制数,用栈的方法操作,需要把得到的余数依次入栈,除尽后再把余数出栈即可。若要将十进制数n(0≤n<64)转换为二进制数,则设置栈的长度至少为(　　)
A.3 B.4
C.5 D.6
答案　D
解析　十进制数 n(0≤n<64)转换为二进制数,得到最大的是 6 位二进制数。
3.栈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出栈。
4.栈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个。
5.队列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入栈并出栈。
6.有一个空栈,若元素入栈的顺序是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个出栈的,也可能是最后一个出栈的。
7.元素A,B,C,D,E,F按序入栈,在所有出栈序列中(元素需全部出栈),以元素E开头且以元素A结尾的出栈序列的数量有(　　)
A.3 B.4
C.5 D.6
答案　B
解析　E出栈时,栈内有元素A、B、C、D。元素A必须最后出栈,出栈序列可能为:EFDCBA、EDFCBA、EDCFBA、EDCBFA。
8.利用栈求逆波兰表达式的方法:从左往右扫描该表达式,遇到数字时入栈;遇到运算符号时,把处于栈上方的两个元素依次出栈,用运算符计算,并把结果压入栈中。如此反复操作,直至表达式扫描结束。使用该算法求表达式“372-+4*8/”的值时,所使用的栈容量至少为(　　)
A.2 B.3
C.4 D.5
答案　B
解析　数字3,7,2入栈,需3个空间。7-2的值为5,入栈,3+5的值为8入栈,此时栈中只有1个元素。8*4的值为32,32再除8,得到结果为4。
9.有如下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出栈。
10.有如下Python程序:
stackA=[0]*6
stackB=[0]*6
topA=topB=-1
d=[5,9,4,8,7,2]
for i in range(len(d)):
　 while topA!=-1 and d[i]　　　topB+=1
　　　stackB[topB]=stackA[topA]
　　　topA-=1
　 topA+=1; stackA[topA]=d[i]
程序执行过程中,变量topB的最大值为(　　)
A.2 B.3
C.4 D.5
答案　C
解析　遍历数组d,若栈stackA不空,且d[i]小于stackA[topA],则让stackA[topA]出栈并入栈stackB。5和9入栈stackA,4让5和9出栈并入栈stackB,8入栈stackA,7让8出栈并入栈stackB,2让7,4出栈并入栈stackB,栈stackB中共有5个元素,因此topB的最大值为4。
11.有如下 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
答案　A
解析　程序首先建立两个长度为10的列表s与q,将a[0]入队。从索引位1开始向后遍历列表a,将s列表小于a[i]的值出栈,加入队列q中。输出队列q中的元素,输出23124。
12.已知字符“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"出队和出栈。
13.(2026年1月浙江选考)有如下 Python 程序段:
s=0
while topa!=-1:
　　while topb!=-1 and stka[topa]>stkb[topb]:
　　　　if (stka[topa]+stkb[topb])%2==1:
　　　　　　topa+=1
　　　　　　stka[topa] = stkb[topb]
　　　　topb-=1
　　if topb!=-1:
　　　　topb-=1
　　s+=stka[topa]
　　topa-=1
若stka为[6,0,0,0,0,0],topa为0,stkb为[2,7,2,1,5],topb为4,执行该程序段后,s的值为 (　　)
A.13 B.14
C.15 D.16
答案　C
解析　本题考查栈的算法实现。栈stka初始有一个元素6,栈stkb初始有5个元素。内循环的条件是栈stkb不为空且栈stka的栈顶元素大于栈stkb的栈顶元素,若两个栈顶元素之和为奇数,将栈stkb的栈顶元素入栈stka,栈stkb始终出栈一个元素。将栈stka栈顶元素累加到变量s中,两个栈各出栈一个元素,直到栈stka为空,结束循环。6大于5且两数之和为奇数,5从stkb出栈并入栈到stka。5大于1且两数之和为偶数,元素1直接出栈。5大于2且两数之和为奇数,2从stkb出栈并入栈到stka。2小于7,结束内循环,s累加值为2,两个栈各出栈一个元素,栈中元素依次为[6,5]和[2]。5大于2且两数之和为奇数,2从stkb出栈并入栈到stka,栈stkb为空,将栈stka中的元素[6,5,2]依次累加到s中并出栈,栈stka为空,结束循环。
14.有如下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
执行该程序段后,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,A先入栈,出栈后替换B,原B位置上的A再次入栈,最后替换D。B选项当i的值为2时,AB在栈中,应该B先出栈。(共58张PPT)
选修一　数据与数据结构
课时25　栈
知识点 学业水平等级
1.能结合生活中的实例,掌握栈的概念、存储结构及特性。 3
2.能结合栈的应用案例,理解栈的入栈和出栈的过程。 4
目 录
CONTENTS
真题剖析
01
知识梳理
02
课堂突破
03
当堂检测
04
课后作业
05
真题剖析
1
　　栈作为一种重要的数据结构,在生活中很多应用的实例,他是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。2023年6月卷和2024年6月卷均考查了在栈中元素先进后出的性质。在2023年1月卷中,利用随机函数,用算法模拟了入栈和出栈的过程。
1.(2024年6月浙江选考)栈初始为空,经过一系列入栈、出栈操作后,栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”,则所有可能的出栈序列中,以“旦”结尾的序列个数为(　　)
A.3 B.4
C.5 D.6
解析　本题考查栈的性质。“旦”要结尾,“生”必定是入栈后马上出栈。剩下“净末丑”3个元素按先进后出的顺序进行组合,“净”先出栈,有“净末丑、净丑末”2种组合。“末”先出栈,有“末净丑、末丑净”2种组合。“丑”先出栈,“净末”在栈中,只有“丑末净”一种组合,因此共有5种组合。
C
2.(2023年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
知识梳理
2
1.同队列一样,栈也是一种操作受限的线性表,仅允许在表的一端进行数据
　　　　或　　　　。
2.进行插入或删除操作的一端称为　　　　,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称为　　　　,位于栈底位置的元素为栈底元素。
3.栈具备“　　　　　　,后进先出”的特点。
4.建立n个元素的空栈st时,需先给分配空间,设置栈顶指针top,相应的语句分别为st=[0]*n;　　　　　　。
5.判断栈st是否空的标志是　　　　。
插入
删除
栈顶
栈底
先进后出
top=-1
top==-1
6.栈st中元素个数为　　　　。
7.入栈也叫压栈操作,把数据元素压入栈顶。与队列(tail指向队尾下一个元素的位置)不同的时,栈顶指针指向栈顶元素,每次入栈时,栈顶指针变量top值　　　　,再给st[top]赋值。
8.出栈时把栈顶元素取出,同时栈顶指针变量top值　　　　。如果栈中没有元素时,即top值为-1时,不能进行出栈操作。
top+1
加1
减1
课堂突破
3
【典例1】 栈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入队
【变式1】 栈s的最大长度为3,初始为空,经过一系列入栈、出栈操作,若元素出栈的顺序是e,c,b,a,d,则可能的入栈序列为(　　)
A.a,b,c,d,e B.a,e,c,b,d
C.e,b,a,c,d D.d,e,a,b,c
解析　A选项元素e要出栈,栈的空间至少需要5个长度。B选项元素a入栈,元素e,c,b分别入栈后马上出栈,元素a出栈,元素d入栈后出栈,只需2个空间。C选项元素c出栈时,b,a在栈中,a要先出栈。D选项元素d,e入栈,e出栈,a,b,c入栈,栈的空间至少需要4个。
B
【典例2】 (2023年1月浙江选考)有后缀表达式“13+2*3+2*”,现利用栈计算该表达式:从左向右扫描,遇到数字时,数字入栈;遇到运算符时,两个元素出栈,用运算符计算,所得结果入栈,如此反复操作,直到扫描结束,栈顶元素是(　　)
A.21 B.22
C.23 D.24
答案　B
思维点拨
明考向 本题考查栈和后缀表达式应用
精点拨 将后缀表达式“13+2*3+2*”转换为中缀表达式后为“((1+3)*2+3)*2”,计算结果为22
解析　元素z是第1个入栈且没有出栈,a在栈中,说明h,e,j,i,a经历了入栈且全部出栈,这4个元素均有可能是第4个出栈的,元素n肯定是第5个出栈的。
D
【典例3】 有如下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
答案　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】 有如下Python程序段:
from random import randint
q=["A","B","C","D","E","0"]
head=0;tail=5;top=-1
s=["0"]*5
for i in range(5):
　 t=randint(0,1)　#随机生成 0或1
　 if t==0 and head　　　top+=1; s[top]=q[head]
　 elif t==1 and top!=-1:
　　　s[top]="0"; top-=1
　 head+=1
执行该程序段后,s的值可能是(　　)
A.['B','E','0','0','0'] B.['A','D','0','0','0']
C.['B','D','0','0','0'] D.['A','C','0','0','0']
解析　本题考查栈的应用。当随机数为0且队不空时,从队列中取元素入栈;随机数为1且栈不为空时,栈顶元素修改为0且出栈。A选项产生t的值依次为1,0,0,1,0时,元素A不入栈也不出栈,B和C入栈,遍历到D时,C出栈,将s[1]修改为0,最后E入栈。B选项产生前4个t的值依次为0,0,1,0时,可得到[A,D,0,0,0],此时队列和栈均不可能为空,若最后一次操作为入栈,s为[A,D,E,0,0],最后一次操作为出栈,s为[A,0,0,0,0],即栈中要么有1个元素,要么有3个元素。C选项B入栈后,在下一轮循环中,若t为0,则C入栈,若t为1则B出栈,因此元素B和D不可能同时在栈中。D选项同理元素A和C不可能同时在栈中。
A
　　栈具备“先进后出,后进先出”的特点,当某个元素出栈后,比他先入栈的元素要么在栈中,要么已经出栈。栈也是一种操作受限的线性表,为了减少查询的时间,仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称为栈底,位于栈底位置的元素为栈底元素。与队列(tail指向队尾下一个元素的位置)不同的是,栈顶指针指向栈顶元素,每次入栈时,栈顶指针变量top值加1,再给st[top]赋值。出栈时把栈顶元素取出,同时栈顶指针变量top值减1。如果栈中没有元素时,即top=-1,不能进行出栈操作。
当堂检测
4
1.栈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入栈,使得这些元素出栈。
2.设栈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个。
3.队列Q从队首到队尾的元素依次为1,2,3,4,5,栈S初始为空。对队列Q中的数据进行操作:队列Q连续出队两次并顺序入栈S,然后栈S出栈一次后再入队Q。重复该操作,过程中若列Q为空则结束。结束后栈S从栈底到栈顶的元素依次为(　　)
A.2,4,1,5,3 B.1,3,5,4,2
C.2,4,5,3,1 D.1,3,5,2,4
B
解析　元素1,2出队后入栈,元素2出栈并入队。元素3,4出队后入栈,元素4出栈并入队。此时队列中有元素5,2,4,栈S从栈底到栈顶的元素1,3。元素5,2出队后入栈,元素2出栈并入队。元素4,2出队后入栈,队列空结束程序。
B
解析　元素32已出栈,则30,97必定在栈中,因此97肯定比30先出栈。
5.栈S和队列Q的初始状态为空,有d1至d6六个数据,每个数据按照进栈、出栈、入队、出队的顺序操作。已知进栈顺序依次为d1、d2、d3、d4、d5、d6,出队顺序依次为d2、d4、d3、d6、d5、d1,则栈S的大小至少要能存储个数是(　　)
A.2　　　　　　B.3　　　　　　C.4　　　　　　D.5
B
解析　出队顺序与出栈的顺序是一致的。d3是第1个出栈,d4要出栈,栈中有元素d1、d3、d4,需3个空间。
6.队列Q从队首到队尾的元素依次是1,2,3,栈S初始为空。约定:P操作是指Q中1个元素出队后入栈,J操作是指Q中1个元素出队后再入队。经过JPJPP系列操作后,栈S中栈顶到栈底的元素依次为(　　)
A.2,1,3 B.1,3,2
C.3,1,2 D.2,3,1
C
解析　元素1出队后入队,元素2出队后入栈,元素3出队后入队,因此1和3依次入栈。
7.有如下Python程序段:
from random import randint
st=[""]*4;ys="ABCD";cz=[1,1,1,1]
x=randint(0,3)　#随机生成0、1、2、3
cz[x]=0
top=-1;pos=0
for i in range(len(cz)):
　 if cz[i]==0 and top>-1:
　　　top=top-1
　 elif cz[i]==1:
　　　top=top+1;st[top]=ys[pos]
　　　pos=pos+1
print(st[:top+1])
B
解析　若产生x的值为0,没有出栈,入栈'A','B','C'共3个元素。产生x值为1,'A'入栈再出栈,接着入栈'B'和'C'共['B','C']2个元素。产生x值为2,'A'和'B'入栈,'B'出栈,'C'入栈,共['A','C']2个元素。产生x值为3,'A','B','C'入栈,'C'出栈,共['A','B']2个元素。
8.有如下程序段:
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"入栈。
9.有如下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中数据,若栈s1不空,且s1栈顶元素大于等于a[i]时,不断地将s1中元素出栈,并入栈s2中,将a[i]入栈s1。因此栈s1中元素有1,3,栈s2中有元素[2,7,5],最后将栈s2中元素出栈并加入栈s1中,因此栈s1中最终结果为[1,3,5,7,2]。
课时作业
5
1.栈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入栈。
2.用“除二取余”法将十进制转换为二进制数,用栈的方法操作,需要把得到的余数依次入栈,除尽后再把余数出栈即可。若要将十进制数n(0≤n<64)转换为二进制数,则设置栈的长度至少为(　　)
A.3 B.4
C.5 D.6
D
解析　十进制数 n(0≤n<64)转换为二进制数,得到最大的是 6 位二进制数。
3.栈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出栈。
4.栈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个。
5.队列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入栈并出栈。
6.有一个空栈,若元素入栈的顺序是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个出栈的,也可能是最后一个出栈的。
7.元素A,B,C,D,E,F按序入栈,在所有出栈序列中(元素需全部出栈),以元素E开头且以元素A结尾的出栈序列的数量有(　　)
A.3 B.4
C.5 D.6
B
解析　E出栈时,栈内有元素A、B、C、D。元素A必须最后出栈,出栈序列可能为:EFDCBA、EDFCBA、EDCFBA、EDCBFA。
8.利用栈求逆波兰表达式的方法:从左往右扫描该表达式,遇到数字时入栈;遇到运算符号时,把处于栈上方的两个元素依次出栈,用运算符计算,并把结果压入栈中。如此反复操作,直至表达式扫描结束。使用该算法求表达式“372-+4*8/”的值时,所使用的栈容量至少为(　　)
A.2　　　　　　　　B.3　　　　　　　　C.4　　　　　　　　D.5
B
解析　数字3,7,2入栈,需3个空间。7-2的值为5,入栈,3+5的值为8入栈,此时栈中只有1个元素。8*4的值为32,32再除8,得到结果为4。
9.有如下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出栈。
10.有如下Python程序:
stackA=[0]*6
stackB=[0]*6
topA=topB=-1
d=[5,9,4,8,7,2]
for i in range(len(d)):
　 while topA!=-1 and d[i]　　　topB+=1
　　　stackB[topB]=stackA[topA]
　　　topA-=1
　 topA+=1; stackA[topA]=d[i]
程序执行过程中,变量topB的最大值为(　　)
A.2 B.3
C.4 D.5
C
解析　遍历数组d,若栈stackA不空,且d[i]小于stackA[topA],则让stackA[topA]出栈并入栈stackB。5和9入栈stackA,4让5和9出栈并入栈stackB,8入栈stackA,7让8出栈并入栈stackB,2让7,4出栈并入栈stackB,栈stackB中共有5个元素,因此topB的最大值为4。
11.有如下 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
A
解析　程序首先建立两个长度为10的列表s与q,将a[0]入队。从索引位1开始向后遍历列表a,将s列表小于a[i]的值出栈,加入队列q中。输出队列q中的元素,输出23124。
12.已知字符“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"出队和出栈。
11.(2026年1月浙江选考)有如下 Python 程序段:
s=0
while topa!=-1:
　　while topb!=-1 and stka[topa]>stkb[topb]:
　　　　if (stka[topa]+stkb[topb])%2==1:
　　　　　　topa+=1
　　　　　　stka[topa] = stkb[topb]
　　　　topb-=1
　　if topb!=-1:
　　　　topb-=1
　　s+=stka[topa]
　　topa-=1
若stka为[6,0,0,0,0,0],topa为0,stkb为[2,7,2,1,5],topb为4,执行该程序段后,s的值为(　　)
A.13　　　　　　　　B.14　　　　　　　　C.15　　　　　　　　D.16
C
解析　本题考查栈的算法实现。栈stka初始有一个元素6,栈stkb初始有5个元素。内循环的条件是栈stkb不为空且栈stka的栈顶元素大于栈stkb的栈顶元素,若两个栈顶元素之和为奇数,将栈stkb的栈顶元素入栈stka,栈stkb始终出栈一个元素。将栈stka栈顶元素累加到变量s中,两个栈各出栈一个元素,直到栈stka为空,结束循环。6大于5且两数之和为奇数,5从stkb出栈并入栈到stka。5大于1且两数之和为偶数,元素1直接出栈。5大于2且两数之和为奇数,2从stkb出栈并入栈到stka。2小于7,结束内循环,s累加值为2,两个栈各出栈一个元素,栈中元素依次为[6,5]和[2]。5大于2且两数之和为奇数,2从stkb出栈并入栈到stka,栈stkb为空,将栈stka中的元素[6,5,2]依次累加到s中并出栈,栈stka为空,结束循环。
14.有如下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
解析　当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先出栈。

展开更多......

收起↑