栈和队列

day17

a 栈的接口与实现

a1 栈

a2 实例

LIFO:后进先出

a3 实现

上图为基于向量模拟实现栈，其中入栈、出栈操作都是在向量末尾完成，复杂度是O（1），如果在向量首部实现入栈、出栈的话，复杂度就会变成O（n）

c

c1-1 栈的典型应用

栈的典型应用场合

c1-2 进制转换算法

计算过程自上而下，输出结果，自下而上，可以应用栈存储输出结果

c1-3实现

c2-1括号匹配实例

c2-2 尝试

c2-3 构思

c2-4 实现

c2-5 反思

只有一种括号时，使用计数器也可以实现

c2-6 扩展

c3-1 栈混洗

栈混洗后结果如下

c3-2 计数

c3-3 甄别

c3-4 算法

编程练习：利用堆栈完成栈混洗模拟实现的编程

c3-5 括号

push换成左括号，pop对应于一个右括号，发现同一元素对应的push/pop操作恰好对应于一对匹配的括号。反过来由n对括号构成的任何一个合法的表达式，也可以解释为对n个元素进行栈混洗的一个合法的过程。总结来说，n个元素的合法的栈混洗有多少种，n对括号的合法的表达式就有多少种，二者一一对应。

c4-1 中缀表达式

这些计算是如何实现的？

c4-2 构思

优先计算优先级高的运算符
延迟缓冲：线性扫描，找到优先级高的先计算，优先级不定的先缓冲起来，接着向下扫描。

c4-3 实例

c4-4 算法框架

c4-5 算法细节

上图解释了程序代码中case ‘=’，即运算符优先级相等时，代码编写的思路。上图中定义了左括号与右括号的优先级相等，当遍历出现右括号时，此时栈顶一定是与之对应的左括号，且二者包含的计算式在之前已经被计算出来了，所以直接将左括号出栈，跳过右括号继续向下遍历即可。
对于\0，其作用也相当于一对括号。

c4-6 实例

其他运算符乐于接收左括号，左括号也乐于接收其他运算符
\0,右括号乐于促成栈顶运算执行

c5-1 逆波兰表达式简化

逆波兰表达式不使用括号表达优先级，而是将运算的优先级体现为运算符在表达式中出现的次序，谁先出现，谁先计算。

c5-2 体验

将中缀表达式转换为RPN，只需要一个堆栈，即可完成运算

c5-3 手工

转换之后，操作数的顺序不会改变

c5-4 RPN转换算法

d 队列

d1 队列接口

enqueue;dequeue

d2 实例

d3 实现

开始第五章