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

第三章 字符串、队列和栈 选修1《数据与数据结构》 3.3 栈 学习目标 栈 栈的概念与特性 栈的基本操作 栈的概念和特性 栈是一种操作受限的线性表，仅允许在表的一端进行插入或删除。 ·栈的概念 ·栈的特性 （1）先进后出、后进先出 （2）有限序列性 栈是一种线性表结构，元素个数有限。栈可以为空。 栈 栈底元素 栈顶元素 ·栈的链式存储结构（链栈） 栈的基本操作 ·栈一般按顺序结构存储的，可以用数组来实现，而在Python语言中，可以用列表实现。 a1 a2 a3 a4 0 1 2 3 栈底： D C B A ^ 栈 top a4 a3 a2 a1 栈顶： top=3 栈结构 数组st的下标： 数组存储栈 top=3 ·建栈 栈的基本操作 top = -1 st = [“”] * 4 栈 3 2 1 0 空栈 下标 top=-1 ·入栈（又称压栈操作） 栈的基本操作 top = -1 st = [“”] * 4 top +=1 st[top] = “A” 栈 3 2 1 0 空栈 下标 top=-1 3 2 1 0 A 下标 top 3 2 C 1 B 0 A 下标 top 3 D 2 C 1 B 0 A 下标 top 满栈 top +=1 st[top] = “B” top +=1 st[top] = “C” top +=1 st[top] = “D” 代码： ·出栈 栈的基本操作 栈 3 2 1 0 空栈 下标 top=-1 3 2 1 0 A 下标 top 3 2 C 1 B 0 A 下标 top 3 D 2 C 1 B 0 A 下标 top 满栈 ·栈的入栈和出栈 栈的基本操作 st = [""] * 6 top = -1 # 元素依次入栈 for i in "ABCDEF": top += 1 st[top