兩棧共享空間：C語言實現雙棧優化記憶體利用率

設計動機

當兩個棧的總元素數量固定但各自增減不均時，分別分配固定空間會導致浪費。雙棧共享一個陣列，一端向右增長，一端向左增長，動態平衡空間使用。

數據結構定義

#define MAXSIZE 100
typedef int SElemType;

typedef struct {
    SElemType data[MAXSIZE];
    int top1; // 棧1棧頂索引，初始 -1
    int top2; // 棧2棧頂索引，初始 MAXSIZE
} SqDoubleStack;

核心操作實現

初始化與判空

Status InitStack(SqDoubleStack *S) {
    S->top1 = -1;
    S->top2 = MAXSIZE;
    return OK;
}

Status StackEmpty(SqDoubleStack S) {
    return (S.top1 == -1 && S.top2 == MAXSIZE) ? TRUE : FALSE;
}

入棧：滿檢查與雙向增長

Status Push(SqDoubleStack *S, SElemType e, int stackNumber) {
    if (S->top1 + 1 == S->top2) return ERROR; // 棧滿：相遇無空位
    if (stackNumber == 1) {
        S->data[++S->top1] = e; // 棧1向右：先增後存
    } else if (stackNumber == 2) {
        S->data[--S->top2] = e; // 棧2向左：先減後存
    }
    return OK;
}

出棧：空檢查與歸還空間

Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber) {
    if (stackNumber == 1) {
        if (S->top1 == -1) return ERROR;
        *e = S->data[S->top1--]; // 取值後棧頂左移
    } else if (stackNumber == 2) {
        if (S->top2 == MAXSIZE) return ERROR;
        *e = S->data[S->top2++]; // 取值後棧頂右移
    }
    return OK;
}

遍歷顯示：雙向輸出

Status StackTraverse(SqDoubleStack S) {
    int i = 0;
    while (i <= S.top1) { visit(S.data[i++]); } // 棧1：從底到頂
    i = S.top2;
    while (i < MAXSIZE) { visit(S.data[i++]); } // 棧2：從底到頂（索引遞增）
    printf("\n");
    return OK;
}

空間利用率分析

• 傳統雙棧各分配 50：總容量 100，若棧1用 80、棧2用 10 → 棧1溢出雖棧2尚有 40 空閒。
• 共享空間：棧1 用 80、棧2 用 10 → 總用 90，仍有 10 空閒，靈活度大增。

應用場景

1. 表達式求值：操作數棧與運算符棧共享空間。
2. 瀏覽器前進/後退：兩個方向歷史記錄總量受限。
3. 嵌入式系統：RAM 受限，多任務棧動態分配。

擴展：多棧共享

可推廣至 N 棧共享一個陣列，需維護 N 個 top 指針，入棧時尋找相鄰棧間隙，複雜度較高，通常用鏈表實現更靈活。