栈

栈 Stack

可用向量或列表实现，操作均只需 $O(1)$ 时间。

Example

• 系统底层：函数的调用栈

• 括号匹配：最基本的编译器语法检查

• 表达式处理：

  • 表达式求值：双栈，操作数栈和运算符栈
  • 逆波兰表达式求值：单栈

• 数学特性：栈混洗数等于卡特兰数

Advanced

利用栈可以实现一些十分有用的数据结构：

• 单调栈：寻找下一个更大/更小元素
  • 直方图内最大矩形
• 最大栈：用辅助栈记录当前最大值，实现 $O(1)$ 获取最值