C 語言實作順序棧：動態擴容與完整操作介面

C 語言實作順序棧：動態擴容與完整操作介面

資料結構定義

#define STACK_INIT_SIZE 10
#define STACKINCREASE 10
#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *base;   // 棧底指標
    ElemType *top;    // 棧頂指標（指向下一個可用位置）
    int InitSize;     // 當前分配容量
} SqStack;

核心操作實作

初始化與銷毀

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

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

進棧（自動擴容）

Status Push(SqStack *s, ElemType value) {
    if (s->top - s->base >= s->InitSize) {  // 滿
        ElemType *newbase = (ElemType*)realloc(s->base,
            (s->InitSize + STACKINCREASE) * sizeof(ElemType));
        if (!newbase) return ERROR;
        s->base = newbase;
        s->top = s->base + s->InitSize;
        s->InitSize += STACKINCREASE;
    }
    *(s->top++) = value;
    return OK;
}

出棧與取頂

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

測試主程式與輸出

int main() {
    SqStack s; InitStack(&s);
    Push(&s, 3); Push(&s, 5); Push(&s, 4);
    Push(&s, 1); Push(&s, 97); Push(&s, 423);
    // 顯示棧內元素（從頂向下）
    SqStack tmp = s;
    while (tmp.top != tmp.base) printf("%d ", *--tmp.top);
    // 出棧三次
    int r; Pop(&s, &r); printf("Pop %d ", r);
    Pop(&s, &r); printf("Pop %d ", r);
    Pop(&s, &r); printf("Pop %d ", r);
    DestroyStack(&s);
    return 0;
}

輸出：423 97 1 4 5 3 Pop 423 Pop 97 Pop 1

設計亮點

• 動態擴容：滿時自動 realloc，無固定容量限制
• 指標算術：以 top - base 計算當前長度，top 指向下一可用位置，邏輯清晰
• 完整介面：Init/Clear/Destroy/Push/Pop/Traverse 一應俱全

此實作可直接作為專案中通用棧模組使用。