C语言从零实现栈：动态数组、内存管理与边界条件全解析

写数据结构，最忌讳的事情就是照着教科书把代码敲一遍，然后自我感动。尤其像栈这种“看起来简单”的结构，很多人觉得不就是push和pop嘛，能有什么技术含量。但真实开发里，栈是递归、表达式求值、函数调用、回溯算法这些复杂逻辑的地基，地基没打牢，上面盖什么都是危房。

我用C语言从零写了一个通用的栈，这个过程中踩了不少坑，也理清了很多之前模糊的概念。这篇文章不是简单丢个代码让你抄，而是把从需求分析、结构设计、边界问题到实战应用的全过程拆开揉碎了讲清楚，适合刚学完指针和结构体、准备深入数据结构的读者，也适合想回头夯实基础的“老手”重新审视自己对内存和边界条件的理解。

1. 一个看似简单的问题：为什么还得从零写栈

1.1 栈是什么，后进先出到底是什么意思

栈的本质是一个受限的线性表，只允许在表尾进行插入和删除。这个“表尾”在栈的语境里叫栈顶。后进先出（LIFO）是所有操作的逻辑基础：最后压进去的元素最先被弹出。

但很多人对“后进先出”的理解停留在背诵层面，真正写代码的时候才发现问题：栈顶指针到底指向最后一个元素还是最后一个元素的下一个位置？容量不够了怎么办？pop的时候要不要把数据清掉？这些细节才是“会”和“懂”之间的差距。

生活里的类比很容易理解——一摞盘子，后放上去的盘子总是最先被拿走。这个类比能解释逻辑，但解释不了内存布局。写C语言的栈，本质上是在管理一块连续内存，把它的“使用规律”严格限制成后进先出。而这种内存管理的精细程度，正是C语言区别于其他高级语言的地方。

1.2 从零写栈的价值，远不止“学会一个数据结构”

我见过不少能用Python几行代码把栈写得“很优雅”的人，换到C语言就懵了。原因很简单：C语言没有现成的容器库，一切内存都要自己管。这个过程逼着你思考三个问题：数据存在哪里、生命周期多长、谁负责释放。

这三问，其实就是C语言开发的三大核心命题。一旦在一棵简单的栈上想明白了，后面写队列、二叉树、哈希表都是同样的套路。

我在某项目里遇到过一段非常典型的代码：结构体数组存了一堆任务，元素按照后进先出的方式取用，但写这段代码的开发者直接用了一个固定大数组，没用栈的结构去约束它。结果就是代码里到处是top--和top++的散装逻辑，稍不注意就越界。后来我把它统一封装成栈的接口，安全性和可读性都上了一个台阶。

从零写栈这件事，表面上是写一个数据结构，实际上是在训练“接口设计能力”和“边界条件意识”。

1.3 这篇文章能让你获得什么

这篇文章会带你一步步实现一个基于动态数组的栈，覆盖完整的生命周期管理：初始化、入栈、出栈、取栈顶、判空、获取栈大小、扩容、销毁。每一段代码我都会解释为什么这么写，而不是让你背下来。

之后我会额外分析几个高频bug，比如扩容之后指针失效、误传结构体副本、漏掉容量自增导致的内存越界。最后用三个实战场景把栈用起来：括号匹配、中缀表达式转后缀表达式、用迭代模拟递归。

读完再回头看那些“会用STL stack”的人，你会明显感觉到自己和他们不在一个层次。

2. 设计先行：定接口远比写代码重要

2.1 先把操作定下来，对外只暴露必要接口

写任何数据结构的第一步，不是打开编辑器，而是把对外提供的操作列清楚。我最终定了七个核心接口，刚好覆盖所有常规使用场景：

接口的定义直接决定了调用方怎么用。这里有一个很重要的设计点：pop和top必须分开。很多初学者会把“弹出并获取栈顶”写成一个函数，这在某些场景下没问题，但如果你想先看一眼栈顶再决定是否弹出，就不得不重新压回去，非常别扭。

比如括号匹配算法里，遇到右括号时你先要看栈顶是不是匹配的左括号，如果是才弹出，不是则直接报错。这个场景天然要求top和pop分开。

