资源简介

(共64张PPT)
课时25 栈
一、栈的概念
1. 栈是“　　　　”的线性表，仅允许在表的一端进行插入或删除操作。
2. 在栈中，进行插入或删除的一端称为　　　　，位于栈顶位置的元素称为栈顶元素；表的另一端称为　　　　，位于栈底位置的元素称为栈底元素。栈结构如图所示。
后进先出　
栈底
栈顶
1. 先进后出、后进先出。最后入栈的元素　　　　出栈，最先入栈的元素最后出栈。
2. 有限序列性。
（1）栈中的元素是有限的。栈可以是空的，也可以包含多个元素。
（2）栈中元素呈线性关系，栈顶元素有一个　　　　，栈底元素有一个　　　　，其他元素既有一个前驱点，又有一个后继点。
最先
前驱点
二、栈的特性
后继点
1. 栈的数组存储。
栈一般按顺序结构存储，可以用数组实现。当对栈进行操作时，栈顶元素在数组中的位置会发生改变，因此使用一个栈顶指针变量 top 来记录　　　　元素在数组中的位置。
三、栈的基本操作
栈顶
2. 栈的链式存储。
（1）利用链式存储方式实现的栈称为　　　　，可以用单向链表实现。栈顶指针 top 为链栈的　　　　head，head 指向第一个节点。
（2）链栈的优点：克服了用数组实现的顺序栈　　　　利用率不高的缺点。
（3）链栈的不足：要为每个栈元素分配额外的指针空间。
链栈
头指针
空间
3.建栈。
（1）可以利用 Python 的列表结构建栈。当栈为空栈时，列表元素初始值设为空，指针 top 值为-1。代码实现如下。
st=[""]*5 #创建一个长度为 5 的栈
top=-1 #表示目前栈中没有元素，为空栈
（2）利用 Python 列表创建一个链栈的代码如下，从栈底到栈顶的元素顺序与链表相反。
st=[[7,3],[4,2],[3,4],[2,1],[8,-1]]
head=0 #链表为 7→2→4→3→8
top=0 #链栈从栈底到栈顶的元素依次为 8，3，4，2，7
4.入栈、出栈。
（1）入栈。
①入栈又叫　　　　操作，把数据元素压入栈顶。每次入栈时，栈顶指针变量 top 值　　　　。
压栈
加 1
②Python 代码实现入栈。
st=[""]*5 #初始化栈
top=-1 #初始化栈顶指针
top+=1 #栈顶指针前移
st[top]="A" #字母 A 入栈
top+=1
st[top]="B" #字母 B 入栈
top+=1
st[top]="C" #字母 C 入栈
（2）出栈。
①出栈时把　　　　 元素取出，同时 top 值　　　　。若栈为空，即 top=-1，不能进行出栈操作。
②Python 代码实现出栈。
st=["T","B","V","C"]
top=3
top-=1 #字母 C 出栈
top-=1 #字母 V 出栈
栈顶
减 1
（3）Python 代码实现用列表自带的函数与方法实现出栈和入栈。
st=[] #建立空列表表示空栈
st.append("A") #字母 A 入栈
st.append("B") #字母 B 入栈
print(st[-1]) #输出栈顶元素，为字母 B
print(len(st)) #输出栈中元素个数，为 2
st.pop() #栈顶元素出栈
print(st[-1]) #输出栈顶元素，为字母 A
典例 1 下列场景适合用栈描述的是 （　　）
A.根据学生的成绩排名依次安排座位
B.医院签到叫号系统
C.浏览器的“返回上一层”功能
D.某次学校大型表演方阵的排列顺序
C
√
题型导向一　栈的概念与特性
胜券点拨1
明考向 本题主要考查栈的概念
审关键 对实际场景的特点进行抽象、明确栈结构的特点是“先进后出，后进先出”
考场思维快闪 A 座位依次排列不存在入栈和出栈的过程，没有体现栈的“先进后出”的特点
B 先到达的人会先被叫号，这样的结构类似于队列的“先进先出”
C 浏览器的“返回上一层”功能中，首先返回的是最后一次浏览的网页，再返回的是再上一次浏览的网页，最先浏览的网页最后才能被“返回”，符合栈“先进后出，后进先出”的特点
D 表演方阵不存在入栈和出栈的过程，不具备栈结构的特点
典例 2 元素 A，C，D，G，K，L，M 依次入栈，则出栈序列不可能是 （　　）
A.C，D，K，G，A，M，L
B.G，D，A，C，L，M，K
C.A，K，G，L，D，M，C
D.G，D，L，K，C，A，M
B
√
胜券点拨2
明考向 本题主要考查栈的特性
审关键 栈中只有栈顶元素能出栈，入栈的元素逐个压在栈底
考场思维快闪 A A、C入栈，C出栈；D入栈，D出栈；G、K入栈，K、G出栈；A出栈；L、M入栈，M、L出栈
B A、C、D、G入栈，G、D出栈；此时栈顶元素为C，只能C或者是后续的K、L、M中任意一个出栈，故D之后出栈的元素不可能是A
C A入栈，A出栈；C、D、G、K入栈，K、G出栈；L入栈，L出栈；D出栈；M入栈，M出栈；C出栈
D A、C、D、G入栈，G、D出栈；K、L入栈，L、K出栈；C出栈；A出栈；M入栈，M出栈
典例 3 ［2023.6 浙江选考］栈 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
√
题型导向二　栈的基本操作
胜券点拨3
明考向 本题主要考查栈的操作
审关键 栈的特性
考场思维快闪 A 若f先出栈，则需要a，b，c，d，e，f都入栈，由于栈s最大长度为3，不可能全部入栈，所以不符
B 若出栈序列为c，b，a，f，e，d，则入栈出栈过程是：a、b、c入栈，c、b、a出栈，d、e、f入栈，f、e、d出栈
C 若出栈序列为c，a，b，d，e，f，则入栈出栈过程是：a、b、c入栈，c出栈，a在b前入栈，根据栈“先进后出”的特性，a会在b后面出栈，所以不符
D 若出栈序列为c，e，d，b，a，f，则入栈出栈过程是：a、b、c入栈，c出栈，d入栈，e在d前出栈，e就需要入栈，但此时栈s已经有3个元素，无法入栈，所以不符
典例 4 ［2024.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
√
胜券点拨4
明考向 本题主要考查队列和栈的操作
审关键 队列和栈的特性
考场思维快闪 根据栈“先进后出”、队列“先进先出”的原理可知，第一个U操作将3出栈S、入队Q，栈S为1,2，队列Q为3；第二个U操作将2出栈S、入队Q，栈S为1，队列Q为3,2；H操作将3出队Q、入队Q，队列Q为2,3；第三个U操作将1出栈S、入队Q，队列Q为2,3,1
典例 5 ［2024.6 浙江选考］栈初始为空，经过一系列入栈、出栈操作后，栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”，则所有可能的出栈序列中，以“旦”结尾的序列个数为（　　）
A.3
B.4
C.5
D.6
C
√
胜券点拨5
明考向 本题主要考查栈的操作
审关键 栈的入栈和出栈
考场思 维快闪 根据栈“先进后出”的特点，若“旦”是最后一个出栈，则“生”一定是第一个出栈。所有可能的出栈序列有5种：“生”“净”“末”“丑”“旦”；“生”“净”“丑”“末”“旦”；“生”“末”“净”“丑”“旦”；“生”“末”“丑”“净”“旦”；“生”“丑”“末”“净”“旦”
典例 6 ［2025.1 浙江选考］有后缀表达式“1 3 + 2 * 3 + 2 *”，现利用栈计算该表达式：从左向右扫描，遇到数字时，数字入栈；遇到运算符时，两个元素出栈，用运算符计算，所得结果入栈。如此反复操作，直到扫描结束，栈顶元素是 （　　）
A.21
B.22
C.23
D.24
B
√
胜券点拨6
明考向 本题主要考查栈与后缀表达式
审关键 栈顶元素与后缀表达式计算结果的关系
考场思 维快闪 将后缀表达式“1 3 + 2 * 3 + 2 *”转换成中缀表达式为“((1+3)*2+3)*2”，计算结果为22，即栈顶元素
典例 7 ［2023.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','#']
D
√
题型导向三　栈的Python实现
胜券点拨7
明考向 本题主要考查栈的Python实现，栈中数据的操作特点
审关键 栈中的数据遵循先进后出的原则
代码 分析 变量op决定对列表a进行的操作；循环中的两段分支分别是：当op值为1，且a[i]不为"#"时将a[i]入栈并将a[i]值置为"#"；当op值为0且栈不为空且a[i]值为"#"时，将a[i]赋值为栈顶元素并将栈顶元素出栈
考场思维快闪 A 跟原来相比没变化，若op的值都为0，则有可能
B a中的元素都为"#"，若op的值都为1，则有可能
C a[0]="#"，说明"A"入栈，a[1]～a[5]无变化；a[6]= "A"，a[6]的原值是"#"，说明进行出栈操作，栈顶元素"A"赋值给a[6]
D a[0]="#"，说明"A"入栈；a[1]="#"，说明"B"也入栈；a[2]="A"，说明此时op=0，a[2]的值应为栈顶元素"B"而不是"A"
else:
　　　（2）　　　1
ans+=　　　（3）　　　1
画线处有如下可选代码：
①top!=-1 ②top==-1 ③top+=1 ④top-=1
⑤top//2 ⑥(top+1)//2
画线处依次应填入的正确代码为 （　　）
A.①③⑥ B.①④⑤
C.②④⑤ D.②④⑥
典例 8 ［2025 台州模拟］某括号序列中，若左括号出现的顺序及个数与右括号保持一致，则称该序列中的括号是匹配的。例如，序列“())(”中的括号是不匹配的，可将其中第 3、4 个括号修改为“(”“)”使其重新匹配。现给出一个长度为偶数的不匹配序列，为使其重新匹配，统计最少需要修改的括号数。实现上述功能的 Python 程序如下：
#输入括号序列，序列中仅包含"("和")"两种字符
s=input()
top=-1
ans=0
for i in range(len(s)):
if s[i]=="(":
top+=1
else:
if 　　　（1）　　　:
top+=1
ans+=1
D
√
胜券点拨8
明考向 本题主要考查栈的Python实现
审关键 括号匹配
考场思 维快闪 当遍历到左括号时，左括号入栈（top+=1）；当遍历到右括号时，若栈为空（top==-1），即没有左括号与其配对，就需要将当前右括号修改成左括号，再入栈左括号，修改的括号数累加1（ans+=1），否则出栈左括号（top-=1），表示与当前右括号匹配。最后，将栈中剩余左括号中的一半修改为右括号，修改的括号数累加(top+1)//2（ans+=(top+1)//2）
典例 9 用 Python 列表自带的函数和方法来模拟栈，代码如下：
import random
a=[1,2,3,4,5]
stack=[a[0]]
i=1;res=[]
while iif random.randint(0,1)==0 or len(stack)==0:
stack.append(a[i])
else:
res.append(stack.pop())
i-=1
i+=1
while len(stack)>0:
res.append(stack.pop())
print(res)
执行该程序段后，输出的结果不可能是 （　　）
A.[1,2,3,4,5] B.[2,1,4,3,5]
C.[1,5,4,3,2] D.[1,4,2,3,5]
D
√
胜券点拨9
明考向 本题主要考查栈的Python实现
审关键 Python列表自带的函数和方法
考场思维快闪 初始栈stack中有一个元素a[0]，while循环遍历列表a中的元素，若random.randint(0,1)的值为0或栈stack为空，则入栈a[i]，否则出栈栈顶元素，并添加到列表res中。循环结束后，若栈stack中还有元素，则依次出栈并添加到列表res中，故res的值即列表a中元素依次入栈对应的出栈的顺序。选项D中1先入栈，接着2，3，4依次入栈，4出栈，此时栈顶元素为3，不可能2先出栈
数据结构类型 结构特性 操作特性
队列 先进先出，后进后出 只允许在队尾进行插入操作，只允许在队首进行删除操作
栈 先进后出，后进先出 只允许在栈顶进行插入和删除操作，栈底不允许进行任何操作
通法一　队列与栈的辨析
1.原则：要出栈必先入栈，只能将栈顶元素出栈。
2.若有序列 A，B，C，D，E，F，G 依次入栈，判断可能的出栈序列。
（1）若先出栈的元素是 C，说明 A、B、C 均已入栈，如图所示，下划线表示已经入栈的元素，圆圈表示本次出栈的元素。
（2）此时栈顶元素为 B，B 为下一次出栈的候选元素，同时 C 后面尚未入栈的元素 D、E、F、G 也是下一次出栈的候选元素。
通法二　出栈序列的判断
（3）无论下一次出栈的是 D、E、F、G 中的哪个元素，该元素及其左边的所有元素肯定都已经入栈。例如，若下一次出栈的元素是 F，则此时的栈顶元素是 E，那么下一次出栈的元素只能是 E 或是尚未入栈的 G。
（4）判断方法总结。
①先确定入栈的顺序。
②一个元素出栈后，下一个出栈的元素只能是入栈序列中其左边相邻的未出栈元素，或其右边的任一元素。
实现方式 普通列表实现 列表自带的函数与方法实现
建栈 st=[0]*n　#创建长度为n的空栈 top=-1　#栈中无元素，栈顶指针指向-1 st=[]　#创建空栈
top=len(st)-1　#栈顶元素即列表末尾元素
入栈 #有元素入栈，栈顶指针先后移 top+=1 #修改栈顶元素为新元素A st[top]="A" '''直接使用append()方法在列表末尾添加元素，不用修改栈顶指针'''
st.append("A")
出栈 '''直接将栈顶指针前移一位，表示已经出栈的元素不在栈中''' top-=1 #直接使用pop()方法删除列表末尾元素表示出栈
st.pop()
获取栈中 元素个数 '''列表下标第一位从0开始，0～top是栈中所有的元素，故top+1的值即是元素的个数''' print(top+1) print(len(st))　#栈即列表
通法三　编程实现栈结构的重点
1.十进制数转换为二进制数。
st=[-1]*100
top=-1
number=int(input("请输入十进制数："))
while number>0:
x=number%2
top=top+1
st[top]=x #入栈
number=number//2
while top>=0:
print(st[top],end="") #出栈
top=top-1
通法四　栈的应用实例
2.括号匹配。
st=[""]*100
top=-1
flag=True #标记是否有不匹配的情况
s=input("请输入数学计算式：")
for i in range(len(s)):
if s[i]=="(": #遇到左括号时，入栈左括号
top=top+1
st[top]=s[i]
elif s[i]==")": #遇到右括号时
if top==-1: #若栈为空，则不匹配
flag=False
break
else: #出栈栈顶的左括号
top=top-1
if top>=0: #若栈中还有括号，则不匹配
flag=False
if flag:
print("括号匹配")
else:
print("括号不匹配")
3.逆波兰表达式。
（1）在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性，这种表达式称为中缀表达式。为了程序实现的方便，将运算符置于其运算对象之后，没有括号，不用考虑运算符号的优先性，这种表达式称为后缀表达式，又叫逆波兰表达式。如表达式“6 8 2 - 2 * 3 / +”是“6+(8-2)*2/3”的逆波兰表达式。
（2）Python 编程实现逆波兰表达式的计算。
st=[0]*100
top=-1
s=input("请输入逆波兰表达式：")
i=0
while iif "0"<=s[i]<="9": #遇到数字字符
#入栈
top+=1
st[top]=int(s[i])
elif s[i] in "+-*/": #遇到运算符
#依次出栈两个元素
x=st[top]
top-=1
y=st[top]
top-=1
#计算结果并入栈
if s[i]=="+":
top+=1
st[top]=y+x
elif s[i]=="-":
top+=1
st[top]=y-x
elif s[i]=="*":
top+=1
st[top]=y*x
elif s[i]=="/":
top+=1
st[top]=int(y/x)
i=i+1
print(st[top]) #输出运算结果
（3）Python 编程实现中缀表达式转换为后缀表达式。
#将输入字符串按空格分割，存储在列表中
s=input("请输入中缀表达式（用空格分隔）：").split()
st=[""]*10
top=-1
res=""
#运算符优先级，此处只考虑四则运算
ops={"+":1,"-":1,"*":2,"/":2}
for i in s:
#若为数字字符，则直接添加到结果 res 中
if "0"<=i<="9":
res+=i
elif i in ops: #若为运算符，则从栈顶开始让优先级大于等于该运算符的元素出栈
while top!=-1 and st[top]!="(" and ops[st[top]]>=ops[i]:
res+=st[top]
top-=1
top+=1;st[top]=i #当前运算符入栈
elif i=="(": #若为左括号，则让左括号入栈
top+=1
st[top]=i
elif i==")": #若为右括号，则从栈顶开始出栈，直到匹配到左括号
while top!=-1 and st[top]!="(":
res+=st[top]
top-=1
top-=1 #左括号也出栈，但不用输出
while top!=-1: #栈中剩余元素出栈
res+=st[top]
top-=1
print(res)
1.下列关于栈的说法，正确的是 （　　）
A.栈中的元素从栈底入栈
B.栈不可以为空
C.在栈中只能删除栈顶元素
D.数据序列的出栈顺序就是逆序的入栈顺序
栈中的元素从栈顶入栈。栈可以是空栈，没有元素的栈即为空栈。栈中元素的出栈序列不一定是逆序的入栈序列，比如可能先入栈两个元素，出栈一个元素，再入栈其他元素，穿插进行操作时，元素的出栈顺序不确定。
一、栈的概念与特性
C
√
2.某个栈的示意图如图所示，将栈中所有数据出栈，则出栈序列是 （　　）
A.Q-O-P-E-G-C-A
B.A-C-G-E-P-O-Q
C.E-P-O-Q-G-C-A
D.A-C-G-Q-O-P-E
栈中的元素只能从栈顶出栈。所以出栈的序列应是从栈顶到栈底的顺序。
D
√
3.某序列的入栈顺序为1，2，3，4，5，6，若4第一个出栈，则下列出栈序列中不可能的是 （　　）
A.4，3，5，2，6，1
B.4，6，5，3，2，1
C.4，2，3，1，5，6
D.4，5，3，6，2，1
C
√
若4第一个出栈，则此时栈中元素依次为1，2，3。下一个出栈的可能是还未入栈的5或6，也可能是栈顶元素3。选项C中，2不可能在3之前出栈。
4.已知一个栈的入栈序列是1，2，3，4，5，出栈序列为s1，s2，s3，s4，s5。若s2为3，则s1不可能为 （　　）
A.1
B.2
C.4
D.5
D
√
若s2为3，则表示3是第2个出栈的。第1个出栈的可能是1或2（先于3入栈），也可能是4（在3后面一个入栈）。不可能是5，因为如果5第1个出栈，第2个出栈的一定是4。
5.［2025浙江联考］用s表示入栈操作，用x表示出栈操作，若元素的入栈顺序是abcd，为了得到acdb的出栈顺序，相应的s和x的操作序列为 （　　）
A.sxsxssxx
B.sssxxsxx
C.sxssxxsx
D.sxssxsxx
若元素的入栈顺序是abcd，出栈顺序为acdb，则操作过程为：a入栈；a出栈；b、c入栈；c出栈；d入栈；d、b出栈。相应的s和x的操作序列为sxssxsxx。
D
√
二、栈的基本操作
6.栈初始为空，现将元素“听”“风”“吹”“雨”“过”依次入栈，若要求出栈顺序为“风”“吹”“听”“过”“雨”，则栈的容量至少为 （　　）
A.2 B.3 C.4 D.5
入栈、出栈过程为：“听”“风”入栈；“风”出栈；“吹”入栈；“吹”“听”出栈；“雨”“过”入栈；“过”“雨”出栈。因此栈的容量至少为2。
A
√
7.若某个栈的深度为3，a，b，c，d，e依次入栈，则下列出栈顺序不可能的是
（　　）
A.abcde B.acdbe
C.cbaed D.bedca
D
√
选项D，b最先出栈，则此时栈内元素为a；接着e要出栈，则c、d、e必须依次入栈，此时栈内元素为a、c、d、e，深度超过3，故不可能。
8.有如下Python程序段，使用列表模拟栈的操作：
st=[""]*7
top=-1
for i in range(3):
　top=top+1
　st[top]=str(i)
for i in range(2):
　top=top+1
　st[top]="A"
while st[top]=="A":
　top=top-1
执行该程序段后，top的值是 （　　）
A.3 B.2 C.6 D.5
B
√
已知栈的最大长度为7，首先将字符"0"、"1"、"2"入栈，此时栈顶指针top的值为2，然后再将"A"、"A"入栈，此时栈顶指针top的值为4，最后若栈顶元素为"A"，则将栈顶元素出栈，故"A"全部出栈，最后top的值为2。
三、栈的Python实现
9.［2025稽阳联考］有如下Python程序段：
s="info-Tec"
st=[]
key=1
for c in s:
　if "a"<=c<="z":
　　st.append(chr((ord(c)-ord("a")+key)%26+ord("a")))
　else:
　　st.pop()
　key=key%3+1
while len(st)!=0:
　print(st.pop(),end="")
执行该程序段后，输出的结果是 （　　）
A.effd B.hpfe C.efpj D.fgpipj
C
√
首先程序通过for循环遍历字符串s，并进行入栈、出栈操作。当c="i"时，字符循环右移1位，并入栈，st=["j"]，key=key%3+1=2；当c="n"时，字符循环右移2位，并入栈，st=["j","p"]，key=key%3+1=3；当c="f"时，字符循环右移3位，并入栈，st=["j","p","i"]，key=key%3+1=1；当c="o"时，字符循环右移1位，并入栈，s=["j","p","i","p"]，key=key%3+1=2；当c="-"时，出栈栈顶元素，st=["j","p","i"]，key=key%3+1=3；当c="T"时，出栈栈顶元素，st=["j","p"]，key=key%3+1=1；当c="e"时，字符循环右移1位，并入栈，st=["j","p","f"]，key=key%3+1=2；当c="c"时，字符循环右移2位，并入栈，st=["j","p","f","e"]，key=key%3+1=3。最后将栈st中的元素依次出栈并输出。
10.若在一个栈中，所有元素出栈的顺序是67，98，21，46，75，11，则可能的入栈顺序是 （　　）
A.11，67，21，46，98，75
B.75，11，46，21，67，98
C.67，21，98，75，46，11
D.98，21，46，67，11，75
C
√
选项A按照该顺序入栈，则98出栈之后下一个出栈的元素应是46或75。选项B按照该顺序入栈，则46出栈之后下一个出栈的元素应是11或21或67或98。选项D按照该顺序入栈，则67出栈后下一个出栈的应是46或11或75。选项C数据67入栈后出栈，数据21、98入栈后逐个出栈，75、46入栈后逐个出栈，最后11入栈后出栈。
11.［2026天域名校协作体］若元素入栈的顺序依次为A，B，C，D，E，约定操作：若当前栈顶元素P出栈后的出栈总次数是已入栈次数的一半，则将P元素出栈。最终栈中元素从栈底到栈顶的顺序是 (　　)
A.A，C，E B.A，B，D
C.A，C，D D.A，B，E
A
√
入栈出栈过程为：A、B入栈（共入栈2次），B出栈（共出栈1次）；C、D入栈（共入栈4次），D出栈（共出栈2次）；E入栈（共入栈5次）。最终栈中元素从栈底到栈顶的顺序是A，C，E。
12.［2025精诚联盟］队列q从队首到队尾的元素依次为1，2，3，栈s从栈底到栈顶的元素依次为4，5。约定：A操作是指元素出队并入栈，B操作是指元素出栈并入队，C操作是指元素出队后再入队。经过CBAA系列操作后，队列中元素的个数为
（　　）
A.1 B.2 C.3 D.4
B
√
执行C操作：1出队后入队，队列q变为2，3，1。执行B操作：5出栈后入队，队列q变为2，3，1，5，栈s变为4。执行A操作：2出队后入栈，队列q变为3，1，5，栈s变为4，2。执行A操作：3出队后入栈，队列q变为1，5，栈s变为4，2，3。最终队列中元素的个数为2。
13.栈和队列初始为空，数据均经过入栈→出栈→入队→出队操作后，栈和队列又为空。若数据入栈顺序是“礼”“乐”“射”“御”“书”“数”，出队顺序是“乐”“射”“书”“数”“御”“礼”，则栈的容量至少为 （　　）
A.2 B.3 C.4 D.5
B
√
出队顺序是“乐”“射”“书”“数”“御”“礼”，则入队和出栈顺序同样是“乐”“射”“书”“数”“御”“礼”。则数据入栈、出栈过程为：“礼”“乐”入栈；“乐”出栈；“射”入栈；“射”出栈；“御”“书”入栈；“书”出栈；“数”入栈；“数”“御”“礼”出栈。故栈的容量至少为3。
14.某栈中数据从栈底到栈顶实现降序排列，利用队列S将数据送入该栈。队列中原始数据依次为4，2，1，3，若队首数据大于栈顶数据，可利用操作M（出栈后再入队）调整数据入栈顺序，则操作M的执行次数至少为 （　　）
A.1 B.2 C.3 D.4
C
√
操作过程为：4、2、1依次出队后入栈；1、2依次出栈后入队；3、1依次出队后入栈；1出栈后入队；2、1依次出队后入栈。故操作M至少执行了3次。
15.已知栈s的最大深度为3，且初始为空，经过一系列入栈、出栈操作后，栈仍为空。若元素的入栈顺序为“梅”“兰”“竹”“菊”，设所有出栈序列中以“梅”为开头和以“梅”为结尾的序列个数分别为x和y，则x-y的值为 （　　）
A.0 B.1 C.2 D.3
B
√
已知栈s的最大深度为3，则出栈序列中以“梅”为开头的有“梅兰竹菊”“梅兰菊竹”“梅竹兰菊”“梅竹菊兰”“梅菊竹兰”，共5个。出栈序列中以“梅”为结尾的有“兰竹菊梅”“兰菊竹梅”“竹兰菊梅”“竹菊兰梅”，共4个。故x-y=5-4=1。
16.［2025杭州模拟］有1个队列Q，队首到队尾的元素依次为d，e，s，k，栈S初始为空。约定：О操作是指元素出队后入栈，I操作是指元素出栈后入队。经过OOIOOIO系列操作后，栈S的栈顶元素为 （　　）
A.d B.e C.s D.k
B
√
经过OO操作后，队列Q为s，k，栈S为d，e；经过I操作后，队列Q为s，k，e，栈S为d；经过OO操作后，队列Q为e，栈S为d，s，k；经过I操作后，队列Q为e，k，栈S为d，s；经过O操作后，队列Q为k，栈S为d，s，e。故栈S的栈顶元素为e。
17.元素1，2，3，4，5依次入栈，假设出栈序列为X，3，Y，Z，4，下列关于X、Y、Z的说法，正确的是 （　　）
A.X不可能为1
B.Y不可能为2
C.Z不可能为5
D.X、Y的值比Z小
D
√
已知3第2个出栈，4最后一个出栈，则第1个出栈的可能是1或2。第3个出栈的可能是1或2。第4个出栈的一定是5。
18.栈初始为空，经过一系列入栈、出栈操作后，栈又为空。若元素入栈的顺序为“红”“黄”“蓝”“白”“黑”，其中“白”第一个出栈，则下列说法不正确的是 （　　）
A.“黄”一定比“红”先出栈
B.最后一个出栈的元素可能是“黑”
C.可能的出栈序列个数为3
D.“蓝”可能第3个出栈
C
√
已知元素入栈的顺序为“红”“黄”“蓝”“白”“黑”，且“白”第一个出栈，则可能的出栈序列有“白蓝黄红黑”“白蓝黄黑红”“白蓝黑黄红”“白黑蓝黄红”，共4种。
19.［2025宁波九校联考］有如下Python程序段：
s=[0]*100;q=[0]*100
top=-1
result=0
exp="+1+23+456"
for c in exp[::-1] :
　if "0"<=c<="9":
　　top+=1
　　s[top]=int(c)
　elif top!=-1:
　　num=0
　　while top!=-1:
　　　num=num*10+s[top]
　　　top-=1
　　result+=num
print(result)
D
√
运行该程序段后，下列说法正确的是 (　　)
A.程序计算的是数学表达式654+32+1的运算结果
B.若加框处代码改为range(len(exp)-1,-1,-1)，则程序运行结果不变
C.若exp的值改为"1+23+456"，则程序运行结果不变
D.若exp的值改为"+1+23+456+"，则程序运行结果不变
该程序段逆序遍历字符串exp，若当前元素为数字字符，则转换成整型后入栈；否则，当栈不为空时，依次将栈顶元素出栈，通过按权相加将出栈的数字组成一个整数num，然后将num累加到result。对于exp="+1+23+456"，计算过程为：6、5、4入栈，4、5、6出栈，组成整数456；3、2入栈，2、3出栈，组成整数23；1入栈，1出栈，组成整数1，因此result=456+23+1=480。range(len(exp)-1,-1,-1)是字符串exp的索引序列，而不是字符串exp中的元素，程序会报错。若exp的值改为"1+23+456"，则最后一个整数1无法累加到result。
20.［2026江浙皖发展共同体］有如下Python程序段：
s=input("输入由小写字母组成的字符串：")
ans="";st=[""]*len(s);top=-1
for i in s:
　if top!=-1 and abs(ord(i)-ord(st[top]))==1:
　　top-=1
　else:
　　top+=1
　　st[top]=i
while top!=-1:
　ans=st[top]+ans
　top-=1
print(ans)
运行该程序段后，若输出的结果是“ct”，则输入的字符串s不可能是 (　　)
A."cutt" B."crst" 　C."cedbt" D."effect"
C
√
该程序段遍历字符串s中的元素，若栈st不为空且当前元素与栈顶元素的ASCII码值相差1，则出栈栈顶元素，否则入栈当前元素。最后依次出栈栈顶元素，并逆序连接到ans。若输入的字符串s为"cedbt"，则入栈出栈过程为："c"入栈，"e"入栈，"e"出栈（当前元素"d"与栈顶元素"e"的ASCII码值相差1），"c"出栈（当前元素"b"与栈顶元素"c"的ASCII码值相差1），"t"入栈。最后"t"出栈并连接到ans，故输出的结果为t。
21.有如下Python程序段：
w=input()
st=[""]*len(w)
top=-1
c=0
for i in w:
　if i=="(":
　　top=top+1
　　st[top]=i
　elif top>=0 and i==")":
　　top=top-1
　　c=c+1
print(c)
执行该程序段后，输入w的值为"()())(()(()))"，输出的结果是 （　　）
A.3 B.4 C.5 D.6
D
√
该程序段的功能是验证括号匹配问题。当遇到左括号时入栈；当遇到右括号时，若栈不为空，则出栈，且计数器c加1。w中包含6对匹配的括号，故输出的结果是6。
22.［2025嘉兴检测］有如下Python程序段：
s="01357987"
k=3
stack=[s[0]]
for char in s[1:]:
　while stack[-1]>char and k>0:
　　#删除stack列表的最后一个元素
　　stack.pop()　
　　k-=1
　stack.append(char)
while k>0:
　stack.pop()
　k-=1
while stack[0]=="0":
　#删除stack列表的第一个元素
　stack.pop(0)　
执行该程序段后，stack的值是 （　　）
A.["1","3","5","7"]
B.["7","9","8","7"]
C.["0","7","9","8","7"]
D.["0","1","3","5","7"]
A
√
该程序段首先将字符串s中的第一个字符入栈，然后遍历s中的剩余字符，若栈顶元素的值大于当前元素的值，且k大于0，则出栈栈顶元素并且k累减1，直到栈顶元素的值不大于当前元素的值或k不大于0，然后入栈当前元素；否则直接入栈当前元素。遍历结束后，若k大于0，则出栈栈顶元素并且k累减1直到k不大于0。最后删除列表stack前面值为"0"的元素。初始"0"入栈，然后"1"、"3"、"5"、"7"、"9"依次入栈，接着"9"出栈后"8"入栈，接着"8"出栈后"7"入栈，此时栈中元素依次为"0"、"1"、"3"、"5"、"7"、"7"，k的值为1，因此"7"出栈，最后删除栈底元素"0"。故最后stack的值是["1","3","5","7"]。
23.［2026江浙皖发展共同体］有如下Python程序段：
from random import randint
s=[0]*10
a=[5,7,2,8,4,3,6]
top=0
s[top]=a[0]
b=0
n=randint(5,len(a))
for i in range(1,n):
　while top!=-1 and a[i]>s[top]:
　　top-=1
　top+=1
　s[top]=a[i]
while top!=-1:
　b=b+s[top]
　top-=1
print(b)
D
√
for循环的作用是构造一个单调递减栈，n的取值范围是[5,7]。当n=5时，s=[8,4]；当n=6时，s=[8,4,3]；当n=7时，s=[8,6]。第2个while循环的作用是累计栈s的元素值，其值可能为12或15或14，故输出的结果不可能是21。
执行该程序段后，输出的结果不可能是 （　　）
A.12 B.14
C.15 D.21
执行该程序段后，输出的结果不可能是 （　　）
A.48,57,
B.74,80,76,
C.74,68,62,33,44,
D.98,45,78,88,
24.有如下Python程序段：
#随机产生n个两位正整数存入数组a
q=[-1]*n
top=-1
for i in range(n):
　if a[i]%3==0:
　　top+=1
　　q[top]=a[i]
　elif a[i]>q[top] and a[i]%2==0:
　　top+=1
　　q[top]=a[i]
while top>-1:
　print(q[top],end=",")
　top-=1
B
√
for循环的作用是将3的倍数或大于栈顶元素的偶数入栈。根据栈后进先出的特性，需要将输出序列逆序入栈。选项B中76和80是递增的偶数，可以先后入栈，但74小于80且不是3的倍数，不能入栈。
25.有如下Python程序段：
import random
n=6
s=[0]*n
top=-1
flag=True
for i in range(n):
　x=random.randint(1,100)
　if flag or top!=-1 and x%2!=s[top]%2:
　　top+=1
　　s[top]=x
　　flag=not flag
　elif top!=-1:
　　top-=1
print(s[:top+1])
执行该程序段后，输出的结果不可能是 （　　）
A.[88,75,42,85,78,93]
B.[]
C.[23,92,92,61]
D.[89,87,88,52,45,82]
D
√
当栈s非空，栈顶元素s[top]与变量x的奇偶性不同或flag的值为True时，x才能入栈，入栈后flag的值取反。不入栈时，若栈s非空则出栈1个元素。选项D中89入栈后，flag更新为False，87为奇数不会入栈，89会出栈，故输出结果不可能为选项D。
26.有如下Python程序段：
stk=[5,2,6,3,7]
lst=[""]*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
√
在while循环中，当栈stk不为空时，变量s累加栈顶元素的值，若s是a的倍数，则跳出循环，否则将栈顶元素入列表lst，每循环一次会出栈一个元素。最后在for循环中将列表lst的元素全部入栈stk。当a为2时，lst为[7,"","","","","","","","",""]，stk为[5,2,6,3,7]；当a为3时，lst为[7,3,6,"","","","
","","",""]，stk为[5,2,7,3,6]；当a为4时，lst为[7,3,"","","","","","","",""]，stk为[5,2,6,7,3]。
27.［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和列表stkb模拟栈a和栈b，topa和topb分别为栈a和栈b的栈顶指针。操作1：当栈a的栈顶元素大于栈b的栈顶元素时，若两者相加为奇数，则将栈b的栈顶元素出栈后入栈a；否则将栈b的栈顶元素出栈。反复执行操作1，直到栈b为空或栈a的栈顶元素不大于栈b的栈顶元素。操作2：此时若栈b仍不为空，则再出栈一个元素，同时将栈a的栈顶元素出栈并累加到变量s。对于题干给出的值，首先执行操作1：初始栈a中的元素为[6]，栈b中的元素为[2,7,2,1,5]；6>5且6+5为奇数，则5出栈b后入栈a，此时栈a为[6,5]，栈b为[2,7,2,1]；5>1，但5+1不为奇数，则1直接出栈，此时栈b为[2,7,2]；5>2且5+2为奇数，则2出栈b后入栈a，此时栈a为[6,5,2]，栈b为[2,7]。2<7，执行操作2：栈b不为空，则7出栈，此时栈b为[2]；将栈a的栈顶元素出栈并累加到变量s，此时栈a为[6,5]，s为2。继续执行操作1：5>2且5+2为奇数，则2出栈b后入栈a，此时栈a为[6,5,2]，栈b为空。由于栈b为空，后续不会再执行操作1，将反复执行操作2直到栈a为空，因此最终s=2+2+5+6=15。
28.将十进制数转换为二进制数可以采用栈的处理思想，使用Python程序实现进制转换的代码如下：
x=int(input("输入一个十进制数："))
result=[0]*20　#空栈
top=-1　#栈顶指针
while x>0:
　B=x%2
　　　　① 　　　
　result[top]=B
　x=　　　② 　　　
while top>-1:
　print(　　　③　　　,end="")
　top=top-1
请回答下列问题：
（1）若输入的十进制数为23，则输出的二进制数是　　　　　　　。
（2）请在画线处填入合适的代码。
10111
①top+=1　②x//2　③result[top]
（1）将十进制数23转换为二进制数的结果是10111。　（2）①处有元素入栈，要更新栈顶指针，故填入代码为top+=1。②处的作用是对x重新赋值进行下一次循环，已知十进制转换为二进制使用的是“除2取余”的方法，所以被除数x应该变为原x除2之后获得的商，即x//2。③处的作用是将获得的二进制数输出，已知二进制数是由获得的余数逆序拼接得到的，所以此处将得到的数据输出就是将result中的元素逐个出栈，即将栈顶元素出栈，故填入代码为result[top]。
29.在实验室的架子上存放着一排重量不等的砝码，在做实验的过程中，需要使用砝码称量一定量的物品质量。例如，称取10g的高锰酸钾，可以使用一个10g或者2个5g的砝码进行称取。请回答下列问题：
（1）小明想要称取21克的氯化钠固体，架子上从0~7的位置编号上依次存放了如下质量的砝码（单位：g）：1，5，6，7，9，10，12，15。若必须取用12g的砝码，则取用的其他砝码在架子上的位置编号是　　　　。
4
（1）若必须使用12克的砝码称取21克的氯化钠，则其他砝码的总重为9g，故取用的其他砝码在架子上的位置是4。
（2）由于每次手动计算会浪费大量的时间，小明编写了如下Python程序，运行界面如图所示，请在画线处填入合适的代码。
def weigh(t,lis):
　n=len(lis)
　stack=[]
　k=0;c=0
　while stack or k　　while t>0 and k　　　if t>=int(lis[k]):
　　　　stack.append(k)
　　　　t=　　　① 　　　
　　　k+=1
　　　if t==0:
　　　　print('取位置为',stack,'的砝码')
　　　　c+=1
①t-int(lis[k])
　　if 　　　②　　　:
　　　k=stack.pop()
　　　t+=int(lis[k])
　　k+=1
　if c==0:
　　print("无方案")
m=int(input("物品重量m："))
fm=input("架子上的砝码重量依次是：")
#将fm转换为列表
shelf=　　　③ 　　　　
print("拿取砝码的方案有：")
weigh(m,shelf)
②len(stack)!=0
③fm.split(",")
（2）①处自定义函数weigh(t,lis)中，stack存放取用的砝码的位置，t为待称的总重量，当某个位置的砝码满足if条件时，stack存储该砝码的位置k，观察后续语句，当t的值为0时，输出stack，说明此时所有的砝码重量和与t相等，故当一个砝码的位置存储到stack中之后，t的值要减去该砝码的重量，以控制下一个砝码的选择范围，注意列表lis中元素的数据类型为字符串类型，应将其转换为整型之后再进行运算，故填入代码为t-int(lis[k])。②处执行pop()方法的条件是列表不为空，此处为将上一个方案中stack内的元素出栈，在列表lis中寻找其他的可能方案，故填入代码为len(stack)!=0。③处输入的内容默认为字符串，根据运行界面可知，输入的砝码重量用“,”分隔，在程序操作的时候，shelf变量应该是一个列表，将字符串转换为列表的方法是split()，需要设置分隔符为逗号，故填入代码为fm.split(",")。
①t-int(lis[k])　②len(stack)!=0　③fm.split(",")　

展开更多......

收起↑