C 語言實現通用棧：動態擴容、類型參數化與完整接口設計

編輯：關於C語言

C 語言實現通用棧：動態擴容、類型參數化與完整接口設計

設計目標

支持任意數據類型（以 int 為例，可通過宏/修改類型擴展）。
動態擴容：滿時自動增容（realloc）。
完整接口：初始化、銷毀、入棧、出棧、判空、清空、打印。
錯誤處理：返回 Bool 狀態碼，出參帶回數據。

頭文件

// mystack.h
#ifndef MYSTACK_H
#define MYSTACK_H

#include 
#include 

#define MYSTACK_INCREASE_NUM 2  // 每次擴容增量
typedef int ElementType;        // 元素類型，修改此處適配其他類型
typedef int Bool;               // 0 假，非零真

typedef struct {
    ElementType *bottom;  // 棧底指針
    ElementType *top;     // 棧頂指針（指向下一可用位置）
    int size;             // 當前容量
} MyStack;

// 接口聲明
MyStack* initStack(int size);
Bool freeStack(MyStack *stack);
Bool push(MyStack *stack, ElementType data);
Bool pop(MyStack *stack, ElementType *outputData);
Bool isEmpty(MyStack *stack);
void makeStackEmpty(MyStack *stack);
void printStack(MyStack *stack);

#endif

實現文件

// mystack.c
#include "mystack.h"

MyStack* initStack(int size) {
    MyStack *s = (MyStack*)malloc(sizeof(MyStack));
    if (!s) return NULL;
    s->bottom = (ElementType*)malloc(sizeof(ElementType) * size);
    if (!s->bottom) { free(s); return NULL; }
    s->top = s->bottom;      // 空棧：top == bottom
    s->size = size;
    return s;
}

Bool freeStack(MyStack *s) {
    if (!s) return 0;
    free(s->bottom);
    free(s);
    return 1;
}

Bool push(MyStack *s, ElementType data) {
    if (!s) return 0;
    // 動態擴容
    if (s->top - s->bottom >= s->size) {
        ElementType *new_bottom = (ElementType*)realloc(s->bottom, 
            sizeof(ElementType) * (s->size + MYSTACK_INCREASE_NUM));
        if (!new_bottom) return 0;
        s->top = new_bottom + s->size;  // 修正 top 指針
        s->bottom = new_bottom;
        s->size += MYSTACK_INCREASE_NUM;
    }
    *s->top = data;  // 存值
    s->top++;        // 指針後移
    return 1;
}

Bool pop(MyStack *s, ElementType *out) {
    if (!s || isEmpty(s)) { printf("stack is empty\n"); return 0; }
    s->top--;               // 先回退指向頂部元素
    *out = *s->top;         // 取值
    return 1;
}

Bool isEmpty(MyStack *s) {
    return s && s->bottom == s->top;
}

void makeStackEmpty(MyStack *s) {
    if (s) s->top = s->bottom;
}

void printStack(MyStack *s) {
    if (!s) return;
    if (isEmpty(s)) { printf("stack is empty\n"); return; }
    for (ElementType *p = s->bottom; p != s->top; p++)
        printf("%d\n", *p);
}

測試用例

// stacktest.c
#include "mystack.h"
#include 

int main() {
    MyStack *s = initStack(2);
    push(s, 1); push(s, 2);
    printStack(s);           // 1 2
    
    push(s, 3);              // 觸發擴容
    printStack(s);           // 1 2 3
    
    int a, b, c;
    pop(s, &a); pop(s, &b);  // 3, 2
    push(s, 4);
    pop(s, &c);              // 4
    printf("a=%d b=%d c=%d\n", a, b, c);  // 3 2 4
    
    makeStackEmpty(s);
    pop(s, &a);              // stack is empty
    printf("a=%d\n", a);     // 4 (未修改)
    
    freeStack(s);
    return 0;
}

關鍵設計點解析

設計點	實現方式	優勢
頂部指針語義	`top` 指向下一可用位置	空棧判斷簡單（`top==bottom`），入棧先存值後 `top++`
動態擴容	`realloc` + 固定增量	避免頻繁分配，`MYSTACK_INCREASE_NUM` 可調
擴容後指針修正	`top = new_bottom + old_size`	保證數據連續性，`top-bottom` 仍為元素數
出棧順序	先 `top--` 再取值	`top` 指向下一位，頂部元素在 `top-1`
類型參數化	頭文件 `typedef ElementType`	修改一處適配任意類型（結構體需注意深拷貝）