文档文本内容
本节内容
顺序栈
的实现
王道考研/CSKAOYAN.COM知识总览
创、销、增、删、改、查
王道考研/CSKAOYAN.COM顺序栈的定义
内存
top = 4 top(4B)
data[9]
data[8]
data[7]
data[6]
Sq:sequence —— 顺序 data[5]
top 指向栈顶元素 top e
data[4]
d
data[3]
顺序存储:给各个数据 c
data[2]
元素分配连续的存储空
b
data[1]
间,大小为
a
data[0]
MaxSize*sizeof(ElemType)
王道考研/CSKAOYAN.COM初始化操作
内存
top = -1 top
data[9]
data[8]
data[7]
data[6]
data[5]
data[4]
data[3]
data[2]
data[1]
data[0]
top
增删改查
王道考研/CSKAOYAN.COM进栈操作
内存
top = 1
top = 0
top = -1 top
data[9]
data[8]
data[7]
data[6]
data[5]
data[4]
等价
data[3]
data[2]
b
data[1]
a
data[0]
注意:错误写法!
top
王道考研/CSKAOYAN.COM进栈操作
内存
top = 9
top
top dat k a[9]
j
data[8]
i
data[7]
h
data[6]
g
data[5]
f
data[4]
等价
e
data[3]
c
data[2]
b
data[1]
a
data[0]
王道考研/CSKAOYAN.COM出栈操作
内存
top = 8
top = 9
top
top dat k a[9] 数据还残留
在内存中,
j
data[8]
只是逻辑上
dat i a[7] 被删除了
h
data[6]
g
data[5]
f
data[4]
等价
e
data[3]
c
data[2]
b
data[1]
a
data[0]
注意:错误写法!
k
x
王道考研/CSKAOYAN.COM读栈顶元素操作
内存
top = 8 top
data[9]
top j
data[8]
i
data[7]
h
data[6]
g
data[5]
f
data[4]
e
data[3]
唯一区别 c
data[2]
b
data[1]
a
data[0]
x
王道考研/CSKAOYAN.COM另一种方式
内存
top = 0
top(4B)
data[9]
data[8]
data[7]
data[6]
data[5]
初始指向 0
data[4]
data[3]
data[2]
空栈
data[1]
top
data[0]
王道考研/CSKAOYAN.COM另一种方式
内存
top = 5
top(4B)
data[9]
data[8]
top 指向下一个
等价 data[7]
可以插入的位置
data[6]
进栈
top
data[5]
e
data[4]
✅
d
data[3]
c
data[2]
出栈
b
data[1]
a
data[0]
栈满的条件:top == MaxSize
注意审题 啊喂!
顺序栈的缺点:
栈的大小不可变
王道考研/CSKAOYAN.COM共享栈
内存
两个栈共享同一片空间
top1
1
data[9]
2
data[8]
3
data[7]
g
data[6]
f
data[5]
e
data[4]
d
data[3]
c
data[2]
b
data[1]
a
data[0]
top0
栈满的条件:top0 + 1 == top1
王道考研/CSKAOYAN.COMtop=-1
知识回顾与重要考点 销? —— 清空、回收
声明栈时
分配内存
都是 O(1) 时间复杂度
函数运行结束后系
统自动回收内存
王道考研/CSKAOYAN.COM