2.2 底层实现三种方案，先对比再选择

栈的底层实现无外乎三种思路，各有优劣，先看对比再决定怎么写：

定长数组适合容量可预估的小场景，比如解析一段固定格式的文本，栈深度最多几十层。但一旦你预估错了，栈溢出就会以最难查的数组越界形式出现——轻则数据错乱，重则段错误。

链表的好处是每次压入一个节点就当场分配内存，不需要预留容量，也不用搬移已有数据。缺点也很明显：内存碎片化、每个节点多存一个next指针、CPU缓存的局部性极差。如果你在递归算法里频繁入栈出栈，链表的节点反复malloc和free，性能损失会非常显著。

动态数组是工程实践里最常用的方案，结合了数组的缓存友好和链表的动态性。通过扩容策略，把每次入栈操作的均摊时间复杂度控制在O(1)。

2.3 为什么我把“存储颗粒度”定为整数类型

实现的时候，很多人会纠结一个问题：栈里到底存什么类型？整数？结构体？任意类型？

我在这篇里把元素类型定义为int，这么做有几点考虑。首先，C语言的数据结构教学里，最忌讳一上来就搞复杂的泛型宏或者void*抽象，那会把注意力从“栈本身的逻辑”拉到“类型系统的复杂度”上去。其次，int是最简单的可拷贝类型，能让你清晰地看到入栈出栈时数据的流向，不会被深拷贝、浅拷贝这类问题干扰。

但这不代表你以后就只能用int。代码写完之后，你要理解的关键点在于：栈管的是“数据本身”还是“数据的副本”。存int时，入栈是拷贝一份值进去；如果存结构体，你需要考虑是复制整个结构体，还是只复制一个指针。这个判断放到了后面的扩展部分讲，现在先把基础打牢。

3. 核心代码实现：动态数组栈的完整落地

3.1 结构体定义与初始化，容量与栈顶的初始状态

栈结构体我设计成三要素：数据指针、栈顶索引、当前容量。C语言里对这三个字段的定义直接决定了操作的边界条件写起来是简单还是繁琐。

c复制#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define STACK_INIT_CAPACITY 8

typedef struct {
    int *data;
    int top;        // 指向栈顶元素的下标，空栈时为 -1
    int capacity;   // 当前分配的数组容量
} Stack;

top的初始值很关键。我选择了-1表示空栈。这样当push第一个元素时，先将top自增到0，再往data[0]里放值，逻辑非常顺。如果初始化为0，则空栈时top指向的是第一个空位，判断空就得改成top == 0，计算元素个数则是top本身。两种方案都可行，但一旦选定，所有边界条件都必须围绕同一个约定来写，混了必出事。

初始化函数负责分配初始内存，并设置好初始状态：

c复制bool stack_init(Stack *s) {
    s->data = (int*)malloc(sizeof(int) * STACK_INIT_CAPACITY);
    if (s->data == NULL) {
        return false;
    }
    s->top = -1;
    s->capacity = STACK_INIT_CAPACITY;
    return true;
}

这里有个很容易被忽略的细节：参数必须传指针。如果你写成bool stack_init(Stack s)，函数内部无论如何修改，外面的s都不会有任何变化。C语言的函数参数本质上都是值传递，结构体也不例外。我见过不少初学者在这上面栽了跟头，函数执行完之后data还是个野指针，程序直接崩溃。

3.2 入栈与扩容：均摊O(1)的核心技巧

入栈操作是栈最核心的功能，而动态数组栈的精髓在于扩容策略。

c复制static bool stack_resize(Stack *s, int new_capacity) {
    int *new_data = (int*)realloc(s->data, sizeof(int) * new_capacity);
    if (new_data == NULL) {
        return false;
    }
    s->data = new_data;
    s->capacity = new_capacity;
    return true;
}

bool stack_push(Stack *s, int value) {
    if (s->top + 1 >= s->capacity) {
        int new_capacity = s->capacity * 2;
        if (!stack_resize(s, new_capacity)) {
            return false;
        }
    }
    s->top++;
    s->data[s->top] = value;
    return true;
}

