栈

顺序栈（顺序存储结构）

  • 存储结构：用一段连续存储单元（数组）存放栈元素
  • 关键指针：
    • 常见做法：top 指向当前栈顶元素位置，或指向栈顶元素的下一位置（两种约定均可，需配套一致）
  • 上溢/下溢：
    • 上溢（overflow）：栈满仍入栈（越界）
    • 下溢（underflow）：栈空仍出栈（非法）
  • 时间复杂度：入栈/出栈/取栈顶均为 O(1)
  • 空间特性：需要预先分配容量 MaxSize，可能产生空间浪费或容量不足

共享栈

  • 两个栈共享同一数组空间，分别从两端向中间增长
  • 优点：在总空间固定时，能更充分利用存储空间；当一个栈空而另一个栈满的情况减少
  • 满栈判定：两栈顶指针相遇（或满足相邻条件，依约定而定）

链栈（链式存储结构）

  • 存储结构：用单链表实现，通常把表头作为栈顶以便 Push/Pop 在表头进行
  • 栈顶指针：指向栈顶结点
  • 优点：
    • 不需要预先分配固定容量，理论上只受限于可用内存
    • 入栈/出栈无需移动大量元素。
  • 时间复杂度：入栈/出栈/取栈顶均为 O(1)；额外指针域带来一定存储开销

栈的典型应用与要点

括号匹配

  • 思想：扫描表达式，遇到左括号入栈，遇到右括号则与栈顶左括号进行匹配并出栈
  • 关键结论：
    • 扫描结束时栈必须为空才匹配成功；
    • 扫描中任何时刻出现“需要出栈但栈空”则匹配失败

表达式求值与表达式转换

  • 三种常见表示：
    • 中缀（运算符在中间，日常书写）
    • 后缀/逆波兰式（RPN）（运算符在后，便于用栈求值）
    • 前缀（运算符在前）
  • 中缀 → 后缀（人为转换逻辑，核心是“运算符栈”处理优先级与括号）：
    • 约定：运算符有优先级（如 * / 高于 + -），且多数二元运算符是左结合（同优先级从左到右计算）。括号用于改变优先级
    • 准备：
      • 一个输出序列（写下后缀表达式）
      • 一个运算符栈（暂存运算符与左括号）
    • 从左到右扫描中缀表达式的每个记号（操作数/运算符/括号）：
      • 遇到操作数：直接追加到输出序列
      • 遇到左括号 (：入运算符栈（它的作用是“隔断”，直到遇到对应右括号才弹出）
      • 遇到右括号 )：
        • 反复弹出栈顶运算符并追加到输出序列，直到弹出左括号 ( 为止（左括号本身不输出）
      • 遇到运算符 op（如 + - * /）：
        • 当运算符栈非空，且栈顶是运算符 topOp，并且：
          • topOp 的优先级 高于 op，或
          • topOp 的优先级 等于 op 且 op 是左结合
        • 则将 topOp 出栈并追加到输出序列；重复上述比较，直到不满足条件或遇到左括号
        • 最后将当前运算符 op 入栈
    • 扫描结束：
      • 将运算符栈中剩余的运算符依次弹出并追加到输出序列（此时不应再有括号；若有通常说明表达式括号不匹配）
  • 后缀表达式求值：
    • 扫描：操作数入栈；遇运算符则弹出两个操作数计算后再入栈；
    • 结束时栈顶即结果

出栈序列计数（卡特兰数）

  • 问题表述（常见考点）：对 n 个元素按固定顺序 1,2,...,n 依次入栈（入栈顺序固定），在允许任意时刻出栈的前提下，一共有多少种不同的出栈序列？
  • 结论：合法出栈序列的种类数为第 n 个卡特兰数

    Cn = (1 / (n + 1)) · C(2n, n)

  • 推理思路：
    • 将一次入栈记为 +1（向上一步），一次出栈记为 -1（向下一步）。
    • 任何完整过程都包含 n 次入栈与 n 次出栈，因此共有 2n 步，且最终高度回到 0。
    • 合法性约束：任意时刻都不能出现“出栈次数 > 入栈次数”，对应到路径就是：从起点出发的过程中，高度不能降到 0 以下（不能穿过 x 轴下方）。
    • 先不管合法性：只要求 n 个 +1 与 n 个 -1 的排列，数量是

      C(2n, n)

    • 再数“非法路径”（第一次跌破 0 的路径）。用反射原理可证明：非法路径条数等于

      C(2n, n + 1)

      直观理解：把某条第一次跌破 0 之后的部分作镜像映射，可与“`n+1` 次出栈、`n-1` 次入栈”的序列建立一一对应，从而得到计数。
    • 因此合法路径（合法出栈序列）数为：

      Cn = C(2n, n) - C(2n, n + 1) = (1 / (n + 1)) · C(2n, n)

  • 递推形式（常用性质）：

    C0 = 1

    Cn = Σk=0n-1 Ck · Cn-1-k (n ≥ 1)

    含义：按“最后一次出栈对应的元素”将整体拆成左右两个相互独立的合法子结构

递归与函数调用栈

  • 递归本质：把大问题分解为规模更小的同类子问题，依靠系统调用栈保存返回点与局部状态。
  • 关键结论：
    • 必须有递归出口（终止条件）；
    • 深度过大可能导致栈溢出；
    • 很多递归可改写为显式栈的非递归形式（如深度优先搜索）

深度优先搜索（DFS）

  • DFS 的“先走到底再回退”天然符合栈的 LIFO 特性
  • 实现上：递归 DFS 使用系统栈；非递归 DFS 使用显式栈保存待访问结点/状态

栈相关常见结论小结

  • 栈是受限线性表，核心特性：LIFO。
  • 顺序栈与链栈的基本操作复杂度均为 O(1)，差别主要在空间管理方式（固定容量 vs 动态分配）。
  • “溢出”分为上溢与下溢；实现中需做边界检查与错误处理
    • 上溢：栈满时入栈
    • 下溢：栈空时出栈

队列

循环队列

  • 核心思想：数组首尾相接，指针按模运算循环移动：
    • front = (front + 1) % MaxSize
    • rear = (rear + 1) % MaxSize

判空与判满

循环队列必须解决“front == rear 时到底是空还是满”的二义性，常见方法：

  • 牺牲一个存储单元（最常用）

    • 判空：front == rear
    • 判满：(rear + 1) % MaxSize == front
    • 可用容量：MaxSize - 1

  • 增加计数器 size

    • 判空：size == 0
    • 判满：size == MaxSize

  • 增加标志位 tag（区分最近一次操作是入队还是出队）

链队列（链式存储结构）

  • 用链表实现队列，通常设置：
    • front 指向队头结点（或头结点/哨兵结点）
    • rear 指向队尾结点
  • 若采用**带头结点（哨兵）**的链队列：
    • 判空常为 front == rear（都指向头结点）。
  • 优点：
    • 不需要预设容量，适合元素个数变化较大场景；
    • 入队在尾部插入、出队在头部删除，均为 O(1)

队列的变形与应用要点

双端队列（Deque）

  • 两端允许进入，一端允许退出
  • 两端允许退出，一端允许进入

队列在算法/系统中的常见用途

  • 层次遍历（BFS）：按层推进天然符合 FIFO，典型实现用队列保存待访问结点
  • 缓冲与调度：如打印队列、消息队列、CPU 就绪队列等