設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置： 程式碼之家 >> 編程語言 >  >> C語言 >> C >> C 語言入門

C 語言數據結構：順序棧與鏈式棧完整實現指南

     編輯：C 語言入門

棧是僅允許在表尾（棧頂）進行插入/刪除的線性表，遵循後進先出（LIFO）原則。本文基於嚴蔚敏《數據結構》（C 語言版）接口規範，提供順序棧（動態擴容）與鏈式棧兩種完整實現，包含初始化、銷毀、清空、判空、求長、取頂、入棧、出棧、遍歷等九大核心操作，代碼符合生產級健壯性標準。

棧的抽象數據類型 (ADT) 定義

ADT Stack {
    數據對象: D = {a₀, a₁, ..., aₙ₋₁} (n≥0)
    數據關係: R = { | 1≤i

實現一：順序棧（動態數組 + 自動擴容）

結構設計

#define STACK_INIT_SIZE 100   // 初始容量
#define STACK_INCREMENT 10    // 擴容增量

typedef int DataType;         // 元素類型，可按需修改

typedef struct {
    DataType *base;           // 棧底指針，指向動態數組首地址
    DataType *top;            // 棧頂指針，指向下一個可用位置
    int stackSize;            // 當前分配容量
} SqStack, *PSqStack;

約定：top == base 表示空棧；top - base == stackSize 觸發擴容；base == NULL 表示棧不存在。

核心操作實現

1. 初始化

PSqStack InitStack(PSqStack s) {
    s = (PSqStack)malloc(sizeof(SqStack));
    if (!s) return NULL;
    s->base = (DataType*)malloc(STACK_INIT_SIZE * sizeof(DataType));
    if (!s->base) { free(s); return NULL; }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
    return s;
}

2. 入棧（自動擴容）

int Push(PSqStack s, DataType e) {
    if (!s) return 0;
    // 滿棧檢查與擴容
    if (s->top - s->base >= s->stackSize) {
        DataType *newBase = (DataType*)realloc(s->base, 
            (s->stackSize + STACK_INCREMENT) * sizeof(DataType));
        if (!newBase) return 0;  // 擴容失敗
        s->top = newBase + (s->top - s->base);  // 修正 top 指針
        s->base = newBase;
        s->stackSize += STACK_INCREMENT;
    }
    *s->top++ = e;  // 賦值並後移 top
    return 1;
}

3. 出棧

int Pop(PSqStack s, DataType *e) {
    if (!s || s->top == s->base) return 0;  // 空棧
    *e = *--s->top;  // 先回退再取值
    return 1;
}

4. 其他操作

int StackEmpty(PSqStack s) { return s && s->top == s->base; }
int StackLength(PSqStack s) { return s ? s->top - s->base : -1; }
int GetTop(PSqStack s, DataType *e) { 
    if (!s || s->top == s->base) return 0;
    *e = *(s->top - 1); 
    return 1; 
}
void ClearStack(PSqStack s) { if (s) s->top = s->base; }
void DestroyStack(PSqStack s) { 
    if (s) { free(s->base); free(s); } 
}
void StackTraverse(PSqStack s, void (*visit)(DataType)) {
    if (!s) return;
    for (DataType *p = s->base; p < s->top; ++p) visit(*p);
}

實現二：鏈式棧（單鏈表頭插法）

結構設計

typedef struct LNode {
    DataType data;
    struct LNode *next;
} LNode, *LinkStack;

約定：頭節點不存數據，head->next 指向棧頂節點。空棧時 head->next == NULL。此設計統一了插入/刪除邏輯，無需特判首節點。

核心操作實現

1. 初始化

LinkStack InitStack() {
    LinkStack s = (LinkStack)malloc(sizeof(LNode));
    if (s) s->next = NULL;
    return s;
}

2. 入棧（頭插法 O(1)）

int Push(LinkStack s, DataType e) {
    if (!s) return 0;
    LNode *node = (LNode*)malloc(sizeof(LNode));
    if (!node) return 0;
    node->data = e;
    node->next = s->next;
    s->next = node;
    return 1;
}

3. 出棧

int Pop(LinkStack s, DataType *e) {
    if (!s || !s->next) return 0;
    LNode *top = s->next;
    *e = top->data;
    s->next = top->next;
    free(top);
    return 1;
}

4. 其他操作

int StackEmpty(LinkStack s) { return s && !s->next; }
int StackLength(LinkStack s) {
    int len = 0;
    for (LNode *p = s ? s->next : NULL; p; p = p->next) ++len;
    return len;
}
int GetTop(LinkStack s, DataType *e) {
    if (!s || !s->next) return 0;
    *e = s->next->data;
    return 1;
}
void ClearStack(LinkStack s) {
    if (!s) return;
    LNode *p = s->next;
    while (p) {
        LNode *tmp = p;
        p = p->next;
        free(tmp);
    }
    s->next = NULL;
}
void DestroyStack(LinkStack *s) {  // 雙重指針修改頭指針
    if (!s || !*s) return;
    ClearStack(*s);
    free(*s);
    *s = NULL;
}
void StackTraverse(LinkStack s, void (*visit)(DataType)) {
    for (LNode *p = s ? s->next : NULL; p; p = p->next) visit(p->data);
}

兩種實現深度對比

維度順序棧鏈式棧
空間分配連續記憶體，預分配+擴容離散節點，按需分配
空間利用率可能有預留閒置零碎片，但每節點額外指針開銷
擴容性能偶發 O(n) realloc 拷貝每次 O(1) 分配，無擴容
訪問速度緩存友好，CPU 預取優勢指針追蹤，緩存未命中率高
最大容量受限於連續記憶體可用性僅受限於總堆內存
適用場景高頻操作、容量可預估、對性能敏感容量極不確定、長壽命、內存碎片化環境

測試驗證主程序

void PrintElement(DataType e) { printf("%d ", e); }

int main() {
    printf("=== 順序棧測試 ===\n");
    PSqStack sq = InitStack(NULL);
    for (int i = 1; i <= 5; ++i) Push(sq, i*10);
    printf("長度: %d\n", StackLength(sq));
    StackTraverse(sq, PrintElement); putchar('\n');
    DataType e; Pop(sq, &e); printf("出棧: %d\n", e);
    StackTraverse(sq, PrintElement); putchar('\n');
    DestroyStack(sq);

    printf("\n=== 鏈式棧測試 ===\n");
    LinkStack lk = InitStack();
    for (int i = 1; i <= 5; ++i) Push(lk, i*100);
    printf("長度: %d\n", StackLength(lk));
    StackTraverse(lk, PrintElement); putchar('\n');
    Pop(lk, &e); printf("出棧: %d\n", e);
    StackTraverse(lk, PrintElement); putchar('\n');
    DestroyStack(&lk);
    return 0;
}

工程級增強建議

  1. 泛型化：用 void* 元素 + 銷毀回調函數，支持任意類型
  2. 線程安全：加入 pthread_mutex_t 實現並發訪問保護
  3. 錯誤碼細化：區分配置失敗、空棧、參數非法等錯誤類型
  4. 迭代器模式：提供 StackIterator 替代回調遍歷，支持中斷/嵌套
  5. 內存池：頻繁創建銷毀場景下，鏈式棧節點可用對象池管理

棥雖簡單，卻是編譯器語法分析、函數調用棧、表達式求值、瀏覽器前進後退、撤銷重做等無數系統的核心骨架。掌握其兩種經典實現及優劣權衡，是從「會用庫」進階為「能造輪子」的關鍵一步。

  1. 上一篇文章：
  2. 下一篇文章：
C 語言入門
嵌入式C語言核心知識體系：數據類型、指針進階、關鍵字與可變參數深度解析 嵌入式C語言核心知識體系：數據類型、指針進階、關鍵字與可變參數深度解析

跨平台數據類型尺寸：移植性的基石 嵌入式開發頻繁面對 16/
C 語言 memcpy 函數深度解析：從錯誤實現到標準庫級優化 C 語言 memcpy 函數深度解析：從錯誤實現到標準庫級優化

前言：一次失敗的面試經驗 昨天嘗試手寫 memcpy 函數，
C 語言指標完全圖解：從直接引用到函數指標、字串操作與動態記憶體 C 語言指標完全圖解：從直接引用到函數指標、字串操作與動態記憶體

核心概念：直接引用 vs 間接引用 直接引用：透過變數名

C 語言聯合體 深度解析：記憶體佈局、大小計算與實戰應用 C 語言聯合體 深度解析：記憶體佈局、大小計算與實戰應用

聯合體四大核心特性 結構本質：聯合體是一種特殊結構 零偏移
C語言字符串拼接實戰：無庫函數、無冗餘、O(n)極簡實現 C 語言 memcpy 函數深度解析：從錯誤實現到標準庫級優化 C 語言指標與自增運算子結合的運算順序完整解析 無窮級數求 e^x 近似值 C++ 實作 C 語言實戰經驗談：從 scanf 陷阱到記憶體管理的常見錯誤與最佳實踐 C語言科學計算器完整實現：表達式解析、中綴轉後綴、棧式計算、錯誤處理與交互循環 C語言動態內存管理核心：malloc/free 與指標的協作機制
欄目導航
  • C 語言基礎
  • C 語言入門
  • 關於C
  • C 語言實例練習
  • C 語言問答
    • Copyright © 程式碼之家 All Rights Reserved