扩容为什么翻倍而不是加固定值？数学原因很简单：如果每次push都触发扩容，假设初始容量为m，插入n个元素，总扩容成本是m + m + 2m + 4m + ... ，加起来约等于2n，均摊到每个push就是O(1)。如果每次只扩固定大小，比如加8个，那扩容总成本就是8 + 16 + 24 + ...，量级变成O(n²)，大量数据时性能会急剧恶化。

realloc这个函数可能是扩展了新内存，也可能直接在原地扩大。如果原地扩不了，它会拷贝旧数据到新位置并释放旧内存。这里就出现一个经典问题：realloc返回新地址后，原来的data指针可能已经失效了，所以必须把返回值赋值回去。

但这里还有个陷阱——如果realloc失败，原来的指针还是有效的，但你直接把NULL赋给了data，旧内存就泄漏了。所以上面的写法用了一个临时变量new_data先接收结果，判断成功后才赋值给s->data，这个习惯一定要养成。

入栈时的另一个细节是顺序：先判断容量，再自增top，最后写入数据。如果把top++和写入的顺序颠倒，在调试时很容易观察到中间状态异常。保持“先扩容、再移动游标、最后落数据”的顺序，逻辑最清晰。

3.3 出栈与取栈顶：到底要不要清理数据

出栈和取栈顶看起来简单，但有不少讲究。

c复制bool stack_pop(Stack *s, int *out_value) {
    if (s->top == -1) {
        return false;
    }
    if (out_value != NULL) {
        *out_value = s->data[s->top];
    }
    s->top--;
    return true;
}

bool stack_top(Stack *s, int *out_value) {
    if (s->top == -1) {
        return false;
    }
    if (out_value != NULL) {
        *out_value = s->data[s->top];
    }
    return true;
}

出栈时很多人会纠结：要不要把data[top]置为0？我给出的答案是：不需要。原因很简单，栈的逻辑长度由top决定，top--之后，那块内存就属于“不会被访问的区域”了。如果后续入栈覆盖它，旧值自然被新值替代。置零只是白白增加开销。

但你必须理解，这叫“逻辑上的删除”，不是“物理上的删除”。data[top]的内存里还残留着旧数据，只是栈的接口不允许你访问它。这不是bug，而是行为约定。如果你做的是内存敏感的嵌入式开发，且栈里存的是指针，那就一定要在pop时把这部分逻辑处理好（比如先手动释放指针指向的资源），否则会内存泄漏。

出栈和取栈顶都用int *out_value这个输出参数，而不是直接返回int，原因在于错误处理。空栈时无法弹出，我们需要给调用方一个明确的失败信号。用返回值表达成功失败、用输出参数传数据，是C语言中非常经典的接口设计模式。

3.4 辅助接口与销毁：干净利落地收尾

栈的辅助接口和销毁逻辑，是很多人写代码时最容易敷衍的部分，但恰恰是这里最容易出问题。

c复制bool stack_is_empty(Stack *s) {
    return s->top == -1;
}

int stack_size(const Stack *s) {
    return s->top + 1;
}

void stack_destroy(Stack *s) {
    free(s->data);
    s->data = NULL;
    s->top = -1;
    s->capacity = 0;
}

stack_size计算方式是top + 1，这正好能跟我们选择top = -1表示空栈的约定对上。如果你在初始化时选择了top = 0表示空栈，那这里就要写top，同时判空条件也要改成top == 0。一整套约定保持一致，是你长期维护代码的前提。

stack_destroy里最容易被忽略的是：free(s->data)之后，原来的指针变成了悬垂指针。如果不置为NULL，万一后面有人粗心地在销毁后再次调用push，代码就会在已经释放的内存上写数据，这几乎必然导致崩溃或数据损坏。置空之后，至少后续操作会因为非法访问而快速暴露问题，而不是在莫名其妙的地方翻车。

很多初学者会问：销毁之后要不要把s->data = NULL？答案是要。这就是一个“宁可代码多一行，也要把状态搞干净”的习惯。

3.5 完整测试代码：用实际运行检验实现

写完一堆API之后，如果不用一段完整的测试代码把每个接口过一遍，你根本不知道自己写的东西能不能跑。我一般会写一个简单但覆盖面足够广的测试程序，把正常流程、边界条件、错误处理全部验证一遍。

