栈　　课件　 【核心知识精讲精析】 浙教版（2019）高中信息技术选修1

3.3栈新课导入装置只有一端是开放的，所有的操作都只能在这开放的一端进行。数据具有“先进后出、后进先出”的特征，可采用“栈”这种数据结构。栈栈是一种后进先出的线性表，仅允许在表的一端进行插入或删除操作。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；另一端称为栈底，位于栈底位置的元素称为栈底元素。栈顶元素栈底元素栈的特性先进后出、后进先出有限序列性元素的个数是有限的，栈可以为空，也可包含多个元素。栈中元素呈现线性特征，栈顶元素有一个前驱点，栈底元素有一个后继点，其它元素既有一个前驱点又有一个后继点。栈顶元素栈底元素牛刀小试1.有六个元素按照6,5,4,3,2,1的顺序依次进栈，则出栈顺序不可能是（）5,4,3,6,1,24,5,3,1,2,63,4,6,5,2,12,3,4,1,5,62.一个栈的入栈序列是1,2,3,4,5，其出栈序列为s1,s2,s3,s4,s5，若s2是3，则s1不可能是（）A.1B.2C.4D.5CD栈的创建：数组创建栈一般按照顺序结构存储，可以使用数组来实现。栈顶元素在数组中的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位置。栈的创建：链表创建栈的链式存储称为链栈，设置栈顶指针top为链栈的头指针。特点：克服了用数组实现的顺序栈空间利用率不高的缺点，但要为每个栈元素分配额外的指针空间。栈操作（建栈\入栈IN\出栈OUT）例：有5个字母“a”“b”“c”“d”“e”按序入栈，可创建长度为5的栈st：初始为空串，

栈顶指针top设置为-1代码示例：top=-1st=[“”]*5栈按顺序结构存储，通过数组实现，所以Python可使用列表创建栈栈操作（建栈\入栈IN\出栈OUT）栈顶指针top记录栈顶元素的位置，初始值为-1，进栈一个元素，top指针加1，即st[top]=栈顶元素栈操作（建栈\入栈IN\出栈OUT）top=-1#初始值top=top+1 #top=0st[top]=”a”#a入栈，top指向a的位置top=top+1 #top=1st[top]=”b”#b入栈，top指向b的位置top=top+1 #top=2st[top]=”c”#c入栈，top指向c的位置top=top+1 #top=3st[top]=”d”#d入栈，top指向d的位置top=top+1 #top=4st[top]=”e”#e入栈，top指向e的位置栈操作（建栈\入栈IN总结\出栈OUT）停止入栈的条件是什么？st=[“”]*5top=-1while______________top+=1st[top]=“*”top<len(st):栈操作（建栈\入栈IN\出栈OUT）出栈，排在栈顶的元素依次出栈，top指针变量依次减1，直至top的值等于-1栈操作（建栈\入栈IN\出栈OUT）top=4#初始值st[top]=””#e出栈top=top-1 #top=3，top指向d的位置st[top]=””#d出栈top=top-1 #top=2，top指向c的位置st[top]=””#c出栈top=top-1 #top=1，top指向b的位置st[top]=””#b出栈top=top-1 #top=0，top指向a的位置st[top]=””#a出栈top=top-1 #top=-1，栈空停止出栈的条件是什么？top=len(st)-1while____________print(st[top])st[top]=“”top-=1top!=-1:栈应用1：十进制数转换为二进制数算法思想：1）用栈结构存放每次获得的余数2）根据栈特征输出每次获得的余数st=[0]*100#初始值为0top=-1num=int(input(“输入十进制数”))whilenum!=0:___________________________#将余数放入栈num=num//2whiletop!=-1:print(st[top],end=“”)______________________________top+=1st[top]=num%2st[top]=“”top-=1括号匹配将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列3种情况：栈空，出现右括号，不匹配。扫描结束，栈中还有左括号，不匹配。扫描结束，栈空，匹配。数据合并问题程序备注st=[""]*100#初始化

top=-1#初始化为空栈

flag=True#标记是否有不匹配的情况

s=input("请输入数学表达式：")初始化各项数据foriinrange(len(s)):

ifs[i]=="(":#左括号入栈

top+=1

st[top]=s[i]

elifs[i]==")":#右括号与栈顶元素比较

iftop==-1:

flag=False

break

else:

top-=1从左往右逐步处理数学表达式：若为左括号则入栈；若为右括号则与栈顶指针进行匹配。数据合并问题程序备注iftop>0:#栈中还有剩余元素

flag=False栈中还有剩余元素，即左括号数量大于右括号。ifflag:

print("括号匹配")

else:

print("括号不匹配")请输入数学表达式：(((a+b)*(c-d)-e)/f)括号匹配请输入数学表达式：((a+b)*c)-d)+(e括号不匹配字母A、B、C、D、E、F依次入栈，然后依次出栈并输出foriin"ABCDEF":

top+=1

st[top]=i

whiletop>-1:

print(st[top],"出栈")

top-=1st=[]

foriin"ABCDEF":

st.append(i)

print(len(st))

foriinrange(len(st)):

print(st.pop(),"出栈“)用列表自带函数和方法实现栈逆波兰表达式逆波兰表达式（后缀表达式）：将运算符置于其运算对象之后，没有括号，无需考虑运算符号的优先级。中缀表达式转后缀表达式：表达式中加入括号；将所有运算符移到对应括号的右边；删除所有的括号。逆波兰表达式计算：从左往右扫描逆表达式，遇到数字入栈；遇到运算符号，将栈中最上方的两个元素依次出栈并用运算符计算，将计算结果压入栈中。重复上述过程直至表达式扫描结束。表达式第一步第二步第三步a+b*c(a+(b*c))(a(bc)*)+abc*+6+(8-2)*2/3(6+(((8-2)*2)/3))(6(((82