Okay, three, two, one, let's jam

302 栈和队列的应用

9 min read

栈和队列的应用

栈与表达式求值

中缀表达式转后缀表达式

优先级>=栈顶符号的时候需要弹出。

输入：中缀表达式 infixExp （以字符或字符串数组形式）
输出：后缀表达式 postfixExp （字符串或数组）
 
1. 创建一个空栈 operatorStack 用于存放运算符
2. 创建一个空列表 postfixList 用于存放后缀表达式元素
 
3. 从左到右遍历中缀表达式中的每个元素 token
    3.1 如果 token 是操作数（数字或变量）
        将 token 直接添加到 postfixList
    3.2 如果 token 是左括号 "("
        将 token 压入 operatorStack
    3.3 如果 token 是右括号 ")"
        从 operatorStack 弹出运算符，依次添加到 postfixList，直到弹出左括号 "("（左括号不加入 postfixList）
    3.4 如果 token 是运算符 op（如 +, -, *, /, ^）
        while operatorStack 不为空 且 栈顶运算符 topOp 的优先级 >= 当前运算符 op 的优先级
              （若运算符结合性为左结合，使用 >= 比较；右结合则使用 >）
            弹出 topOp 并添加到 postfixList
        将当前运算符 op 压入 operatorStack
 
4. 遍历结束后，将 operatorStack 中剩余运算符依次弹出并添加到 postfixList
 
5. 返回 postfixList 作为后缀表达式

运算符优先级表（从高到低）

运算符说明优先级值（示例）
()括号最高（特殊处理）
^乘方4
* /乘、除3
+ -加、减2
其他比较低的运算符或括号1 或 0

注意事项

  • 优先级和结合性必须明确，否则转换结果错误。
  • 括号匹配：输入表达式括号必须匹配，否则弹栈时可能找不到对应左括号。
  • 操作数格式：支持多位数字或变量时，解析时应正确识别完整操作数。
  • 空格或分隔符：表达式中元素应清晰分隔，方便逐个处理。
  • 错误处理：遇到非法字符或格式应有异常处理。
  • 运算符集：根据需求支持的运算符不同，优先级和结合性规则也要相应调整。

人工中缀转后缀

在人工转换中缀表达式到后缀表达式时，一种直观的方法是利用“加括号”和“运算符后移”的思路：

  • 根据运算符的优先级，为每个操作数和运算符组合添加括号，使其成为完全括号化的表达式。

  • 例如，对于 A + B * C：

    • B * C 优先级高，先加括号：A + (B * C)
    • 然后 A + (B * C) 整体加括号：(A + (B * C))

  • 对于 (A + B) * C：

    • A + B 优先级高（括号强制），先加括号：((A + B) * C)

  • 完全括号化后，将每个运算符“移动”到其对应右括号的外面。

  • 最后，移除所有括号。

  • 示例 1: A + B * C

    1. 完全括号化: (A + (B * C))
    2. 运算符后移: (A (B C *) +)
    3. 移除括号: A B C * +

  • 示例 2: (A + B) * C

    1. 完全括号化: ((A + B) * C)
    2. 运算符后移: ((A B +) C *)
    3. 移除括号: A B + C *

后缀表达式求值

输入：后缀表达式 postfixExp （以空格分隔的字符串或数组）
输出：表达式计算结果
 
1. 创建一个空栈 stack 用于存放操作数
 
2. 从左到右遍历后缀表达式中的每个元素 token
    2.1 如果 token 是数字（操作数）
        将 token 转换为数字，压入栈 stack
    2.2 否则 token 是运算符 op（如 +, -, *, /）
        从栈中弹出两个操作数，先弹出的赋值给右操作数 b，后弹出的赋值给左操作数 a
        根据运算符 op 计算 result = a op b
        将 result 压入栈 stack
 
3. 遍历结束后，栈顶元素即为表达式的计算结果，弹出并返回该结果

注意事项

  • 操作数顺序：弹出栈顶的两个操作数时，先弹出的为右操作数，后弹出的为左操作数，计算时顺序不能颠倒（如 a op b）。
  • 运算符合法性：输入的后缀表达式必须是合法的，运算符数量和操作数数量匹配，避免栈空时弹栈错误。
  • 除法处理：除法时注意除数不能为零，且根据需求处理整数除法或浮点除法（整数除法可能只保留整数部分）。
  • 数字格式：支持多位数字和负数时，解析数字时应正确识别完整数字。
  • 空格分隔：后缀表达式中元素应当用空格或其他明确分隔符分开，方便逐个读取。
  • 栈初始化和结束状态：开始时栈为空，结束时栈中应仅剩一个元素，即最终结果，若多于一个元素说明表达式不合法。

综上，后缀表达式求值的核心是利用栈结构，遇数字入栈，遇运算符弹出两个数字计算后再入栈，遍历完表达式后栈顶即为结果

队列在广度优先遍历的应用

广度优先遍历（Breadth-First Search, BFS）是一种图或树的遍历算法，它从起始节点开始，探索其所有相邻节点，然后是这些相邻节点的未访问邻居，以此类推，逐层向外扩展。队列的先进先出（FIFO）特性使其成为实现 BFS 的理想数据结构。

核心思想： 队列保证了节点是按照它们被发现的顺序（即距离起始节点的距离）进行访问的。先被发现的节点（更靠近起始节点）会先被处理，从而实现逐层遍历的效果。

算法步骤：

  1. 初始化：
    • 创建一个空队列 Q。
    • 创建一个集合或数组 visited 用于记录已访问的节点，避免重复访问和死循环。
    • 将起始节点 s 标记为已访问，并将其加入队列 Q。
  2. 遍历：
    • 当队列 Q 不为空时，重复以下步骤：
      • 从队列 Q 中出队一个节点 u。
      • 处理节点 u（例如，打印节点值，检查是否为目标节点等）。
      • 遍历节点 u 的所有未访问邻居 v：
        • 将邻居 v 标记为已访问。
        • 将邻居 v 入队 Q。

示例应用：

  • 二叉树层次遍历：按照从上到下、从左到右的顺序逐层访问二叉树中的所有节点。
  • 查找最短路径： 在无权图中，BFS 可以找到从起始节点到所有其他节点的最短路径（按边数计算）。
  • 社交网络分析： 查找“六度分隔理论”中的连接路径。
  • 网络爬虫： 从一个起始页面开始，逐层爬取链接的页面。
  • 垃圾回收： 标记 - 清除算法中，从根对象开始遍历可达对象。

Graph View

Backlinks