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

第三章字符串、队列和栈

选修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#元素依次入栈foriin"ABCDEF":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=[]foriin"ABCDEF":st.append(i)print(st)whilest:print(st.pop(),end="")

栈

输出结果：['A','B','C','D','E','F']FEDCBA

·十进制转二进制

栈的基本应用st=[-1]*100top=-1number=int(input("请输入十进制整数："))whilenumber>0: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

·思考

栈的基本应用

栈

如何把计算表达式转化成