数据结构：栈的原理与 C 语言实现

2. 源文件实现 (Stack.c)

源文件包含具体的函数逻辑。在编写过程中，有几个关键点需要特别注意。

初始化与销毁

初始化时需将内存置空，容量设为 0。销毁时不仅要释放内存，还要将指针置为 NULL，防止悬空指针。

#include "Stack.h"

// 初始化栈
void StackInit(Stack* ps) {
    assert(ps); // 断言检查空指针
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

// 销毁栈
void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

入栈与动态增容

当栈空间不足时，需要进行扩容。直接一次性开辟过大空间会浪费内存，过小则会频繁触发扩容降低效率。经验表明，每次扩容为原容量的 2 倍是一个较好的平衡点。

// 入栈
void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    
    // 检查是否需要扩容
    if (ps->size == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        
        if (tmp == NULL) {
            perror("realloc");
            return;
        }
        
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    
    ps->a[ps->size] = data;
    ps->size++;
}

出栈与访问

出栈只需减小 size 计数即可，无需真正删除数组末尾的元素，因为下次写入时会覆盖它。获取栈顶元素时，需注意下标是 size - 1。

// 出栈
void StackPop(Stack* ps) {
    assert(ps && ps->size > 0);
    ps->size--;
}

// 获取栈顶元素
STDataType StackTop(Stack* ps) {
    assert(ps && ps->size > 0);
    return ps->a[ps->size - 1];
}

// 获取有效元素个数
int StackSize(Stack* ps) {
    assert(ps);
    return ps->size;
}

// 检测栈是否为空
int StackEmpty(Stack* ps) {
    assert(ps);
    return ps->size == 0;
}

3. 测试用例 (Test.c)

通过简单的测试验证功能是否正常。例如依次压入 1 到 6，然后弹出几个元素并查看栈顶值。

#include "Stack.h"

int main() {
    Stack S;
    StackInit(&S);
    
    StackPush(&S, 1);
    StackPush(&S, 2);
    StackPush(&S, 3);
    StackPush(&S, 4);
    StackPush(&S, 5);
    StackPush(&S, 6);
    
    StackPop(&S);
    int ret1 = StackTop(&S);
    
    StackPop(&S);
    int ret2 = StackTop(&S);
    
    StackPop(&S);
    int ret3 = StackTop(&S);
    
    printf("%d %d %d\n", ret1, ret2, ret3);
    
    StackDestroy(&S);
    return 0;
}

四、总结

栈的实现相对简单，但涉及到的内存管理细节不容忽视。重点掌握以下几点：

1. LIFO 原则：始终在栈顶操作。
2. 动态扩容：使用 realloc 配合合理的倍数策略。
3. 健壮性：利用 assert 处理空指针和非法状态。
4. 资源清理：程序结束前务必释放动态分配的内存。

理解栈的实现有助于深入掌握内存布局及数据结构的基础逻辑。