第11课 栈1——初识栈-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

第三章│字符串、队列和栈 ——3.3　栈，教材P82～90 第11课　栈1——初识栈 新课程目标 1.理解栈的概念和特性。　2.掌握栈的基本操作，并能编程实现。 目录 CONTENTS 教材整体感悟 知本与探源 01 02 命题整体感知 尝试与研析 01 教材整体感悟 知本与探源 教材整体感悟 知本与探源 1． 栈的概念与特性 (1)栈的概念 ①同队列一样，栈也是一种操作受限的___________，仅允许在表的 _________进行插入或删除。 ②进行插入或删除操作的一端称为________，位于栈顶位置的元素称为 ____________；相应地，将表的另一端称为________，位于栈底位置的元素为_____________。 　线性表　 　一端　 　栈顶　 　栈顶元素　 　栈底　 　栈底元素　 教材整体感悟 知本与探源 (2)栈的特性 ①栈具备“____________、____________”的特点。 ②______________：栈中的元素是__________。栈可以是________，也可以包含多个元素。栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。 　先进后出　 　后进先出　 　有限序列性　 　有限的　 　空的　 教材整体感悟 知本与探源 2． 栈的基本操作 栈一般按顺序结构存储，可以用数组实现，常用操作有__________、 ________、________等。 　建栈　 　入栈　 　出栈　 教材整体感悟 知本与探源 (1)在Python中，当要存储n个元素时，可以用列表创建一个长度为n的栈。例如，创建一个长度为4的栈st，Python代码实现如下： top＝－1 st＝[0]*4 (2)入栈又叫压栈操作，把数据元素压入栈顶。每次入栈时，栈顶指针变量top值加1，再给st[top]赋值。例如，入栈顺序为 1 2 3，Python代码实现如下： 教材整体感悟 知本与探源 top＋＝1 st[top]＝1 top＋＝1 st[top]＝2 top＋＝1 st[top]＝3 (3)出栈时把栈顶元素取出，同时栈顶指针变量top值减1，如果栈中没有 教材整体感悟 知本与探源 元素，即top＝－1时，不能进行出栈操作。例如，出栈顺序为 3 2 1，Python代码实现如下： print(st[top]) top＝top－1 print(st[top]) top＝top－1 print(st[top]) 教材整体感悟 知本与探源 top＝top－1 (4)用列表自带的函数和方法实现栈 Python中用自带的函数和方法可以实现建栈、入栈、出栈、栈中元素个数的统计等操作。例如： st＝[]　　　　　　　#建立一个空栈st st.append(”A”) #字母A入栈 st.append(”B”) #字母B入栈 教材整体感悟 知本与探源 print(st[1]) #输出栈顶元素，为字母B print(len(st)) #输出栈中元素个数，为2 st.pop() #弹出栈顶元素，栈顶出栈 print(len(st)) #输出栈中元素个数，为1 教材整体感悟 知本与探源 本课核心点 ● 重难点 1．利用栈实现十进制转R进制(2<＝R<＝16) (1)Python程序： 教材整体感悟 知本与探源 方法1 方法2 top＝－1 st＝[””]*100　#创建栈st n＝int(input(”请输入十进制数n：　”)) r＝int(input(”请输入转换后的进制r：　”)) while n！＝0： t＝n%r n＝n//r top＋＝1 if t<＝9： st[top]＝str(t)　　#余数入栈 else： 　　st[top]＝chr(t＋55) #余数入栈 print(”转换结果为：　”，end＝””) while top>＝0：　#依次出栈，余数逆序连接 print(st[top]，end＝””) top－＝1(2) st＝[] n＝int(input(”请输入十进制数n：　”)) r＝int(input(”请输入转换后的进制r：　”)) while n！＝0： t＝n%r n＝n//r if t<＝9： st.append(str(t))　 #余数入栈 else： 　　st.append(chr(t＋55)) #余数入栈 print(”转换结果为：　”，end＝””) while len(st)>0：　#依次出栈，余数逆序连接 print(st.pop()，end＝””) 教材整体感悟 知本与探源 (2)运行结果： (3)图示说明： 教材整体感悟 知本与探源 2．括号匹配 设计一个程序，判断输入的数学计算式中的括号(只有小括号)是否匹配。 (1)Python程序：   方法1 方法2 st＝[””]*100 top＝－1 flag＝True　　 #标记是否有不匹配的情况 s＝input(”请输入数学计算公式：　”) for i in range(len(s))： if s[i]＝＝”(”： top＋＝1 st[top]＝s[i] elif s[i]＝＝”)”： st＝[] s＝input(”请输入数学计算公式：　”) flag＝True　　 #标记是否有不匹配的情况 for i in range(len(s))： if s[i]＝＝”(”： st.append(s[i]) elif s[i]＝＝”)”： if len(st)＝＝0： flag＝False 教材整体感悟 知本与探源 (2)运行结果： 请输入数学计算公式：　((a＋b)－c*((6＋)) 括号不匹配 if top＝＝－1： flag＝False break else： top－＝1 if top>＝0： flag＝False if flag： 　print(”括号匹配”) else： print(”括号不匹配”) break st.pop() if flag and len(st)＝＝0： 　print(”括号匹配”) else： print(”括号不匹配”) 02 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例1下列关于栈的说法中，不正确的是(　　) A．栈是一种操作受限的线性表 B．栈仅允许在表的一端进行插入或删除操作 C．栈不能为空，至少应包含一个元素 D．栈的特点是先进后出 【解析】 栈中的元素是有限的，可以是空的，也可以包含多个元素，选项C错误。 C 命题整体感知 尝试与研析 变式1下列关于栈的说法中，正确的是(　　) A．栈按照“先进先出”的方式组织数据　　　　　　 B．可以选中栈的中间位置插入新元素 C．不能删除栈顶位置的元素 D．不能在栈底位置插入新元素 【解析】 新元素入栈需要在栈顶进行，选项D正确。 D 命题整体感知 尝试与研析 例2一个栈的入栈顺序为1，2，3，4，5，则其出栈顺序不可能为(　　) A．1，2，3，4，5　　　　　B．4，5，3，2，1　　　　　 C．4，3，5，1，2　　　　　D．3，2，1，5，4 【解析】 判断出栈顺序的方法：对于某个数据而言，在它之前入栈但在它之后出栈的数据，是按入栈顺序的逆序出现的。选项A，按入栈的顺序出栈， 选项符合题意；选项B， 对4，5来说，3，2，1都是先它们入栈， 后它们出栈， 出栈是逆序的，选项符合题意；选项C， 对4，3，5来说， 2，1都是先它们入栈但后它们出栈的， 所以应该是2先出栈，选项不符合题意；选项D， 使用上面的方法判断， 选项符合题意。 C 命题整体感知 尝试与研析 变式1设栈S的初始状态为空，元素a，b，c，d，e，f，g依次入栈S。入栈和出栈可以交替进行，且7个元素出栈的顺序是b，d，c，f，e，a，g，则栈S的容量至少应该为(　　) A．1 B．2 C．3 D．4 【解析】 根据元素的入栈和出栈的顺序，第二个出栈的是“d”，当该元素出栈时，栈中至少有“a，c，d”三个元素，故栈的容量至少为3，选项C正确。 C 命题整体感知 尝试与研析 变式2有一个空栈，若元素“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”还没有入栈。若“o”出栈后，依次将栈中的元素全部出栈，然后“n”入栈、出栈，则最后一个元素为“n”；若“o”出栈后，在栈中的“P”出栈前任何时间“n”入栈、出栈，则最后一个出栈的元素为“P”，故选项A、B 均错。因“o”第一个出栈，可以判断元素“P”“y”“t”“h”均已在栈中，故元素“P”“y”“t”“h”“o”的出栈顺序是确定的，即为“o”“h”“t”“y”“P”，故选项D 错误。 命题整体感知 尝试与研析 例3有如下Python程序段： a＝”1A2B” ans＝[] for ch in a： if ”0”<＝ch<＝”9”： num＝int(ch) else： 命题整体感知 尝试与研析 num＝ord(ch)－ord(”A”)＋10 st＝[] for i in range(4)： st.append(str(num%2)) num//＝2 ans＝ans＋st[：：－1] print(ans) 命题整体感知 尝试与研析 执行该程序段后，输出的结果是(　　) A．['0'，'0'，'0'，'1'，'1'，'0'，'1'，'0'，'0'，'0'，'1'，'0'，'1'，'0'，'1'，'1'] B．['1'，'1'，'0'，'1'，'0'，'0'，'0'，'1'，'0'，'1'，'0'，'1'，'1'] C．['1'，'0'，'0'，'0'，'0'，'1'，'0'，'1'，'0'，'1'，'0'，'0'，'1'，'1'，'0'] D．['1'，'1'，'0'，'1'，'0'，'1'，'0'，'1'，'0'，'1'，'1'] A 命题整体感知 尝试与研析 【解析】 程序实现的是把十六进制数“1A2B”转换为二进制数，结果为“0001101000101011”，选项A正确。 命题整体感知 尝试与研析 变式1有如下Python程序段： a，b＝map(int，input().split()) w＝0 while b**w<＝a： w＋＝1 st＝[0]*w；top＝－1 while a>0： 命题整体感知 尝试与研析 top＝top＋1 st[top]＝a%b a＝a//b while top>－1： print(st[top]，end＝””) top＝top－1 命题整体感知 尝试与研析 若输入的值为“17 8”，则输出的结果是(　　) A．21 B．12 C．17 D．71 【解析】 利用栈实现进制转换，将17转换为8进制，选项A正确；第1个循环，找出b进制数的位数，再设置栈的容量；第2个循环将10进制数转换成b进制数，并依次入栈；第3个循环依次出栈。 A 命题整体感知 尝试与研析 变式2用栈的数据结构编写进制转换中的“除二取余法”的Python程序段如下： st＝[－1]*100 top＝－1 n＝int(input(”请输入一个十进制数：　”)) while n>0： # 命题整体感知 尝试与研析 while top！＝－1： print(st[top]，end＝””) top－＝1 上述程序段中加框处的代码由以下四部分组成： ①n＝n//2　②top＋＝1　③x＝n%2　④st[top]＝x 下列选项中，代码顺序正确的是(　　) A．③④②① B．③①②④ C．①②③④ D．①③④② B 命题整体感知 尝试与研析 【解析】 利用栈实现进制转换，由于top等于－1，需要先将top后移，再入栈，选项B正确。 命题整体感知 尝试与研析 例4有如下Python程序段： w＝input() flag＝True st＝[””]；top＝－1 c＝0 for i in w： if flag and i＝＝”(”： 命题整体感知 尝试与研析 top＝top＋1 st[top]＝i flag＝False elif not flag and i＝＝”)”： 　 top＝top－1 　 c＝c＋1 　 flag＝True 命题整体感知 尝试与研析 print(c) 若输入w的值为“()()(()()))”，执行该程序段后，则输出的结果是(　　) A．6 B．3 C．4 D．5 【解析】 利用栈进行括号匹配判断，当条件“flag and i＝＝”(””成立时，左括号入栈，并将flag设为False；当flag是False时，再遇到“(”，不入栈；当条件“not flag and i＝＝”)””成立时，左括号出栈，并将flag设为True，选项C正确。 C 命题整体感知 尝试与研析 变式1有如下Python 程序段： s＝”abbacabcbbcc”；s1＝”” st＝[””]*100；top＝－1 top＋＝1；st[top]＝s[0] for i in s[1：]： if i！＝st[top]： top＋＝1；st[top]＝i 命题整体感知 尝试与研析 else： top＝top－1 while top>＝0： s1＝st[top]＋s1；top－＝1 执行该程序段后，变量s1 的值为(　　) A．'acba' B．'cbac' C．'abca' D．'cabc' D 命题整体感知 尝试与研析 【解析】 利用栈进行去重操作，先将s[0]入栈，接着依次判断，如果栈头元素与s[i]相等，则top前移(出栈)；如果不同则入栈；最后st＝[”c”，”a”，”b”，”c”]；最后循环出栈，由于“s1＝st[top]＋s1”逆序连接，选项D正确。 命题整体感知 尝试与研析 变式2[2023·温州中学检测]有如下Python程序段： s＝list(input()) # 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 【解析】 从代码中不难发现，遇到'('　时，对应的下标入栈，遇到')'，元素出栈。同时列表元素重新组合，组合原则：两端不动，最内层配对括号内的元素翻转，同时将这对括号抛弃。过程如下：(ed(y(oc))p)－>(ed(yco)p)－>(edocyp)－>pycode，选项A正确。 A 命题整体感知 尝试与研析 例5[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 命题整体感知 尝试与研析 【解析】 本题考查栈的运用。列表stk 用于模拟栈，变量top 即栈顶指针。依次读取列表a 中每个元素a[i]，并同时随机产生0 或1 赋值给变量op。接下来只有两种情况会改变a[i]的值：①op 为1 且a[i]值不为“#”时(为字母)，将a[i]入栈并将其值变为“#”；②op 为0 且栈不为空且a[i]值为“#”时，出栈并将值赋给a[i]。选项A，当op 的值每次都是0 时即可实现；选项B，当op 的值每次都是1 时即可实现；选项C，当op 的值依次是1，0，1，1，0，0，0 时即可实现；选项D，a[0]，a[1]值是“#”，表明“A”“B”均已入栈，则出栈顺序一定是“B”“A”，故选项中a[2]、a[3]值为“A”“B”不可能。 命题整体感知 尝试与研析 变式1有如下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 命题整体感知 尝试与研析 执行该程序段后，输出的结果不可能是(　　) A．48，57， B．74，80，76， C．74，68，62，33，44， D．98，45，78，88， 【解析】 当a[i]是3的倍数时，将a[i]的值入栈。当a[i]大于栈顶元素q[top]，且a[i]是偶数时，将a[i]的值入栈。最后栈中的元素依次出栈。选项A，数字48和57是3的倍数，入栈顺序为57，48，输出的出栈顺序为48，57，选项正确；选项B，数字74，80，76都是偶数，若出栈顺序为74，80，76，则入栈顺序为76，80，74，其中74小于栈顶元素80，不符 B 命题整体感知 尝试与研析 合入栈条件，选项错误；选项C，数字33是3的倍数，数字74，68，62，44是偶数，入栈时符合a[i]大于栈顶元素q[top]，入栈顺序为44，33，62，68，74，出栈顺序为74，68，62，33，44，选项正确；选项D，数字45，78是3的倍数，数字98，88是偶数，入栈时符合a[i]大于栈顶元素q[top]，入栈顺序为88，78，45，98，出栈顺序为98，45，78，88。 命题整体感知 尝试与研析 变式2某算法利用“栈”的思想进行字符串处理，其步骤如下：①创建长度为n 的空栈，字符依次入栈；②当达到栈满状态或数据全部入栈时，字符依次出栈，按照出栈顺序连接成新字符串；③若还有未处理的字符，则重复步骤①②，直到全部字符处理完毕。实现该功能的Python 程序段如下： s＝input(”请输入字符串：　”) n＝5；st＝[””]*n top＝－1；i＝0；m＝”” 命题整体感知 尝试与研析 while i<len(s)： 命题整体感知 尝试与研析 上述程序段中加框处可选的代码有： ①top－＝1　②top＋＝1　③top＋1<n　④top<n 下列选项中，代码顺序正确的是(　　) A．④②① B．③①② C．③②① D．④①② 【解析】 条件(1)处后面的相应代码是入栈的操作，那么栈不能为满的状态。栈满时top＝＝n－1，所以此处代码：top＋1<n；每次入栈时，栈 C 命题整体感知 尝试与研析 顶指针变量top 值加1，以便元素入栈，(2)处代码：top＋＝1。(3)是出栈操作，出栈是取出栈顶元素，同时top 值减1，代码：top－＝1，选项C正确。 命题整体感知 尝试与研析 |随|堂|检|测| 1． 栈和队列都是线性表结构，下列关于栈和队列的异同点的说法中，正确的是(　　) A．队列存储可以使用数组实现，栈不可以用数组存储 B．队列的队首元素和栈的栈顶元素都是最先进入的元素 C．队列和栈中的每个元素(不包含首尾元素)都有一个前驱点和后继点 D．队列和栈在线性表的两端都允许插入或者删除数据元素 C 命题整体感知 尝试与研析 【解析】 选项A，栈也可以用数组存储，选项错误；选项B，栈顶元素是最晚进入的元素，选项错误；选项D，栈只允许在栈顶处进行插入与删除，队列在队尾进行插入，队首进行删除，选项错误。 命题整体感知 尝试与研析 2． 设某个栈入栈顺序为“1，2，3，4，5”，则出栈顺序不可能是(　　) A．1，2，3，4，5 B．5，4，3，2，1 C．3，2，1，4，5 D．3，4，5，1，2 【解析】 根据栈的元素入栈和出栈特点，依次输入1，2，3后(入栈)，3出栈，输入4(入栈)，4出栈，输入5(入栈)，5出栈，栈底到栈顶剩下1，2，依次出栈顺序为2，1，所以选项D的出栈顺序不可能。 D 命题整体感知 尝试与研析 3．有如下Python程序段： st＝[0]*10 top＝－1 num＝int(input(＂请输入一个整数：　＂)) while num>0： top＋＝1 st[top]＝num%8 命题整体感知 尝试与研析 num＝num//8 while top>－1： print(st[top]，end＝＂＂) top－＝1 若输入“126”，执行该程序段后，则输出的结果是(　　) A．126 B．621 C．176 D．671 C 命题整体感知 尝试与研析 【解析】 程序利用栈实现将十进制数转换为八进制数的功能，127转换为八进制数的结果为176，选项C正确。 命题整体感知 尝试与研析 4．2023·学军中学检测有如下Python 程序段： s＝input(”请输入字符串s：　”) k，ch＝1，s[0] for i in range(1，len(s))： if k＝＝0： ch＝s[i] k＝1 命题整体感知 尝试与研析 else： if ch＝＝s[i]： 　　 k＋＝1 else： k－＝1 print(ch) 命题整体感知 尝试与研析 若输入字符串s 分别为以下四个选项的内容，执行该程序段后，ch 的值不为“A”的是(　　) A．AAQAQ B．AQRQA C．QAQQA D．RQQAA 【解析】 利用栈的思维找不同，当栈空时，更新ch的值；当ch与s[i]相等，入栈，不相等则出栈；选项C，初始ch＝”Q”，先遇到”A”，k＝0， 更新ch＝”Q”；再遇到”Q”，k＝2；遇到”A”，k＝1，最终ch＝”Q”，选项C符合题意。 C 命题整体感知 尝试与研析 5． 有如下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) 执行该程序段后，输出的结果不可能是(　　) A．12 B．14 C．15 D．21 【解析】 根据a[i]>s[top]，从栈底到栈顶的元素是一个降序序列。n 的范围是[5，7]，前5 个元素构建的降序序列是8，4，和为12；前6 个元素构建的降序序列是8，4，3，和为15；前6 个元素构建的降序序列是8，6，和为14；不可能的结果是21，选项D符合题意。 D 感谢聆听，再见！ whileand i<len(s)： st[top]＝s[i] i＋＝1 while top！＝－1： m＋＝st[top] print(”密文：　”，m) $$