一、栈结构：先进后出，后进先出

使用场景：某个数据集合只涉及一端插入和删除数据，并且满足先进后出，后进先出

二、实现一个栈

通过数组实现——顺序栈
空间复杂度O(1)，时间复杂度O(1)
通过链表实现——链式栈

三、支持动态扩容的顺序栈

image.png

四、栈的应用-函数调用栈

  1. int main() {
  2.    int a = 1; 
  3.    int ret = 0;
  4.    int res = 0;
  5.    ret = add(3, 5);
  6.    res = a + ret;
  7.    printf("%d", res);
  8.    reuturn 0;
  9. }
  11. int add(int x, int y) {
  12.    int sum = 0;
  13.    sum = x + y;
  14.    return sum;
  15. }

image.png

五、栈的应用-实现表达式求值

编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

例：下图展示了四则运算：3+5*8-6的计算过程：
image.png

六、栈的应用-用栈检查表达式中的括号是否匹配

题目：已知一个表达式中只包含三种括号，圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。那我现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？
解题思路：用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。