双端栈 (Double Stack)

什么是双端栈？

双端栈（也称共享栈）是使用一个连续的一维数组来存储两个单独的栈的设计模式。其核心设计在于让两个栈分别从数组的两端向中间增长：

栈 A (Stack A)：栈底在数组开头（索引 $0$），压栈时指针 topA 向右移动（topA++）。
栈 B (Stack B)：栈底在数组末尾（索引 $N-1$），压栈时指针 topB 向左移动（topB--）。

共享内存优势

相比于为两个栈分别开辟两个固定长度的数组，双端栈可以实现空间互补。只要两栈的元素总数不超过数组容量 $N$，就不会发生溢出。只有当 topA + 1 == topB 时，才会判定为 栈满溢出（Stack Overflow）。

共享数组容量：

点击下方左右面板的 PUSH 或 POP 按钮对栈 A 和栈 B 进行操作。

栈 A (从左增长)

栈 B (从右增长)

C++ 核心代码对照

双端栈 C++ 类实现

class DoubleStack {
private:
    int* arr;       // 共享的一维数组
    int capacity;   // 数组总容量
    int topA;       // 栈 A 的栈顶指针，初始为 -1
    int topB;       // 栈 B 的栈顶指针，初始为 capacity

public:
    DoubleStack(int size) {
        capacity = size;
        arr = new int[capacity];
        topA = -1;
        topB = capacity;
    }

    // 压入栈 A
    bool pushA(int val) {
        if (topA + 1 == topB) {
            cout << "Stack Overflow (栈已满冲突)!" << endl;
            return false;
        }
        arr[++topA] = val;
        return true;
    }

    // 压入栈 B
    bool pushB(int val) {
        if (topA + 1 == topB) {
            cout << "Stack Overflow (栈已满冲突)!" << endl;
            return false;
        }
        arr[--topB] = val;
        return true;
    }

    // 弹出栈 A
    bool popA(int& val) {
        if (topA == -1) {
            cout << "Stack A Empty (栈 A 已空)!" << endl;
            return false;
        }
        val = arr[topA--];
        return true;
    }

    // 弹出栈 B
    bool popB(int& val) {
        if (topB == capacity) {
            cout << "Stack B Empty (栈 B 已空)!" << endl;
            return false;
        }
        val = arr[topB++];
        return true;
    }
};