TsingHuaDSA-栈和队列

该文章为清华大学数据结构与算法设计MOOC课程读书笔记.

1. 栈

1.1 接口

栈接口

LIFO后进先出

1.2 栈实现

• 基于向量

  
  向量实现stack

• 基于列表
  思路：维持栈顶的指针

1.3 应用

stack典型应用

1）conversion -> 进制转换

• 问题：给一个十进制非负整数，将其转化为𝝀进制表示

• 思路：n对𝝀反复取模(即求余数)，整除。最终各取模结构逆序输出则为结果。
  

  进制转换算法

• 实现

  
  进制转换实现

2）递归嵌套 -> 括号匹配

• 思路
  左括号入栈，右括号如果栈不为空，出栈，若为空，则适配。

  
  括号匹配算法

• 若括号同类型，则可以用计数器（本质上就是在统计栈中的元素个数）
  计数器算法
• 若括号不同类型，则计数器算法失效，栈算法依然有效。

• 扩展
  • 不一定是括号，只要是能够构成匹配对的符号都可以使用，比如xml，html的tag*

3) 递归嵌套 -> 栈混洗stack permutation

• 栈混洗中：每个元素被push一次也被pop一次
• 括号匹配中：左括号对应了一次push与右括号对应一次pop

结论：n个数栈混洗与n对括号的有效排列是一一对应的

栈混洗与括号匹配

4）延迟缓冲 -> 中缀(infix)表达式计算

• 思想
  关键：对前缀进行缓冲
  

  中缀表达式计算思想
  关键：当遇到的运算符比栈顶运算符优先级低，说明栈定的运算符可以进行计算了。
  这也说明了，栈中的操作符，优先级高的排在上，优先级低的排在下。
  中缀表达式Stack实现思想

• 实现
  关键：两个stack，一个存operator，另一个存operand

5) 逆波兰表达式Reversed Polish Notation

• 特点
  通过后缀(postfix)表达式来避免了括号，让运算符出现的顺序代表运算的顺序。
  

  RPN

• 思路

  • 读到数入栈
  • 读到运算符，数出栈参运算，并将结果再次入栈

RPN求值

• 中缀表达式转换 -> RPN

• 思路
  在中缀表达式算法中略作修改：

  • 遇到数字：直接续接到RPN尾部
  • 遇到运算符：
    • 若比栈顶运算符优先级高，将该运算符直接连接到RPN尾部
    • 若比栈顶运算符优先级低，将栈顶运算符连接到RPN尾部
      RPN转换

2. 队列

2.1 队列接口

队列接口

FIFO

2.2 队列实现

关键：维持头，尾两个指针