c复制int main(void) {
    Stack stack;
    if (!stack_init(&stack)) {
        fprintf(stderr, "init failed\n");
        return 1;
    }

    for (int i = 0; i < 100; i++) {
        stack_push(&stack, i);
    }
    printf("size = %d\n", stack_size(&stack));

    while (!stack_is_empty(&stack)) {
        int value;
        stack_pop(&stack, &value);
        if (value < 95) {
            printf("poped: %d\n", value);
        }
    }
    printf("size after pop all = %d\n", stack_size(&stack));

    int top_value;
    if (!stack_top(&stack, &top_value)) {
        printf("top on empty stack failed as expected\n");
    }

    stack_destroy(&stack);
    return 0;
}

这个测试覆盖了三个关键场景：大量入栈触发多次扩容、连续出栈直到清空、在空栈上执行top验证错误返回。如果你想更严谨，可以把循环次数改成10000甚至100000，再用内存检测工具跑一遍，看有没有泄漏和越界。后面“问题排查”部分会展开讲。

4. 高频bug实录：这些坑我全踩过

4.1 扩容之后指针失效：最常见的隐蔽炸弹

动态数组栈最重要也最易错的问题，就是扩容带来的地址变化。当realloc决定把数据搬到一个更大的内存区域时，原来data指向的地址就失效了。如果你在代码的别处保存过这个地址的副本，那么你手里握着的就是一个悬垂指针，再用它读写数据，后果不可预测。

我测试时就遇到过这种情况：在push之前把stack.data存到另一个变量里，入栈几次导致扩容后，再用那个旧指针去读数据，看到的全是乱码。我排查了很久才发现是旧地址已经失效。

这类问题的回避方式很粗暴也有效：永远不要把内部data指针暴露给外部，所有访问都通过push、pop、top这些接口进行。这是“封装”的意义所在。如果你觉得“直接把内部指针拿出去用很方便”，那么你迟早要为这个方便付出代价。

4.2 误传结构体副本：修改全都白费

这个坑我曾经反复踩。看代码：

c复制void stack_push_bad(Stack s, int value) {
    // 操作的是s的副本，外部栈完全没变
    s.data[s.top + 1] = value;
    s.top++;
}

很多人在第一次接触结构体传参时，都会写出类似的代码。C语言里结构体作为参数传递时，会把整个结构体拷贝一份。函数内部确实修改了参数，但修改的只是副本，函数返回后主调函数里的Stack纹丝不动。

这个bug的隐蔽之处在于：当栈很小、内存没有越界迹象时，程序可能“碰巧”能正常运行，你甚至会以为自己写对了。但一旦数据量增大，top值不同步，各种诡异行为就会接连冒出来。

从第一次写栈开始，就要养成“修改结构体内容必须传指针”的肌肉记忆。这也是为什么标准库里所有可能改动栈状态的函数，参数都写成Stack *s。

4.3 内存泄漏与越界：用检测工具把问题扼杀

栈写好了，不代表就万事大吉。C语言的内存错误靠人肉找，非常痛苦，正确姿势是交给工具。我在写完这个栈后，用内存检测工具做了一次全量检查，没有任何输出。这不算奇迹，只是说明基本的malloc/free配对和边界处理做对了。

如果你想验证自己的栈有没有泄漏，可以试试把测试程序里主循环的压入和弹出次数加大，然后重点检查三个方向：

另外我强烈建议自己手动设计几个边界case：容量恰好满时再push一次、容量为1时压入两个元素、空栈时连续pop三次。这些case看起来简单，却能快速暴露你在容量判断和边界处理上的纰漏。

4.4 测试驱动：把断言写进测试代码里

如果有条件，我建议在测试代码里直接用断言，而不是用肉眼去看打印结果。这样当出栈顺序出错时，程序会在出错的第一时间停止并给出具体位置，而不是打印一大屏数据之后你还要人肉比对。

c复制#include <assert.h>

// 在测试中验证“后进先出”的核心性质
stack_push(&stack, 10);
stack_push(&stack, 20);
stack_push(&stack, 30);

