栈　课件-浙教版（2019）高中信息技术选修1

XX中学栈新课导入装置只有一端是开放的，所有的操作都只能在这开放的一端进行。数据具有“先进后出、后进先出”的特征，可采用“栈”这种数据结构。栈栈是一种后进先出的线性表，仅允许在表的一端进行插入或删除操作。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；另一端称为栈底，位于栈底位置的元素称为栈底元素。栈顶元素栈底元素栈的特性先进后出、后进先出有限序列性元素的个数是有限的，栈可以为空，也可包含多个元素。栈中元素呈现线性特征，栈顶元素有一个前驱点，栈底元素有一个后继点，其它元素既有一个前驱点又有一个后继点。栈顶元素栈底元素牛刀小试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为链栈的头指针。特点：克服了用数组实现的顺序栈空间利用率不高的缺点，但要为每个栈元素分配额外的指针空间。建栈、入栈、出栈栈以数组形式存储，因此Python中用列表创建栈。为了操作方便，把指向栈顶元素的指针变量top值设置为-1。创建长度为6，初始值为空串的空栈st字母A、B、C、D、E、F依次入栈，然后依次出栈并输出st=[""]*6

top=-1foriin"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(),"出栈“)括号匹配将表达式中数字和运算符号忽略，直接判断左右括号的数量和位置是否匹配，判断过程用栈结构来实现：若出现左括号则进栈，右括号则把栈顶的左括号出栈，判断是否匹配，分下列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(a+(b*c))(a(bc)*)+abc*+6+(8-2)*2/3(6+(((8-2)*2)/3))(6(((82)-2)*3)/)+682-2*3/+a/b-c+d*e-a*c((((a/b)-c)+(d*e))-(a*c))((((ab)/c)-(de)*