Skip to content

techniques

双栈法

“双栈法”（Two Stacks）是计算机科学中极其经典且优雅的技巧。它的核心思想通常可以归结为两点：“负负得正（顺序反转）” 或 “状态隔离（主辅分离）”。

以下是双栈法最常见的五种适用场景以及具体的使用方法：

1. 场景一：二叉树的之字形（ZigZag）层序遍历

  • 适用情况： 当你需要按层遍历树或图，且相邻两层的遍历方向完全相反时。

  • 为什么用双栈： 栈的特性是后进先出 (LIFO)，它天生自带“反转”属性。如果你把一层节点压入栈，弹出来的顺序就是反的。我们需要两层反转，所以需要两个栈。

void zigzagPrint(tree *a){
    if(!a) return;
    push(a, &S2);
    int isFirst = 1;

    while(!emptyS(&S1) || !emptyS(&S2)){
        while(!emptyS(&S2)){
            tree *curr = pop(&S2);
            if(!isFirst) printf(" ");
            printf("%d", curr->element);
            isFirst = 0;
            if(curr->right) push(curr->right, &S1);
            if(curr->left) push(curr->left, &S1);
        }
        while(!emptyS(&S1)){
            tree *curr = pop(&S1);
            if(!isFirst) printf(" ");
            printf("%d", curr->element);
            isFirst = 0;
            if(curr->left) push(curr->left, &S2);
            if(curr->right) push(curr->right, &S2);
        }
    }
}

2. 场景二：用两个栈实现一个队列 (Queue via Stacks)

  • 适用情况： 在只有栈（LIFO）这种数据结构的情况下，如何模拟出队列（FIFO, 先进先出）的行为。

  • 使用方法：

    • 定义 StackIn (输入栈) 和 StackOut (输出栈)。

    • 入队 (Enqueue)： 永远直接把数据压入 StackIn。

    • 出队 (Dequeue)：

      1. 如果 StackOut 里面有元素，直接从 StackOut 弹出顶部元素。

      2. 如果 StackOut 是空的，就把 StackIn 里的所有元素依次弹出，并压入 StackOut 中。然后再从 StackOut 弹出顶部元素。

3. 场景三：表达式求值 / 简易计算器 (Expression Evaluation)

  • 适用情况： 解析带有括号和不同优先级运算符的数学表达式（如 3 + 5 * (2 - 8)）。

  • 为什么用双栈： 数字和运算符的处理逻辑不同，且运算符存在优先级（乘除高于加减），需要分离状态并暂存。

  • 使用方法：

    • 操作数栈 (Operand Stack)： 专存数字。

    • 运算符栈 (Operator Stack)： 专存 + - * / ( )。

    • 遍历表达式：遇到数字直接进数字栈；遇到运算符，与运算符栈顶比较优先级。如果当前优先级低或相等，就从数字栈弹出两个数，从运算符栈弹出一个符号，计算结果后重新压回数字栈。

4. 场景四：包含 Min/Max 函数的栈 (Min Stack)

  • 适用情况： 设计一个栈，除了具备正常的 push 和 pop，还需要能在 \(O(1)\) 的时间复杂度内获取栈内的最小值或最大值。

  • 为什么用双栈： 普通栈无法记住“历史最小值”。我们需要一个辅助栈来同步记录每个状态下的极值。

  • 使用方法：

    • 主栈 (Main Stack)： 正常存取所有数据。

    • 辅助栈 (Min Stack)： 存对应时刻的最小值。

    • 当新元素压入主栈时：如果新元素 \(\le\) 辅助栈顶元素，也把它压入辅助栈。

    • 当弹出元素时：如果弹出的元素等于辅助栈顶元素，辅助栈也跟着弹出一个。

5. 场景五：软件的 撤销/重做 (Undo/Redo) 或 浏览器前进/后退

  • 适用情况： 需要在一个线性的历史记录中来回穿梭。

  • 为什么用双栈： 历史是“过去”，未来是“重做”。当前状态刚好夹在两个时间轴中间。

  • 使用方法：

    • 撤销栈 (Undo Stack)： 每做一次新操作，把状态压入此栈。点击“撤销”时，把栈顶弹出。

    • 重做栈 (Redo Stack)： 点击“撤销”时，把弹出的状态压入这个重做栈。如果此时做了一个新操作，重做栈必须全部清空（因为未来改变了）。