數據結構：鏈棧（Linked Stack）C語言完整實現

編輯：關於C語言

數據結構：鏈棧（Linked Stack）C語言完整實現

鏈棧是棧的鏈式存儲結構，通常採用不帶頭結點的單鏈表實現。棧頂對應鏈表頭部，採用頭插法進行入棧、出棧操作，時間複雜度均為 O(1)。本文給出規範、完整的 C 語言實現，修正了原文中類型定義不一致、操作函數混用順序棧邏輯等問題。

一、類型定義

typedef int ElemType;  // 可根據需要改為其他類型

typedef struct Node {
    ElemType data;
    struct Node* next;
} LinkNode, *LinkStack;  // LinkStack 即棧頂指針

二、基本操作實現

1. 初始化 — 創建空棧

LinkStack Init_LinkStack(void) {
    return NULL;  // 空棧棧頂指針為 NULL
}

2. 判空

int IsEmpty_LinkStack(LinkStack top) {
    return top == NULL;
}

3. 入棧 — 頭插法

int Push_LinkStack(LinkStack* top, ElemType x) {
    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    if (!newNode) return 0;  // 內存分配失敗
    newNode->data = x;
    newNode->next = *top;
    *top = newNode;
    return 1;  // 成功
}

4. 出棧 — 刪除頭結點並返回值

int Pop_LinkStack(LinkStack* top, ElemType* x) {
    if (IsEmpty_LinkStack(*top)) return 0;  // 棧空
    LinkNode* temp = *top;
    *x = temp->data;
    *top = temp->next;
    free(temp);
    return 1;
}

5. 讀取棧頂元素（不刪除）

int Top_LinkStack(LinkStack top, ElemType* x) {
    if (IsEmpty_LinkStack(top)) return 0;
    *x = top->data;
    return 1;
}

6. 銷毀棧 — 釋放所有節點

void Destroy_LinkStack(LinkStack* top) {
    LinkNode* p;
    while (*top) {
        p = *top;
        *top = (*top)->next;
        free(p);
    }
}

7. 遍歷輸出（從棧頂到棧底）

void Print_LinkStack(LinkStack top) {
    LinkNode* p = top;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

三、完整測試主程序

int main(void) {
    LinkStack S = Init_LinkStack();
    int val;
    
    Push_LinkStack(&S, 10);
    Push_LinkStack(&S, 20);
    Push_LinkStack(&S, 30);
    printf("棧內元素（頂到底）：");
    Print_LinkStack(S);  // 輸出: 30 20 10
    
    Top_LinkStack(S, &val);
    printf("棧頂元素: %d\n", val);  // 30
    
    Pop_LinkStack(&S, &val);
    printf("出棧: %d\n", val);      // 30
    printf("剩餘元素：");
    Print_LinkStack(S);  // 20 10
    
    Destroy_LinkStack(&S);
    return 0;
}

四、鏈棧 vs 順序棧對比

特性	鏈棧	順序棧
存儲結構	鏈表，動態分配	數組，固定大小或動態擴容
內存利用	無內部碎片，但有指針開銷	可能預留過多/不足，需擴容策略
訪問非棧頂元素	O(n) 遍歷	O(1) 下標隨機訪問
適用場景	大小難預估、頻繁增減、嵌入式受限環境	大小可預估、需高性能隨機訪問、緩存友好