图解 | 不就是栈吗
你好，我是微木。
今天分享的内容是栈这种数据结构，主要内容有：
- 栈的定义及应用
- 顺序栈的介绍及实现
- 链式栈的介绍及实现
- 顺序栈与链式栈的简单比较
- 栈在字符串比较，表达式求值中的应用
01
栈的定义及应用
栈（stack）是一种先进后出，后出先进的数据结构。之所以这样，是因为栈是操作受限的线性表，允许元素进出的一端称为 栈顶（top），不允许元素进出的一端称为 栈底（bottom）。
栈的操作一般有两种，一是 入栈（push），即将元素放入栈中；另一个操作是 出栈（pop），即从栈中取出元素。
我们说栈是一种操作受限的线性表，只能在一端对元素进行操作，那么栈这种数据结构有哪些应用场景呢？
其实，我们上网时用到的浏览器的后退查看历史记录功能，在Word文档中撤销当前操作这个功能都是栈这种数据结构的具体应用场景。
02
顺序栈的介绍及实现
我们把用数组（关于数组的介绍可以看 浅谈数组 这篇文章）来实现的栈称为顺序栈，由于入栈、出栈这些操作都是在栈顶这一端完成的。因此，在用数组实现栈时，需要思考的一个问题就是：
是把索引为0的一端作为栈顶呢？还是作为栈底呢？
如果把索引为0的一端作为栈顶，那么元素入栈，即向数组索引为0的位置增加元素时，需要把之前的元素向后移动一个位置。同理，元素出栈，即删除索引为0的元素时，需要把之后的元素向前移动一个位置。这就增加了操作的时间复杂度。
因此，应该把索引为0的一端作为栈底，这样不论是元素入栈，还是元素出栈，都不需要移动其它元素，这时其时间复杂度是O(1)。
基于简单数组的实现
基于简单数组的实现，代码如下：
元素入栈的动画演示如下：
元素出栈的动画演示如下：
基于动态数组的实现
基于简单数组实现的栈，存在一个弊端，就是在初始化时，数组的容量已经确定了，这样当数组满时，元素就无法入栈了。
为了解决这个问题，可以用动态数组来实现栈。所谓动态数组，就是在数组容量达到其最大容量时，对其进行扩容，在这里扩容为之前的2倍。然后，将原数组中的元素依次拷贝至扩容后的数组内，动画演示如下：
相比较于基于简单数组的实现，基于动态数组的实现，代码的主要变化是在元素入栈时，增加了是否需要扩容的判断，如果当前数组中元素个数等于数组容量，则扩容为之前容量的2倍，代码实现如下。
此时，基于动态数组实现的栈，其元素入栈这个操作的时间复杂度是多少呢？
上述代码中的push方法是每次向数组末尾添加一个元素，然后当数组满时，进行扩容，扩容为原有数组的2倍；resize方法是用于扩容的，所谓的扩容就是新开辟一个容量大小为newCapacity的数组，然后将原数组的元素依次复制到新数组中，这个操作的时间复杂度T(n)=O(n)。
接着看下push方法的时间复杂度。对于push这个方法来说，其中有两个操作，一个是向数组末尾添加元素，每次执行添加操作时，时间复杂度是O(1)；一个是扩容，每次扩容的时间复杂度是O(n)。那么，push方法的时间复杂度是O(n)吗？
扩容这一步，是在数组满的情况下才会触发执行，也就是在扩容之前，会有n次向数组末尾添加元素的操作，且每次操作耗时是1，总耗时为n。扩容操作在数组满时触发一次，耗时是n，即将数组添加满并进行扩容总共需要n+1次操作，这些操作总耗时是2n。
因此，在将扩容这个操作的耗时 均摊到之前每次添加元素到数组末尾这个操作上时，每次操作耗时约为2，即将数组添加满并进行扩容操作，其时间复杂度不是O(n)，而是O(1)。关于时间复杂度的更多内容可以查看 满满的一篇，全是复杂度分析核心知识点 这篇文章。
03
链式栈的介绍及实现
我们把用链表（关于链表的更多介绍可以查看 数据结构 #2 36张图带你深刻理解链表 这篇文章）实现的栈称为链式栈。
对于链表而言，我们只知道其头节点，因此在用链表实现栈时，应该把链表的头节点作为栈顶，这样不论是元素入栈，即增加节点至链表头部，还是元素出栈，即删除链表头节点，其时间复杂度都是O(1)。
基于链表实现的栈，代码如下：
元素入栈——增加节点至链表头部，动画演示如下：
元素出栈——删除链表头节点，动画演示如下：
04
顺序栈与链式栈的简单比较
在时间复杂度方面，顺序栈与链式栈不论是元素入栈还是元素出栈，其时间复杂度都是O(1)。
在空间性能方面，顺序栈由于需要事先确定一个固定容量，因此，可能会有空间浪费的问题；链式栈，虽然不需要事先确定固定容量，但是每个元素都有一个指针域，因此增加了内存开销。
在使用时，如果元素数量变化是不可预测的，建议使用链式栈；如果元素数量在可控范围内，那么建议使用顺序栈。
05
栈在字符串比较，表达式求值中的应用
我们通过LeetCode中的两道题目来看下栈的简单应用，题目有：
- LeetCode #844 比较含退格的字符串
LeetCode #150 逆波兰表达式求值
LeetCode #150 逆波兰表达式求值
栈在字符串比较中的应用
题目描述：
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
示例:
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
思路分析:
该题目用栈求解的思路是：
首先遍历每个字符。
然后，如果当前考察的字符不是退格符#，则将其入栈；如果当前考察的字符是退格符#，则将栈顶元素出栈。
最后，比较栈中的字符转换为字符串之后是否相等。
动画演示：
代码实现：
栈在表达式求值中的应用
题目描述：
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
示例:
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
思路分析:
该题目用栈求解的思路是：
首先，对于给定的字符串数组进行遍历，对每个元素进行考察。
然后，如果当前考察的元素不属于+、 -、*、/，则将其入栈；如果当前考察的元素属于+、 -、*、/，则将栈顶元素及其后面一个元素出栈。接着，将出栈的两个元素进行表达式求值运算，并将计算结果入栈。
最后，当字符串数组中的所有元素考察完毕时，将栈顶元素出栈，就是最终计算结果。
动画演示：
代码实现：
今天的分享就到这里了
如有错误
欢迎在公众号后台留言指出
下一篇我们将学习新的内容，敬请期待 返回搜狐，查看更多
责任编辑：