資料結構：棧的靜態與動態順序存儲完整實現（C 語言）

棧（Stack）核心概念

• LIFO（後進先出） / FILO（先進後出） 線性表。
• 棧頂：允許插入/刪除的一端，由指標 top 指示。
• 棧底：固定端，不動。
• 空棧：無元素時 top == bottom（動態）或 top == 0（靜態）。

一、靜態順序存儲（固定大小陣列）

結構定義

#define MAX_STACK_SIZE 100
typedef int ElemType;
typedef struct {
    ElemType stack_array[MAX_STACK_SIZE];
    int bottom;  // 固定為 0
    int top;     // 當前棧頂下標，0 表空
} SqStack;

基本操作

// 初始化
SqStack Init_Stack(void) {
    SqStack S;
    S.bottom = S.top = 0;
    return S;
}

// 進棧
Status Push(SqStack *S, ElemType e) {
    if (S->top == MAX_STACK_SIZE - 1) return ERROR; // 滿
    S->stack_array[++(S->top)] = e;                 // 先增後存
    return OK;
}

// 出棧
ElemType Pop(SqStack *S) {
    if (S->top == 0) return ERROR;                  // 空
    return S->stack_array[(S->top)--];              // 先取後減
}

溢位說明：Push 時棧滿為「上溢」（錯誤）；Pop 時棧空為「下溢」（可作正常控制條件）。

二、動態順序存儲（可擴容陣列）

結構定義

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
typedef struct {
    ElemType *bottom;   // 動態分配基址
    ElemType *top;      // 指向棧頂「下一個」可用位置
    int stacksize;      // 當前分配容量（元素數）
} SqStack;

基本操作

// 初始化
Status Init_Stack(SqStack *S) {
    S->bottom = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S->bottom) return ERROR;
    S->top = S->bottom;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

// 進棧（自動擴容）
Status Push(SqStack *S, ElemType e) {
    if (S->top - S->bottom >= S->stacksize) {       // 滿
        ElemType *newbase = (ElemType*)realloc(S->bottom,
                           (S->stacksize + STACK_INCREMENT) * sizeof(ElemType));
        if (!newbase) return ERROR;
        S->top = newbase + S->stacksize;            // 關鍵：調整 top 相對位置
        S->bottom = newbase;
        S->stacksize += STACK_INCREMENT;
    }
    *(S->top)++ = e;                                // 存值並後移 top
    return OK;
}

// 出棧
ElemType Pop(SqStack *S) {
    if (S->top == S->bottom) return ERROR;          // 空
    return *--(S->top);                             // 先前移再取值
}

擴容細節：realloc 可能移動記憶體塊，故必須重新計算 top = bottom + 原大小 以保持邏輯位置不變。

三、傳值 vs 傳址的關鍵差異

所有修改棧狀態的操作（Push、Pop、Init）**必須傳址（指標）**，否則函數內修改的是副本，主調函數的棧結構不變。唯有唯讀操作（如 GetTop）可傳值，但為統一風格建議全用指標。

四、總結對比

五、常見面試/考試陷阱

1. Push 時 S->top++ 與賦值順序顛倒會導致元素寫錯位置或覆蓋。
2. 動態棧 realloc 後未更新 top 導致邏輯錯亂。
3. 混淆「top 指向棧頂元素」與「top 指向棧頂下一個空位」兩種約定，導致 Pop/Push 邏輯不一致。

結語

棯雖簡單，但「靜態/動態、指標語義、擴容細節、傳值傳址」考驗的是對記憶體模型與指標運算的基礎功力。掌握這兩種實現，應付教學、面試、嵌入式開發綽綽有餘。