int v;
stack_pop(&stack, &v);
assert(v == 30);
stack_pop(&stack, &v);
assert(v == 20);
stack_pop(&stack, &v);
assert(v == 10);
assert(stack_is_empty(&stack));

这段代码从本质上验证了栈的“后进先出”特性，而不是简单地看某个数值对不对。以后你哪怕改动内部实现，只要这个测试还能跑过，就说明核心行为没有被破坏。

5. 把栈真正用起来：三个实战例子

5.1 括号匹配：最经典的入门应用

栈最有代表性的应用就是括号匹配。给定一个字符串(([]){})，怎么判断它是否合法？思路是：遇到左括号就入栈，遇到右括号就取栈顶对比，匹配就弹出，不匹配直接报错；遍历完字符串之后，如果栈为空，说明全部匹配。

我在实现的时候用switch处理字符类型，这比写一长串if清晰得多：

c复制bool is_matching_pair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

bool check_brackets(const char *str) {
    Stack stack;
    if (!stack_init(&stack)) {
        return false;
    }

    for (const char *p = str; *p; p++) {
        if (*p == '(' || *p == '[' || *p == '{') {
            stack_push(&stack, *p);
        } else if (*p == ')' || *p == ']' || *p == '}') {
            int top_ch;
            if (!stack_top(&stack, &top_ch) || !is_matching_pair((char)top_ch, *p)) {
                stack_destroy(&stack);
                return false;
            }
            stack_pop(&stack, NULL);
        }
    }

    bool ok = stack_is_empty(&stack);
    stack_destroy(&stack);
    return ok;
}

这个例子把top和pop分开的价值表现得淋漓尽致：遇到右括号时，要先“看一眼”栈顶元素是否匹配，匹配了才“弹出”。如果当初把两者合并成一个函数，这里就会很别扭。

5.2 中缀转后缀表达式：栈处理运算优先级

另一个经典应用是把中缀表达式3 + 4 * 2转换为后缀表达式3 4 2 * +。算法思路不复杂：遇到数字直接输出；遇到运算符时，如果栈顶运算符优先级不低于当前运算符，就把栈顶弹出输出，然后当前运算符入栈；遇到左括号直接入栈，右括号则不断弹出直到左括号。

转换完成后，再配合一个栈做后缀表达式求值，就能实现一个完整的计算器。这个例子很好地说明了栈如何解决“当前操作符要不要等后面的操作符”这类带优先级的问题。

我在自己的实现中给运算符定义了优先级：乘除为2，加减为1。转换算法的核心代码如下：

c复制int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

void infix_to_postfix(const char *infix, char *postfix, int postfix_len) {
    Stack stack;
    stack_init(&stack);
    int j = 0;

    for (const char *p = infix; *p; p++) {
        if (*p >= '0' && *p <= '9') {
            if (j > 0) postfix[j++] = ' ';
            postfix[j++] = *p;
        } else if (*p == '(') {
            stack_push(&stack, *p);
        } else if (*p == ')') {
            int top_ch;
            while (stack_top(&stack, &top_ch) && (char)top_ch != '(') {
                postfix[j++] = ' ';
                postfix[j++] = (char)top_ch;
                stack_pop(&stack, NULL);
            }
            stack_pop(&stack, NULL); // 弹出左括号
        } else {
            int top_ch;
            while (stack_top(&stack, &top_ch) &&
                   (char)top_ch != '(' &&
                   precedence((char)top_ch) >= precedence(*p)) {
                postfix[j++] = ' ';
                postfix[j++] = (char)top_ch;
                stack_pop(&stack, NULL);
            }
            stack_push(&stack, *p);
        }
    }

    while (stack_top(&stack, &top_ch)) {
        postfix[j++] = ' ';
        postfix[j++] = (char)top_ch;
        stack_pop(&stack, NULL);
    }
    postfix[j] = '\0';
    stack_destroy(&stack);
}

这个算法完全依赖栈的两个性质：保存“等待中的运算符”，以及在正确的时机（遇到右括号或更低优先级运算符）把栈顶元素弹出。

5.3 用栈模拟递归：把函数调用过程搬到显式内存

