浙江大学数据结构（2.2.1什么是堆栈）
堆栈
计算机如何进行表达式求值？
- 有两类对象构成的：
- 运算数
- 运算符号
- 不同的运算符号优先级不一样
后缀表达式
- 中缀表达式：运算符号位于两个运算数之间，如：a+b*c-d/e
- 后缀表达式：运算符号位于两个运算数之后，如：abc*+de/-
[例]
6 2 / 3 - 4 2 * + = ？8
- 6 2 /（3）
- 3 3 - （0）
- 4 2 * （08）
- 0 8 + （8）
后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号
- 遇到运算数怎么办？如何“记住”目前还不未参与运算的数？
- 遇到运算符号怎么办？对应的运算数是什么？
启示：需要有种存储方法，能顺序存储运算数，并在需要时“倒序”输出~（先进后出）
- T（n）=O（n）
堆栈的抽象数据类型描述
堆栈（Stack）：具有一定的操作约束的线性表
- 只在一端（栈顶，Top）做插入、删除
- 插入数据：入栈（Push）
- 删除数据：出栈（Pop）
- 后入先出：Last In First Out（LIFO）
- Push和Pop可以穿插交替进行