雙堆疊共享空間（Shared Array Stacks）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 ClearStack(SqDoubleStack *S) {
    S->top1 = -1; S->top2 = MAXSIZE;
    return OK;
}

狀態查詢

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

推入（需指定堆疊編號）

Status Push(SqDoubleStack *S, SElemType e, int stackNumber) {
    if (S->top1 + 1 == S->top2) return ERROR;  // 共享空間滿
    if (stackNumber == 1)
        S->data[++S->top1] = e;
    else if (stackNumber == 2)
        S->data[--S->top2] = e;
    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) {
    for (int i = 0; i <= S.top1; i++) visit(S.data[i]);
    for (int i = S.top2; i < MAXSIZE; i++) visit(S.data[i]);
    printf("\n");
    return OK;
}

關鍵特性

• 滿判斷： top1 + 1 == top2，兩堆疊相遇無縫隙。
• 空間利用率： 總容量 MAXSIZE 完全共享，單堆疊可用至另一為空。
• 適用場景： 兩堆疊使用量互補（一大一小）、嵌入式系統記憶體受限、雙緩衝區管理。

擴展：多堆疊共享

可推廣至 N 個堆疊共享一陣列，維護 top[N] 陣列與 boundary[N] 分界點，分配策略可為固定分區或動態競爭（需鎖同步）。

參考《大話資料結構》。