栈与队列
3.1 栈与队列的定义和特点
- 栈，后进先出(LIFO)
- 队列，先进先出(FIFO)
3.2 案例引入
- 数制的转换
- 括号匹配的检验
- 表达式求值
- 舞伴问题
3.3 栈的表示和操作的实现
3.3.1 栈的类型定义
3.3.2 顺序栈的表示和实现
3.3.3 链栈的表示和实现
3.4 栈与递归
3.5 队列的表示和操作的实现
3.6 案例分析与实现
- 数制的转换
- 括号匹配的检验
- 表达式求值
- 舞伴问题
3.7 小结
- 栈是限定仅在表尾进行插入或删除的线性表,又称为后进先出的线性表。
- 队列是一种先进先出的标星标。它只允许在表的一段进行插入，而在另一端删除元素。队列的主要操作是进队和出队，对于顺序的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXSIZE求模。
- 栈与队列是在程序涉及中被广泛使用的两种数据结构，其具体的应用场景都是与其表示方法和运算规则相互联系的。
- 栈有一个重要应用是在程序设计语言中实现递归
易错点
- 循环队列中对长度进行计算，队尾的下标应该始终大于队首的下标
- 中缀表达式转后缀表达式
- 王道的方法，对符号的优先级进行划分，分为isp（栈内优先），和icp（栈外优先），“+-*/”等符号栈内优先级更高。优先级高的元素出栈，优先级低的元素进栈，当isp=icp时，直接退栈，相当于两个元素相消（推荐）
- 自己的方法，只对“+-*/”符号标记优先级，并且不区分isp和icp，当icp<=isp时，栈顶输出，否则入栈，对“#(”等符号进行特殊处理（不推荐）
- 王道的方法，对符号的优先级进行划分，分为isp（栈内优先），和icp（栈外优先），“+-*/”等符号栈内优先级更高。优先级高的元素出栈，优先级低的元素进栈，当isp=icp时，直接退栈，相当于两个元素相消（推荐）