最后一个例子有点进阶，但非常能体现栈的本质。递归函数在执行时，每次调用都会在系统调用栈上压入一个“栈帧”，里面保存着局部变量和返回地址。如果我们手动用栈来模拟这个过程，就能把递归改写为迭代，从而避免系统栈溢出的风险。

以经典的“十进制转二进制”为例，递归写法是：

c复制void dec_to_bin_recursive(unsigned int n) {
    if (n > 1) {
        dec_to_bin_recursive(n / 2);
    }
    putchar('0' + (n % 2));
}

用栈模拟递归时，思路变成：先不断把n % 2的结果入栈，同时把n除以2，直到n变成0，再依次出栈输出。这个过程的本质是“延迟输出顺序”，恰好是栈的天然能力。

c复制void dec_to_bin_iterative(unsigned int n) {
    Stack stack;
    stack_init(&stack);

    if (n == 0) {
        putchar('0');
        stack_destroy(&stack);
        return;
    }

    while (n > 0) {
        stack_push(&stack, n % 2);
        n /= 2;
    }

    int bit;
    while (stack_pop(&stack, &bit)) {
        putchar('0' + bit);
    }
    putchar('\n');
    stack_destroy(&stack);
}

这个例子非常直观：递归是系统替你把中间状态压栈，迭代是你自己手动压栈。当你理解了这一点，以后再遇到那些把递归改成迭代的问题（比如深度优先搜索非递归实现），就不会觉得玄学了。

6. 从int到任意类型：进阶扩展方向

6.1 用void*元素指针实现通用栈

如果你已经把上面的int版本吃透了，下一步可以尝试把栈推广为可以存储任意类型。最常用的办法是把元素类型改成void*，入栈时传入指针，出栈时返回指针。

c复制typedef struct {
    void **data;
    int top;
    int capacity;
} GenericStack;

这里的本质变化是：data从int*变成了void**，每一个元素不再是一个整数，而是一个指向任意数据的指针。入栈时存的是指针的副本，而出栈时拿到的是指针，你自己决定要不要释放它指向的内存。这个能力让栈从“只能存整数”变成了“能存任何东西”。

但要特别提醒：存指针意味着你要自己保证指针指向的内存生命周期。如果指针指向堆内存，且压入之后不再有其他地方保存该指针，那你pop之后不释放就会泄漏；如果释放了但外部还在用，就会悬垂。类型由int变成void*，数据结构本身变简单了，内存管理复杂度却上去了。

这部分代码我不展开贴了，核心是把stack_push的入参从int value改成void *value，把int *out改成void **out，扩容时realloc的大小改成sizeof(void*) * capacity。

6.2 线程安全与栈的工程化改造

如果你的栈要用在多线程环境里，那就要考虑并发访问问题。最直接的做法是给Stack加一把互斥锁，在push、pop、top等所有可能改动状态的接口处加锁。但加锁带来的性能损失不可避免，所以工程实践中通常会用无锁栈、或者根据读写比例选择更精细的同步策略。

在单线程场景里，我上面实现的栈已经可以高效工作了。如果你只是做练习题或者应付面试，完全没有必要为“线程安全”提前复杂化。先把基础版本的逻辑和边界条件搞扎实，再去研究并发问题，这是一个更合理的学习路径。

6.3 我个人的实操体会

从零写这个栈的过程，最大的收获不是那份代码，而是建立了一套分析和验证数据结构的习惯。现在我看到任何一个新数据结构，第一反应都是先列操作接口、再选底层结构、然后逐一考虑边界条件、最后写测试验证性质。这个流程适用于队列、链表、二叉树，也适用于以后任何自定义数据结构。

另外想强调一个反直觉的经验：代码越短，越不能掉以轻心。栈的完整代码加起来不超过150行，但其中每一行都可能有深坑。top初始值选择、扩容时realloc返回值处理、销毁后置空指针、出栈顺序先取数再自减——这些细节单独看都很简单，组合起来就需要对内存和状态的理解到位。

如果你真的想把这个栈彻底变成自己的东西，我建议你把我上面所有的代码都关掉，自己重新写一遍，再故意写几个有bug的版本去测试。你会发现，亲手踩坑学到的东西，比看十篇文章都牢靠。