C語言單鏈表實現棧：帶頭節點設計，動態擴容、無容量上限

為什麼單鏈表適合做棧？

• 棧只操作棧頂，單鏈表頭部插入/刪除恰好是 O(1)。
• 引入頭節點（哨兵），統一空/非空操作，無需特判首節點。
• 動態分配節點，理論容量僅受限於堆內存，無溢出風險。

數據結構

typedef struct Node {
    int element;
    struct Node *next;
} Node;  // 頭節點不存有效數據，next 指向棧頂

核心操作

Node* Stack_Create(void) {
    Node *h = malloc(sizeof(Node));
    h->next = NULL;
    return h;
}

void Stack_Destroy(Node *h) {
    Node *p = h->next;
    while (p) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
    free(h);
}

void Push(Node *h, int val) {
    Node *n = malloc(sizeof(Node));
    n->element = val;
    n->next = h->next;
    h->next = n;
}

bool Pop(Node *h, int *out) {
    if (!h->next) return false;
    Node *victim = h->next;
    *out = victim->element;
    h->next = victim->next;
    free(victim);
    return true;
}

bool Top(const Node *h, int *out) {
    if (!h->next) return false;
    *out = h->next->element;
    return true;
}

bool IsEmpty(const Node *h) { return h->next == NULL; }

void PrintStack(const Node *h) {
    for (Node *p = h->next; p; p = p->next) printf("%d ", p->element);
    puts("");
}

測試主程式

int main(void) {
    Node *s = Stack_Create();
    Push(s, 3); Push(s, 1); Push(s, 9); Push(s, 4); Push(s, 7);
    PrintStack(s);          // 7 4 9 1 3
    int v; Pop(s, &v); Pop(s, &v);
    PrintStack(s);          // 9 1 3
    Top(s, &v); printf("top=%d\n", v); // 9
    Stack_Destroy(s);
    return 0;
}

對比：靜態數組 vs 單鏈表 vs 動態數組