算法 - 栈

• 极客时间 - 数据结构与算法之美 - 08 | 栈

栈

• 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性
• 顺序栈，由数组实现，有边界，也可做动态扩容
• 链式栈，由链表实现，无边界
• 操作：入栈，出栈。

四则运算表达式求值：

• 两个栈：操作数栈，运算符栈
• 我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；
• 当遇到运算符，就与运算符栈的栈顶元素进行比较。
  • 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
  • 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

四则运算表达式求值（带括号）：

• 两个栈：操作数栈，运算符栈
• 我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；
• 当遇到运算符，就与运算符栈的栈顶元素进行比较。
  • 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
  • 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
• 当遇到(，直接压入运算符栈；
• 当遇到)，看运算符栈顶元素是否为(
  • 如果是(，则运算符栈顶弹出
  • 如果不是(，从运算符栈中取栈顶运算符，则从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续判断。