C 語言實現順序棧：完整代碼、動態擴容、錯誤處理與泛型擴展指南

順序棧 ADT 設計

// stack.h
#ifndef STACK_H
#define STACK_H

typedef int ElemType; // 可替換為 void* 實現泛型
typedef enum { OK = 0, ERROR = -1, OVERFLOW = -2 } Status;

typedef struct {
    ElemType *base;   // 棧底指針
    ElemType *top;    // 棧頂指針 (指向下一個可用位置)
    int stackSize;    // 當前分配容量
} SqStack;

/* 基礎操作 */
Status InitStack(SqStack *s);          // 初始化
Status DestroyStack(SqStack *s);       // 銷毀
Status ClearStack(SqStack *s);         // 清空 (保留內存)
Status Push(SqStack *s, ElemType e);   // 入棧 (自動擴容)
Status Pop(SqStack *s, ElemType *e);   // 出棧
Status GetTop(SqStack *s, ElemType *e); // 取棧頂
int StackEmpty(SqStack *s);            // 判空
int StackLength(SqStack *s);           // 長度

#endif

核心實現 (stack.c)

#include "stack.h"
#include 
#include 

#define INIT_CAPACITY 10
#define INCREMENT 10

Status InitStack(SqStack *s) {
    if (!s) return ERROR;
    s->base = malloc(INIT_CAPACITY * sizeof(ElemType));
    if (!s->base) return OVERFLOW;
    s->top = s->base;
    s->stackSize = INIT_CAPACITY;
    return OK;
}

Status DestroyStack(SqStack *s) {
    if (!s) return ERROR;
    free(s->base);
    s->base = s->top = NULL;
    s->stackSize = 0;
    return OK;
}

Status ClearStack(SqStack *s) {
    if (!s) return ERROR;
    s->top = s->base;
    return OK;
}

Status Push(SqStack *s, ElemType e) {
    if (!s) return ERROR;
    // 滿則擴容
    if (s->top - s->base >= s->stackSize) {
        int newSize = s->stackSize + INCREMENT;
        ElemType *newBase = realloc(s->base, newSize * sizeof(ElemType));
        if (!newBase) return OVERFLOW;
        s->top = newBase + (s->top - s->base); // 修正 top 指針
        s->base = newBase;
        s->stackSize = newSize;
    }
    *s->top++ = e;
    return OK;
}

Status Pop(SqStack *s, ElemType *e) {
    if (!s || !e) return ERROR;
    if (s->top == s->base) return ERROR; // 空棧
    *e = *--s->top;
    return OK;
}

Status GetTop(SqStack *s, ElemType *e) {
    if (!s || !e) return ERROR;
    if (s->top == s->base) return ERROR;
    *e = *(s->top - 1);
    return OK;
}

int StackEmpty(SqStack *s) {
    return (s && s->top == s->base);
}

int StackLength(SqStack *s) {
    return (s ? s->top - s->base : -1);
}

測試驗證 (main.c)

#include "stack.h"
#include 

int main() {
    SqStack s;
    InitStack(&s);
    
    // 壓入 1..100 測試擴容
    for (int i = 1; i <= 100; ++i) {
        if (Push(&s, i) != OK) {
            fprintf(stderr, "Push failed at %d\n", i);
            return 1;
        }
    }
    printf("Stack length: %d, capacity: %d\n", StackLength(&s), s.stackSize);
    
    // 彈出驗證逆序
    int val;
    for (int i = 100; i >= 1; --i) {
        Pop(&s, &val);
        if (val != i) {
            fprintf(stderr, "Mismatch: expected %d, got %d\n", i, val);
            return 1;
        }
    }
    printf("Pop test passed. Empty: %d\n", StackEmpty(&s));
    
    DestroyStack(&s);
    return 0;
}

關鍵設計決策解析

泛型化擴展：void* 版本

// gstack.h
typedef void *ElemType; // 存儲指針
typedef void (*FreeFunc)(void *); // 元素釋放器

typedef struct {
    void **base;
    void **top;
    int stackSize;
    FreeFunc free_elem; // 可選：銷毀時調用
} GSqStack;

Status GPush(GSqStack *s, void *e); // 傳入指針，所有權轉移
Status GPop(GSqStack *s, void **e); // 彈出指針，調用者負責釋放或繼續持有

配合 FreeFunc 實現 RAUI 風格：DestroyStack 遍歷調用 free_elem。

應用場景

1. 表達式求值：中綴轉後綴 (Shunting-yard)、後綴計算 (操作數棧)。
2. 括號匹配：編譯器詞法分析、JSON 解析器。
3. 遞歸轉迭代：DFS、回溯、塔羅漢算法顯式棧模擬調用棧。
4. 瀏覽器前進/後退：雙棧實現歷史導航。
5. 編譯器語法分析：LR 分析器狀態棧、符號棧。

常見錯誤與檢查清單

1. ❌ Push 未檢查擴容失敗 → 寫入野指針。
2. ❌ realloc 後未修正 top → 指針失效。
3. ❌ Pop 空棧不報錯直接返回 → 讀取未初始化內存。
4. ❌ DestroyStack 未置 NULL → 重複釋放 / 野指針。
5. ✅ 所有公開函數檢查 NULL 指針參數。
6. ✅ 錯誤碼區分邏輯錯誤與資源錯誤。
7. ✅ 測試覆蓋：空棧操作、擴容邊界、大量壓入彈出、內存洩漏 (Valgrind)。

總結

順序棧以連續內存、指針算術、動態擴容 實現 O(1) 均攤入棧/出棧。掌握頂指針語義、realloc 指針修正、錯誤碼設計、泛型化 void* 模式，即可構建生產級棧組件。進階方向：線程安全棧 (CAS/鎖)、持久化棧 (函數式數據結構)、硬件加速棧 (Intel MPX/CHERI)。