C 語言實現帶頭結點單鏈表模擬堆疊：完整教學與原始碼

C 語言實現帶頭結點單鏈表模擬堆疊：完整教學與原始碼

繼靜態陣列、動態陣列實現堆疊後，本文介紹帶頭結點單鏈表實現。鏈表無固定容量限制，且堆疊的「先進後出」特性與單鏈表「頭部插入/刪除 O(1)」完美契合。

資料結構設計

typedef int ElemType;
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *Stack;  // Stack 即為指向頭結點的指標

頭結點不存放資料，next 指向棧頂元素。空堆疊時 head->next == NULL。

核心操作實現

1. 初始化

void createStack(Stack *s) {
    *s = (Stack)malloc(sizeof(Node));
    if (!*s) { fprintf(stderr, "記憶體配置失敗\n"); exit(1); }
    (*s)->next = NULL;
}

2. 入棧

void push(Stack s, ElemType val) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) { fprintf(stderr, "記憶體配置失敗\n"); return; }
    newNode->data = val;
    newNode->next = s->next;  // 新節點指向原棧頂
    s->next = newNode;        // 頭結點指向新棧頂
}

3. 出棧

void pop(Stack s) {
    if (isEmpty(s)) return;
    Node *topNode = s->next;
    s->next = topNode->next;
    free(topNode);
}

4. 取棧頂

void top(Stack s) {
    if (isEmpty(s)) { printf("堆疊為空\n"); return; }
    printf("棧頂元素：%d\n", s->next->data);
}

5. 判空

int isEmpty(Stack s) {
    return s->next == NULL;
}

6. 列印（自頂向下）

void printStack(Stack s) {
    if (isEmpty(s)) { printf("堆疊為空\n"); return; }
    Node *p = s->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

7. 銷毀（釋放所有節點）

void destroyStack(Stack s) {
    Node *p = s->next;
    while (p) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
    s->next = NULL;
}

主程式測試

int main() {
    Stack s;
    createStack(&s);
    push(s, 3); push(s, 1); push(s, 9); push(s, 4); push(s, 7);
    printStack(s);  // 7 4 9 1 3
    pop(s); pop(s);
    printStack(s);  // 9 1 3
    top(s);         // 9
    destroyStack(s);
    printStack(s);  // 堆疊為空
    return 0;
}

三種實現方式比較

教學重點總結

1. 頭結點統一空/非空邏輯：免去針對首節點的特判
2. 記憶體管理：每個 malloc 必須配對 free，避免洩漏
3. 指標操作順序：入棧先 new->next = head->next 再 head->next = new；出棧先保存 top 再 head->next = top->next 最後 free(top)
4. 錯誤處理：malloc 失敗、空堆疊操作均需檢查

原始碼已上傳 GitHub：Stack_LinkedList