数据结构与算法之美-栈

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

1. 栈的概念

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，有一个特性：后进先出，先进后出。

image.png

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

2. 栈的实现

栈主要包括入栈和出栈两个操作，可以用数组实现，也可以用链表实现。用数组实现的栈为顺序栈，用链表实现的栈为链式栈。

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

如果用数组来实现支持动态扩容的栈，底层只需要依赖一个支持动态扩容的数组就可以了，当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中：

image.png

3. 栈的应用

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

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

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

从代码中可以看出，main()函数调用了 add()函数，获取计算结果，并且与临时变量 a 相加，最后打印 res 的值，下图是执行到 add()函数时，函数调用栈的情况：

image.png

• 用于表达式求值
  比如：34+13*9+44-12/3。编译器就是通过两个栈来实现的，其中一个栈保存操作数的栈，另一个是保存运算符的栈，我们从左向右遍历表达式，遇到数字就压入操作数栈，遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级要高，就将当前运算符压入栈，如果比运算符栈顶元素的优先级低或者相投，就从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较，如下图：

image.png

• 括号匹配中的应用
  假设表达式中只包含三种括号：() [] {}，并且可以任意嵌套，比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。
  检查是否合法也可以用栈来解决，用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，将其压入栈中，当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
  当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

4. 总结

栈是一种操作受限的数据结构，只支持入栈和出栈，后进先出是最大特点。
可以用链表或者数组来实现，入栈、出栈的时间复杂度都为 O(1)。

5. 练习操作

• 栈的基本实现
• 用栈实现求表达式的值
• 实现括号匹配验证