您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

鏈式堆疊（Linked Stack）C語言完整實現與動態特性分析

編輯：關於C

資料結構定義

typedef int SElemType;

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct {
    LinkStackPtr top;
    int count;
} LinkStack;

核心操作實現

初始化與銷毀

Status InitStack(LinkStack *S) {
    S->top = NULL; S->count = 0;
    return OK;
}
Status ClearStack(LinkStack *S) {
    LinkStackPtr p = S->top, q;
    while (p) { q = p; p = p->next; free(q); }
    S->count = 0; return OK;
}
// 銷毀同 ClearStack 後 free(S) （若 S 為動態分配）

狀態查詢

Status StackEmpty(LinkStack S) { return S.count == 0 ? TRUE : FALSE; }
int StackLength(LinkStack S) { return S.count; }
Status GetTop(LinkStack S, SElemType *e) {
    if (!S.top) return ERROR;
    *e = S->top->data; return OK;
}

推入（頭插法）

Status Push(LinkStack *S, SElemType e) {
    LinkStackPtr n = malloc(sizeof(StackNode));
    if (!n) return ERROR;
    n->data = e; n->next = S->top; S->top = n; S->count++;
    return OK;
}

彈出

Status Pop(LinkStack *S, SElemType *e) {
    if (StackEmpty(*S)) return ERROR;
    LinkStackPtr p = S->top;
    *e = p->data; S->top = p->next; free(p); S->count--;
    return OK;
}

遍歷

Status StackTraverse(LinkStack S) {
    for (LinkStackPtr p = S.top; p; p = p->next)
        visit(p->data);
    printf("\n"); return OK;
}

順序堆疊 vs 鏈式堆疊對比

指標	順序堆疊	鏈式堆疊
空間複雜度	O(MAXSIZE) 固定	O(n) 動態
Push/Pop 時間	O(1) 純陣列操作	O(1) 需 malloc/free
記憶體碎片	無	有
快取友善度	高（連續記憶體）	低（節點分散）
擴容靈活性	需重新分配複製	天然支援
最大容量	受限於預分配	受限於記憶體