3-3栈-课件-2021-2022学年浙教版（2019）高中信息技术选修1.pptx

第三章字符串、队列和栈选修1《数据与数据结构》3.3栈

学习目标栈栈的概念与特性栈的基本操作

栈的概念和特性栈是一种操作受限的线性表，仅允许在表的一端进行插入或删除。·栈的概念·栈的特性（1）先进后出、后进先出（2）有限序列性栈是一种线性表结构，元素个数有限。栈可以为空。栈栈底元素栈顶元素

·栈的链式存储结构（链栈）栈的基本操作·栈一般按顺序结构存储的，可以用数组来实现，而在Python语言中，可以用列表实现。a1a2a3a40123栈底：DCBA^栈topa4a3a2a1栈顶：top=3栈结构数组st的下标：数组存储栈top=3

·建栈栈的基本操作top=-1st=[“”]*4栈3210空栈下标top=-1

·入栈（又称压栈操作）栈的基本操作top=-1st=[“”]*4top+=1st[top]=“A”栈3210空栈下标top=-13210A下标top32C1B0A下标top3D2C1B0A下标top满栈top+=1st[top]=“B”top+=1st[top]=“C”top+=1st[top]=“D”代码：

·出栈栈的基本操作栈3210空栈下标top=-13210A下标top32C1B0A下标top3D2C1B0A下标top满栈

·栈的入栈和出栈栈的基本操作st=[]*6top=-1#元素依次入栈foriinABCDEF:top+=1st[top]=i#元素依次出栈，直至栈为空whiletop-1:print(st[top],end=)top-=1栈输出结果：FEDCBA

·列表自带的方法实现栈栈的基本操作·建立空栈：stacklist=[]·入栈：stacklist.append(“A”)·出栈：stacklist.pop()·输出栈顶元素：print(stacklist[len(stacklist)-1])print(stacklist[-1])·输出栈中元素个数：print(len(stacklist))栈

·列表自带的方法实现栈的入栈和出栈栈的基本操作st=[]foriinABCDEF:st.append(i)print(st)whilest:print(st.pop(),end=)栈输出结果：[A,B,C,D,E,F]FEDCBA

·十进制转二进制栈的基本应用st=[-1]*100top=-1number=int(input(请输入十进制整数：))whilenumber0:x=number%2top+=1st[top]=xnumber=number//2whiletop=0:print(st[top],end=)top=top-1栈输出结果：请输入十进制整数：1001100100

·逆波兰表达式的计算栈的基本应用str=input(请输入逆波兰表达式：)stack=[]foriinstr.split():ifiin+-*/:s2=stack.pop()s1=stack.pop()#eval函数执行一个字符串表达式，并返回表达式的值。该返回值为字符串stack.append(eval(%s%s%s%(s1,i,s2)))else:stack.append(i)print(result：%s%stack[0])栈输出结果：请输入逆波兰表达式：682-2*3/+result：10.0

·思考栈的基本应用栈如何把计算表达式转化成逆波兰式，然后计算其值。例如：计算表达式：6+(83-2)*2/3逆波兰式：6832-2*3/+表达式的值：60.0