专题20 栈课件-2025-2026学年高考信息技术总复习

该高中信息技术高考复习课件聚焦“栈”专题，依据高考评价体系梳理了栈的概念、特性、基本操作（入栈、出栈）及数组与链栈实现等核心考点，对接计算思维（抽象建模、编程实现）和信息意识的水平4考查要求。通过考点诊断和近3年浙江选考真题分析，明确出栈序列判断（如2024浙江选考“生旦净末丑”序列题）、Python代码实现（数组栈顶指针操作、链栈头节点处理）、应用（逆波兰表达式、任务调度）等高频考向，构建完整备考体系。 课件亮点在于“真题情境+技巧拆解+素养融合”，如以2025浙江选考逆波兰表达式计算题为例，提炼“数字入栈-运算符出栈计算”四步法，结合栈顶指针动态变化图培养计算思维。特设“出栈序列规则表”（左右元素判断法）和“Python代码填空模板”（如例7括号匹配的top指针调整），帮助学生突破“栈顶指针初始值”“链栈头节点操作”等易错点，教师可依托真题实例精准教学，助力学生高效冲刺高考。

专题 20 栈 1 知识梳理 归纳提升 题型考法 考点1 栈的概念 1.栈是一种__________的线性结构。 2. 栈仅允许在表的一端进行插入或删除，进行插入或删除操作的一端称为栈顶，将表的另一端称为栈底。 3. 位于栈顶位置的元素称为栈顶元素，位于栈底位置的元素称为栈底元素。 先进后出　 知识梳理 归纳提升 题型考法 考点2 栈的特性 1.先进后出、后进先出。 2.有限序列性 （1）栈中的元素是有限的。栈可以是空的，也可以包含多个元素。 （2）栈中的所有元素呈线性关系，每个元素只有一个前驱点（栈底元 素没有前驱点）和一个后继点（栈顶元素没有后继点）。 知识梳理 归纳提升 题型考法 考点3 栈的基本操作（数组实现的栈） 1.建栈 （1）栈一般按顺序结构存储，用__________来实现。 （2）在 Python 中一般用列表（数组）创建栈。 （3）设栈顶指针 top 指向栈顶元素所在的位置。若栈为空，则 top 值 为_______。 2.入栈 （1）数据只能从栈顶入栈，新入栈的元素称为栈顶元素。 （2）每次数据元素入栈，栈顶指针变量top值加 1。 数组　 　-1　　 知识梳理 归纳提升 题型考法 3.出栈 （1）数据只能从栈顶出栈，每次出栈的元素是栈顶元素，栈顶元素出 栈后，其前驱顺位为新的栈顶元素。 （2）栈顶元素取出，栈顶指针变量 top 值减 1，若栈为_______，即 top=-1，则无法进行出栈操作。 空　　 知识梳理 归纳提升 题型考法 考点4 链栈（链表实现的栈） 利用链式存储方式实现的栈称为链栈，一般用单向链表实现。基本操作如下： （1）链表___________即为栈顶指针 top。 （2）入栈时，新入栈的元素作为链表新的头节点。 （3）出栈时，把头节点出栈。 头指针　　 知识梳理 归纳提升 题型考法 判断正误，正确的画“√”，错误的画“×”。 1. 栈的数组实现中，栈顶指针 top 初始值为 0，表示栈为空。 （　　） 2. 若元素入栈顺序为 a，b，c，d，e，f，已知最后出栈的元素依次为 c，f，则其出栈顺序可能是 b，e，a，d，c，f。 （　　） 3. 若栈的初始状态和最终状态均为空，则元素的出栈序列总数与入栈顺序无关。 （　　） ×　　 ×　　 ×　　 知识梳理 归纳提升 题型考法 判断方法：遍历出栈序列，每出栈一个元素，则在入栈序列中划掉该元素。 可知，该元素左边的是已经入栈的元素，该元素右边的是尚未入栈的元素。 知识梳理 题型考法 归纳提升 则下一个出栈的元素只能是当前划掉元素的左边最近一个未出栈（没划掉）元素，或右边任意一个未入栈元素。（图示中，D 之后出栈的是 C，也可以是 E、F、G） 若出栈序列中的下一个元素与上述描述不符，则说明该出栈序列错误。（图示中，C 之后出栈的只能是 B 或 E、F、G） 知识梳理 题型考法 归纳提升 （1）栈的数组实现。 st=[0]*n #创建长度为 n 的空栈 top=-1 #栈中无元素，top 指向-1 top+=1 #有元素入栈，栈顶指针后移 st[top]="A" #修改栈顶元素为新元素 A top-=1 #直接将栈顶指针指向前一位，表示元素出栈 print(top+1) #列表下标第一位从 0 开始，0~top 是栈中所有元素的下标，输出 top+1 即是输出栈中元素的个数 知识梳理 题型考法 归纳提升 （2）利用列表自带方法实现。 st=[] #创建空栈 st.append("A") #直接添加元素在列表末尾，不用修改栈顶指针 #栈顶元素即列表末尾元素 st[-1] st.pop() #直接删除列表末尾元素表示出栈 print(len(st)) #输出栈中元素的个数 知识梳理 题型考法 归纳提升 逆波兰表达式是将运算符放置在对应的运算数字之后的一种数学表达式。比如中缀表达式“5+((6+7)*8)-9”转换为逆波兰表达式是“5 6 7 + 8 * + 9 -”，可以发现逆波兰表达式里没有括号。具体的转换方法为： （1）先把中缀表达式里每一步运算都加上括号，如“( (5 + ((6 + 7) * 8) ) - 9)”。 （2）然后将对应的操作符（运算符）挪到对应的括号后面，如“((5 ((6 7) + 8) * )+ 9)-”。 （3）最后去掉括号就得到了后缀表达式“5 6 7 + 8 * + 9 -”。 知识梳理 题型考法 归纳提升 （4）具体代码如下： s="5 6 7 + 8 * + 9 -" lis=s.split(" ") print(lis) st=[0]*len(s) top=-1 for i in range(len(lis)): if "0"<=lis[i]<="9": top+=1 st[top]=int(lis[i]) else: num2=st[top] num1=st[top-1] top-=2 if lis[i]=="+": top+=1 st[top]=num1+num2 elif lis[i]=="-": top+=1 st[top]=num1-num2 elif lis[i]=="*": top+=1 st[top]=num1*num2 elif lis[i]=="/": top+=1 st[top]=num1/num2 print(st[top]) 知识梳理 题型考法 归纳提升 考向一 栈的出栈入栈序列 例 1 ［2025浙江选考］有后缀表达式“1 3 + 2 * 3 + 2 *”，现利用栈计算该表达式：从左向右扫描，遇到数字时，数字入栈；遇到运算符时，两个元素出栈，用运算符计算，所得结果入栈。如此反复操作，直到扫描结束，栈顶元素是 （　　） A.21 B.22 C.23 D.24 B 例1 B 将后缀表达式“1 3 + 2 * 3 + 2 *”转换成中缀表达式为“((1+3)*2+3)*2”，计算结果为 22，即栈顶元素。 √ 知识梳理 归纳提升 题型考法 例 2 ［2025杭州模拟］有 1 个队列 Q，队首到队尾的 元 素 依 次 为 "d"，"e"，"s"，"k"，栈 S 初 始 为 空 。约定：О 操作是指元素出队后入栈，I 操作是指元素出栈后入队。经过 OOIOOIO 系列操作后，栈 S的栈顶元素为 （　　） A."d" B."e" C."s" D."k" B 例 2 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"。 √ 知识梳理 归纳提升 题型考法 例 3 ［2024 浙江选考］栈初始为空，经过一系列入栈、出栈操作后，栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”，则所有可能的出栈序列中，以“旦”结尾的序列个数为 （　　） A.3 B.4 C.5 D.6 C 例 3 C 根据栈“先进后出”的特点，若“旦”是最后一个出栈，则“生”一定是第一个出栈。所有可能的出栈序列有5 种，即“生净末丑旦”“生净丑末旦”“生末净丑旦”“生末丑净旦”“生丑末净旦”。 √ 知识梳理 归纳提升 题型考法 例 4 ［2025 浙江 9+1 联盟］元素 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 例 4 D　如出栈序列为 1，3，2，5，4，故 X 可能为 1，Y 可能为 2，Z 可能为 5。 √ 知识梳理 归纳提升 题型考法 考向 二 栈的 Python 实现 例 5 有如下 Python 程序段： s=[""]*len(a) head=2 q=head top=-1 while q!=-1: top+=1 s[top]=a[q][0] q=a[q][1] print(s[top-2]) 若 a=[["a",3],["b",0],["c",1],["d",-1]]，则输出的结果是 （　　） A.a B.b C.c D.d B 例 5 B　根据 head 的值可知，链表 a 中元素的排列顺序是 c→b→a→d，程序将链表中的元素按顺序逐个入栈，得到 栈 s 为["c","b","a","d"]，top=3，故 s[top-2]的值为"b"。 √ 知识梳理 归纳提升 题型考法 例 6 ［2025 台州期末］有如下 Python 程序段： import random a=["A","B","*","C","D"] t=[] for i in range(len(a)): op=random.randint(0,1) if op==1 and a[i]!="*": t.append(a[i]) a[i]="*" elif op==0 and a[i]=="*" and len(t)>0: c=t.pop() a[i]=chr((ord(c)-ord("A")+3)%26+ ord("A")) 执行该程序段后，a 的值不可能是 （　　） A.["A","*","*","C","D"] B.["*","B","D","*","D"] C.["*","*","E","C","D"] D.["*","*","A","*","*"] D 例 6 D 该程序段遍历列表 a，每次生成 0 或 1 存储在变量op中，若op的值为1且a[i]的值不为"*"，则a[i]入栈 t，然后 a[i]更新为"*"；若 op 的值为 1 且 a[i]的值为"*"且栈不为空，则弹出栈顶元素，并存储在变量c中，然后将字符c向右偏移3位的结果赋值给a[i]。因此，列表a中非"*"的元素可能会入栈并更新为"*"，元素"*"可能会变为其前面入栈元素向右偏移 3位的字符，也可能保持不变。选项D中，元素"A"和"B"入栈，所以都变为"*"，第3个元素"*"可能会变为"B"向右偏移3位的字符，即"E"，或保持不变，不可能变为"A"。 √ 知识梳理 归纳提升 题型考法 例 7 ［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 else: 　　　（2）　　　 ans+=　　　（3）　　　 划线处有如下可选代码： ①top!=-1 ②top==-1 ③top+=1 ④top-=1 ⑤top//2 ⑥(top+1)//2 划线处应填入的正确代码为 （　　） A.①③⑥ B.①④⑤ C.②④⑤ D.②④⑥ D 例 7 D top 作为栈顶指针，用于计算已经出现的左括号的个数。当出现右括号时，若 top==-1，即没有左括号配对，则需要将该右括号改成左括号（ans+=1），同时左括号数量加 1（top+=1），否则减少未配对的左括号的个数 （top-=1）。最后，将多余的左括号中的一半转为右括号（ans+=(top+1)//2）。 √ 知识梳理 归纳提升 题型考法 考向 三 栈的应用 例 8 有 n 项任务，每项任务包含任务名、出现时刻、所需时长和紧急程度（数字越大紧急程度越高）。每个时刻只能执行一项任务，且按出现时刻先后顺序执行，若执行过程中出现了紧急程度更高的任务，则正在执行的任务将被暂停，执行紧急程度更高的任务。编写 Python 程序模拟任务执行过程，功能如下：程序运行时，各项任务 数据按出现时刻升序显示，处理完按照任务完成时刻输出。任务列表信息如图 a 所示，程序运行界面如图 b 所示。 知识梳理 归纳提升 题型考法 请回答下列问题： （1）若有任务列表信息为[["T0",2,5,2],["T1",5,4,1],["T2",6,5,3],["T3",9,5,4]]，则系统处理完毕后，各任务完成的先后顺序为　　　　　　　（填写任务名，并用“，”分隔）。 （2）实现上述功能的 Python 程序如下，请在划线处填入合适的代码。 '''task 添加 n 个任务，按任务出现时刻先后，对任务升序排序 例如 task=[["T0",5,4,2], ["T1",8,5,3], ["T2",13,4,1],["T3",16,3,4]]，代码略''' n=len(task) st=[0]*(n+1) top=-1 print("任务完成时刻 --------------") cur=0 T3，T2，T0，T1 知识梳理 归纳提升 题型考法 for i in range(n): while top! =-1 and task[i] [1] >=cur+task[st[top]][2]: #参数 sep="\t"实现对齐输出 print(task[st[top]] [0], cur+task[st[top]][2],sep="\t") cur+=task[st[top]][2] top-=1 if top!=-1: task[st[top]][2]-=　　　①　　　 top+=1 j=top-1 while j!=-1 and 　　　②　　　: st[j+1]=st[j] j-=1 st[j+1]=i cur=task[i][1] while 　　　③　　　: print(task[st[top]][0],cur+task[st[top]][2],sep="\t") cur+=task[st[top]][2] top-=1 task[i][1]-cur task[st[j]][3]>=task[i][3] top!=-1 知识梳理 归纳提升 题型考法 例 8 （1）T3，T2，T0，T1 （2）①task[i][1]-cur ②task[st[j]][3]>=task[i][3] ③top!=-1 （1）T0 先执行了 4 时刻，此时出现 T2，其任务紧急程度最高，T0 暂停，执行 T2；3 时刻后，出现 T3，其任务紧急程度最高，执行 T3；14 时刻时，T3 执行完成，然后按照紧急程度依次执行 T2、T0、T1，因此各任务完成的先后顺序为 T3，T2，T0，T1。 （2）①处更新正在执行的任务的所需时长，即用任务的所需时长 task[st[top]][2]减去已执行的时长（即任务 i 的出现时刻 task[i][1]减去当前任务开 始的时刻 cur），故填入代码为 task[i][1]-cur。②处出现了新任务，需要比较紧急程度，由下文代码可知，填入代码为 task[st[j]][3]>=task[i][3]。③处通过 while 循环输出任务及完成时刻，每输出一个，top 递减 1，故循环条件为top!=-1。 知识梳理 归纳提升 题型考法 THANK YOU $$