引入
今天,我们开始讲一种特殊的线性表,栈。既然是特殊的线性表,那么有哪些不一样的呢?我们一起来看看!
从弹夹说起
下面的图片是一个弹夹
我们知道,如果子弹没有了,那么我们需要一颗一个的将子弹装入弹夹
- 第一颗被装入的子弹在弹夹的最上方
- 第二颗则压在第一颗的上方,循环往复,直到装满
- 此时如果我们要射击,最上面的一颗子弹会首先被发射出去
- 然后弹夹下面的弹簧会将压在下面的子弹顶上来
也就是说,最后被装入的子弹,最先被发射出去。我们将这种情况称之为后进先出
。
栈的定义
栈,是一个后进先出
(Last in First out) 的线性表,我们也称后进先出为LIFO
,它要求只在表尾
进行删除和插入操作。
栈是一种重要的线性结构
,可以说,栈是前面讲过的线性表的一种具体形式,也是一种特殊的线性表:
- 栈的元素必须
后进先出
- 栈的操作只能在这个线性表的
表尾进行操作
。 - 我们称表尾为栈的栈顶(Top)操作的为顶
- 我们称表头为栈的栈底(Bottom)不能操作的为底
栈的插入和删除
我们把栈的操作称之为(Push),类似压子弹,叫做进栈、压栈、入栈。
我们把栈的删除称之为(Pop),类似子弹发射,叫做出站、弹栈。
栈的顺序存储结构
因为栈说到底其实是一个线性表,线性表有两种存储形式,即顺序和链式。栈也分为顺序存储和链式存储两种。
而我们一般情况下使用的是栈的顺序存储结构。
- 开始时,栈内没有任何数据,称之为
空栈。
- 空栈时,栈底就是栈顶。
- 进栈时,从栈顶(表尾)进入,栈顶栈底分离,栈的容量变大。
- 出栈时,从栈顶(表尾)弹出,栈顶下移,栈的容量变小。
定义栈的结构体
定义一个顺序存储结构的栈的结构体,结构体包含三个元素
- base,是指向栈底的指针。
- top,是指向栈顶的指针。
- StackSize,存储着
当前可使用的
最大容量。
1 | struct Stack{ |
创建一个栈
我们来创建一个空栈
1 |
|
其实重要的就几点
- 申请的空间是最大容量倍的类型长度
- 栈顶一开始就是栈底
- 记得把可用容量标记好
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。