算法一看就懂之“堆栈”

上一篇咱们聊完了数据结构中最基础的「 数组 」和「 链表 」，今天咱们再来继续看看「 堆栈 」吧，我写技术文章很少 show code，所以经常有人吐槽。好吧，这个算法系列的文章我打算每一篇的结尾处都找一道算法题写出代码示例，这总可以了吧。

一、「 堆栈 」是什么？

堆栈（stack）是一种先进后出的、操作受限的线性表，也可以直接称为栈。

可以把栈想象成一个桶一样，往这个桶里面一层一层的放东西，先放进去的在里面，后放进去的东西依次在外面。但取东西的时候就是先取靠近外面的，再依次一层层取里面的。这就是 后进先出（ Last In-First Out ）的原则。

因此「 栈 」虽然是线性的，有2个端：顶端和底端，但它只允许从一端进行插入和删除数据，这就是为啥前面说「 栈 」是操作受限的了。

栈只有两种操作：Push 和 Pop 。我们用Push（压入）来表示往栈中插入数据，也叫入栈，用Pop（弹出）来表示从栈中删除数据，也叫出栈。我们可以既可以用 「 数组 」 来实现一个栈，也可以用 「 链表 」 来实现一个栈。

用数组实现的栈，叫做顺序栈：

顺序栈的实现非常简单，这里就不写代码了，写一下思路。先初始化一个数组，然后再用一个变量给这个数组里的元素进行计数，当有新元素需要入栈的时候，将这个新元素写入到数组的最后一个元素的后面，然后计数器加一。当需要做出栈操作时，将数组中最后一个元素返回，计数器减一。

当然在入栈前需要判断数组是否已经满了，如果数组大小等于计数器大小，则表明数组是满的。

出栈的时候也需要判断数组是不是空数组，如果计数器是0，则表明数组是空的。

从上面的实现流程可以看出，通过数组实现的栈，其入栈和出栈都是对单个元素进行操作，因此其入栈和出栈的时间复杂度都是O(1)，并且其入栈和出栈操作并没有额外开销更多空间，因此其空间复杂度也是O(1)的。

用链表实现的栈，叫做链式栈：

实现思路是先定义一个链表节点的类，基于这个类去定义一个头节点Head。当有新元素需要入栈的时候，将这个新元素的Next指针指向头结点Head的Next节点，然后再将Head的Next指向这个新节点。当需要做出栈操作时，直接将Head所指向的节点返回，同时让Head指向下一个节点。

当然，在入栈和出栈时都需要判断链表是否为空的情况。

链式栈的入栈和出栈都是在处理头部节点，所以操作很简单，其时间和空间复杂度均为O(1)。

二、「 堆栈 」的算法实践？

我们来看一个基于用栈来完成的算法题（来源leetcode）：

以上，就是对数据结构中「 堆栈 」的一些思考。

码字不易啊，喜欢的话不妨转发朋友，或点击文章右下角的“在看”吧。

本文原创发布于微信公众号「 不止思考 」，欢迎关注。涉及 思维认知、个人成长、架构、大数据、Web技术 等。