Promacanthus

0.1. 实现栈
0.2. 动态扩容
0.3. 栈的应用

后进者先出，先进者后出，这就是典型的“栈”结构。

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据

从功能上来说，数组或链表确实可以替代栈，但特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选“栈”这种数据结构。

0.1. 实现栈

栈主要包含两个操作:

入栈：在栈顶插入一个数据
出栈：从栈顶删除一个数据

栈既可以用数组来实现，也可以用链表来实现。

用数组实现的栈，我们叫作顺序栈
用链表实现的栈，我们叫作链式栈

不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的数组就够了。

入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
入栈和出栈过程中，只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

注意，存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

0.2. 动态扩容

顺序栈在初始化时需要事先指定栈的大小
链式栈大小虽然不受限制，但是存储next指针，内存消耗相对较多

数组动态扩容：当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。

如果要实现一个支持动态扩容的栈，只需要底层依赖一个支持动态扩容的数组就可以了。实际上，支持动态扩容的顺序栈，平时开发中并不常用到。此时出栈的时间复杂度是O（1），入栈的时间复杂度分为有空间O(1)和需要扩容O(n)，入栈的均摊时间复杂度为O(1)。

0.3. 栈的应用

0.3.1. 栈在函数中的应用

栈比较经典的一个应用场景就是函数调用栈。

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

func main() {
 a, ret, res := 1, 0, 0
 ret = add(3, 5)
 res = a + ret
 fmt.Printf("%d", res)
}

func add(x, y int) int {
 sum := 0
 sum = x + y
 return sum
}

上面代码mian()函数调用add()函数，获取计算结果，并且与临时变量a相加，最后打印res的值。在执行add()函数时，函数调用栈的情况如下图：

0.3.2. 栈在表达式求值中的应用

编译器通过两个栈实现表达式求值，其中一个栈保存操作数，另一个栈保存运算符。

从左向右遍历表达式
当遇到数字，直接压入操作数栈
当遇到运算符，就与运算符栈的栈顶元素比较
1. 如果比栈顶元素优先级高，就将当前运算符压入栈
2. 如果比栈顶元素优先级低或相同，从运算符栈中取栈顶元素，从操作数栈中取两个操作数，进行计算
把计算结果压入栈操作数栈
继续

如下示例为计算3+5*8-6：

0.3.3. 栈在括号匹配中的应用

假设表达式中只包含三种括号：

圆括号()
方括号[]
花括号{}

它们可以任意嵌套。

比如：

合法格式：{[] ()[{}]}或[{()}([])]等
不合法格式：{[}()]或[({)]等

用栈来判断一个包含三种括号的表达式字符串是否合法。

用栈来保存未匹配的左括号，从左到右依次扫描字符串。
当扫描到左括号时，则将其压入栈中；
当扫描到右括号时，从栈顶取出一个左括号。
1. 如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。
2. 如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

0.3.4. 栈在浏览器中的应用

使用两个栈实现浏览器中前进后退的功能，假设两个栈分别为X和Y。

把首次浏览的页面压入栈X
当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次压入栈Y中
当点击前进按钮时，再依次从栈Y中出栈，并将出栈的数据依次压入栈X中
当X中没有数据，说明没有可以继续后退浏览的页面
当Y中没有数据，说明没有可以继续前进浏览的页面