手撕408|数据结构之栈 (4)|今天文末有抽奖

手撕408系列之数据结构栈，冷月出品必是精品，大家好，我是学长冷月。关注下方“学长冷月”可获得更多408答题技巧及资料。

当我们学习一个新的数据结构时，一定要从数据结构的三要素出发。逻辑结构、物理结构以及数据的运算。栈的运算就不多说了，无非就是增删改查、初始化、判空等。

逻辑结构

栈是一个先入后出（First In Last Out）的数据结构，也就是说栈只能在一端进行插入或者删除操作。那么我们就可以对栈下一个定义：栈是一个元素只能先入后出的线性表（受限制的线性表）。

栈是一个受限制的线性表，那为什么我们要对它受限制呢？其实栈中的操作，使用数组或者链表其实都可以实现。但是特定的数据结构作用于特定的场景，数组或者链表暴露给用户的接口很多，我们在有些场景不需要给用户太多的接口，而当我们用到一种先入后出的场景时，栈就排上了用场。

我们可以看下面这张图：

假设，上面这个是一个装盘子的桶，一号盘子在最下面，二号盘子在中间，三好盘子上最上面。如果要放入四号盘子，那么只能放在三号盘子的上面；如果要取盘子也只能先取三号盘子。相信大家能看懂这个例子，栈的思想也就是和这个装盘子的过程有相似之处。

最后在补充两个概念：

栈顶指针(top)：允许插入或删除的那一端

栈底指针(buttom)：固定的，不允许插入或删除的那一端

物理结构

栈的本质既然也是线性表，那么它的物理结构肯定既有顺序实现也有链式实现。

顺序实现也叫做顺序栈，其底层实现为数组。结构体的定义如下图所示：

熟悉数组的同学可以看出，这个结构体其实就是对数组加了一个栈顶指针。

其中，真题对于顺序栈的考察较多，我们要注意以下几个概念，用s来代表一个栈的变量：

栈顶指针：s.top

初始化时：s.top = -1

栈顶元素：s.data[s.top]

进栈操作

IF 栈不满  ; s.top ++ ; s.data[s.top] = data;

出栈操作

IF 栈非空  ; data = s.data[s.top]  ; s.top --

栈空

s.top == -1

栈满

s.top == MaxSize -1

当前栈长

s.top + 1

链式实现也叫做链栈，其结构如下图所示：

熟悉链表的同学应该已经看出，链栈类似于没有头结点的一个单链表。用Lhead代表栈顶指针指向首节点，也就是栈顶元素。使用链栈的优点就是方便栈的元素动态的增加，不会出现栈满的情况。其余的操作就和单链表非常类似，冷月就不多讲了。

明天别忘了来做题！

请帮冷月点一下旁边的在看，再点一个赞,一键三连支持一下！您的每一次点击都是对冷月莫大的鼓励，谢谢！！

点击下面图片即可参加61冷月宠粉福利，一键三连就不用我多说了吧！