3-3栈 课件-2021-2022学年浙教版（2019）高中信息技术选修1
|
13页
|
1685人阅读
|
37人下载
特供
内容正文：
第三章 字符串、队列和栈
选修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
资源预览图
