怎么用C語言實現鏈式棧

# 怎么用C語言實現鏈式棧

## 1. 鏈式棧概述

鏈式棧(Linked Stack)是采用鏈式存儲結構實現的棧。與順序棧不同，鏈式棧不需要預先分配固定大小的存儲空間，而是通過動態內存分配來存儲元素，理論上只要內存足夠就可以無限擴展。

### 1.1 鏈式棧的特點
- 動態內存分配，無需預先確定棧大小
- 插入和刪除操作都在表頭進行，時間復雜度為O(1)
- 不會出現棧滿的情況（除非內存耗盡）
- 每個節點需要額外空間存儲指針，空間利用率略低于順序棧

### 1.2 鏈式棧的基本操作
- 初始化(init)
- 入棧(push)
- 出棧(pop)
- 獲取棧頂元素(top)
- 判斷?？?isEmpty)
- 銷毀棧(destroy)

## 2. 鏈式棧的數據結構設計

### 2.1 節點結構定義

```c
typedef struct StackNode {
    int data;               // 存儲數據（這里以int為例）
    struct StackNode *next; // 指向下一個節點的指針
} StackNode;

2.2 棧結構定義

typedef struct LinkedStack {
    StackNode *top;         // 棧頂指針
    int size;               // 棧中元素個數（可選）
} LinkedStack;

3. 鏈式棧的實現

3.1 初始化棧

void initStack(LinkedStack *stack) {
    stack->top = NULL;     // 棧頂指針初始化為NULL
    stack->size = 0;       // 元素個數初始化為0
}

3.2 判斷棧是否為空

int isEmpty(LinkedStack *stack) {
    return stack->top == NULL;  // 或者 return stack->size == 0;
}

3.3 入棧操作

int push(LinkedStack *stack, int value) {
    // 創建新節點
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return 0; // 入棧失敗
    }
    
    newNode->data = value;
    newNode->next = stack->top; // 新節點指向原棧頂
    stack->top = newNode;       // 更新棧頂指針
    stack->size++;              // 棧大小增加
    return 1; // 入棧成功
}

3.4 出棧操作

int pop(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0; // 出棧失敗
    }
    
    StackNode *temp = stack->top; // 臨時保存棧頂節點
    *value = temp->data;         // 通過指針參數返回棧頂值
    stack->top = temp->next;      // 更新棧頂指針
    free(temp);                   // 釋放原棧頂節點
    stack->size--;                // 棧大小減少
    return 1; // 出棧成功
}

3.5 獲取棧頂元素

int top(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0; // 獲取失敗
    }
    
    *value = stack->top->data; // 通過指針參數返回棧頂值
    return 1; // 獲取成功
}

3.6 銷毀棧

void destroyStack(LinkedStack *stack) {
    StackNode *current = stack->top;
    StackNode *next;
    
    while (current != NULL) {
        next = current->next; // 保存下一個節點地址
        free(current);        // 釋放當前節點
        current = next;       // 移動到下一個節點
    }
    
    stack->top = NULL; // 重置棧頂指針
    stack->size = 0;   // 重置棧大小
}

4. 完整示例代碼

#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

typedef struct LinkedStack {
    StackNode *top;
    int size;
} LinkedStack;

void initStack(LinkedStack *stack) {
    stack->top = NULL;
    stack->size = 0;
}

int isEmpty(LinkedStack *stack) {
    return stack->top == NULL;
}

int push(LinkedStack *stack, int value) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return 0;
    }
    
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
    return 1;
}

int pop(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0;
    }
    
    StackNode *temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    stack->size--;
    return 1;
}

int top(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0;
    }
    
    *value = stack->top->data;
    return 1;
}

void destroyStack(LinkedStack *stack) {
    StackNode *current = stack->top;
    StackNode *next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    stack->top = NULL;
    stack->size = 0;
}

void printStack(LinkedStack *stack) {
    printf("Stack (top to bottom): ");
    StackNode *current = stack->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    LinkedStack stack;
    initStack(&stack);
    
    // 測試入棧
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printStack(&stack); // 輸出: 30 20 10
    
    // 測試獲取棧頂元素
    int topValue;
    if (top(&stack, &topValue)) {
        printf("Top element: %d\n", topValue); // 輸出: 30
    }
    
    // 測試出棧
    int poppedValue;
    pop(&stack, &poppedValue);
    printf("Popped: %d\n", poppedValue); // 輸出: 30
    printStack(&stack); // 輸出: 20 10
    
    // 測試?？张袛?    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No"); // 輸出: No
    
    // 銷毀棧
    destroyStack(&stack);
    printf("Is stack empty after destruction? %s\n", isEmpty(&stack) ? "Yes" : "No"); // 輸出: Yes
    
    return 0;
}

5. 鏈式棧的應用場景

1. 內存受限環境：當系統內存有限且難以預估棧的大小時
2. 遞歸算法：深度不確定的遞歸調用（雖然編譯器通常使用系統棧）
3. 撤銷操作：如文本編輯器的撤銷功能
4. 表達式求值：處理括號匹配、中綴轉后綴等
5. 函數調用：雖然實際由系統棧處理，但原理類似

6. 鏈式棧的變體與擴展

6.1 多棧共享空間

可以通過鏈表實現多個棧共享同一存儲空間，比順序結構的多棧共享更靈活。

6.2 泛型實現

使用void指針或宏定義可以實現支持任意數據類型的鏈式棧：

typedef struct GenericStackNode {
    void *data;
    struct GenericStackNode *next;
} GenericStackNode;

6.3 線程安全版本

通過添加互斥鎖可以實現線程安全的鏈式棧：

#include <pthread.h>

typedef struct ThreadSafeStack {
    StackNode *top;
    int size;
    pthread_mutex_t lock;
} ThreadSafeStack;

7. 常見問題與注意事項

1. 內存泄漏：每次pop操作后必須free節點
2. 空棧檢查：pop和top操作前必須檢查棧是否為空
3. 錯誤處理：malloc可能失敗，需要處理分配失敗的情況
4. 多線程安全：多線程環境下需要額外的同步機制
5. 性能考慮：頻繁的動態內存分配可能影響性能，可考慮內存池優化

8. 總結

鏈式棧通過鏈表結構實現了棧的先進后出特性，相比順序棧具有更好的靈活性，不受固定大小的限制。本文詳細介紹了鏈式棧的數據結構設計、基本操作實現以及相關應用場景。理解鏈式棧的實現原理不僅有助于掌握棧這種基礎數據結構，也為學習更復雜的鏈式結構打下了堅實基礎。

在實際開發中，應根據具體需求選擇順序?；蜴準綏?。對于大小可預估且變化不大的場景，順序棧更為高效；而對于大小不可預知或變化較大的情況，鏈式棧則是更好的選擇。 “`