順序堆疊（Sequential Stack）C語言完整實現與操作詳解

資料結構定義

#define MAXSIZE 100
typedef int SElemType;  // 元素型別，可依需求修改

typedef struct {
    SElemType data[MAXSIZE];
    int top;  // 堆疊頂指標，-1 表示空
} SqStack;

核心操作實現

初始化與清空

Status InitStack(SqStack *S) {
    S->top = -1;
    return OK;
}
Status ClearStack(SqStack *S) {
    S->top = -1;
    return OK;
}

狀態查詢

Status StackEmpty(SqStack S) {
    return S.top == -1 ? TRUE : FALSE;
}
int StackLength(SqStack S) {
    return S.top + 1;
}
Status GetTop(SqStack S, SElemType *e) {
    if (S.top == -1) return ERROR;
    *e = S.data[S.top];
    return OK;
}

推入與彈出

Status Push(SqStack *S, SElemType e) {
    if (S->top == MAXSIZE - 1) return ERROR;  // 堆疊滿
    S->data[++S->top] = e;
    return OK;
}
Status Pop(SqStack *S, SElemType *e) {
    if (S->top == -1) return ERROR;
    *e = S->data[S->top--];
    return OK;
}

遍歷顯示

Status StackTraverse(SqStack S) {
    for (int i = 0; i <= S.top; i++)
        visit(S.data[i]);
    printf("\n");
    return OK;
}
Status visit(SElemType c) { printf("%d ", c); return OK; }

特性分析

優缺點與適用場景

• 優點： 實現簡單、記憶體連續、存取快、無指標開銷。
• 缺點： 容量固定（需預估上限）、擴容麻煩（需重新分配複製）、佔用記憶體可能浪費。
• 適用： 最大深度可預估、效能敏感、嵌入式系統無動態分配環境。

擴展建議

• 動態擴容：data 改為指標，Push 滿時 realloc 擴大 2 倍。
• 泛型化：void* data + 元素大小參數，配合函式指標複製/比較/銷毀。
• 線程安全：加入互斥鎖保護 top 與 data。

參考《大話資料結構》。