『stack』(堆栈)，又称为「栈」或「堆叠」，FILO(先进后出)。栈也是线性表，只允许在一端进行插入或删除的线性表。
『top』栈顶。

顺序栈

用数组(顺序表)实现栈。一般说的栈都是用数组来实现的。

点击查看

共享栈

点击查看

链式栈

用链式存储实现栈。使用头插、头删法即可实现。实际应用也比较少。

带头结点

不带头结点

点击查看

栈的应用

括号匹配

[刘长途 在 第三章 8节 7分42秒]
[视频代码 在 第三章 8节 8分]

表达式求值

表达式形式

• 中缀表达式
  运算符在中间。

• 前缀表达式(波兰式)

  运算符在前，运算符按中缀表达式，从右往左计算。

• 后缀表达式(逆波兰式)[重点]

  运算符在后，运算符按中缀表达式，从左往右计算。

表达式相互转换

递归

函数调用栈。