手写C语言栈：从结构体定义到动态扩容的完整实现

手写一个栈这件事，看着好像挺简单，但真从头到尾用 C 语言把它写明白，其实一点都不轻松。我从零写栈的时候，踩过的坑包括：结构体字段设计得别扭、扩容时机没想清楚、返回值语义混乱导致调用方根本不知道哪里出错，还有最常见的——内存泄漏。这篇文章我会完整复盘一遍"从零写栈：c语言版本"的全过程，把结构体定义、API 设计、动态扩容、经典应用和排查经验一次讲透。适合刚学完指针和结构体、想用数据结构巩固 C 语言基础的同学，也适合准备面试、需要把栈的实现细节彻底搞明白的开发者。

1. 内容整体设计与思路拆解

1.1 先想清楚：这个栈到底解决什么问题

栈是一种后进先出（LIFO）结构，这个概念好理解，但真实项目中它无处不在。函数调用时的返回地址管理、表达式求值中的运算符优先级处理、编辑器里的撤销操作、浏览器的后退记录，底层都是栈。

很多人第一反应是"直接调现成的库不就行了吗"，标准库确实没有通用的栈容器，得自己写。就算在工作中可以直接用高级语言封装好的栈，理解它内部怎么做、为什么这样做，也会在排查问题时派上大用场。

所以我设计这个项目时，先给自己定了三个目标：

• 用最纯粹的 C 语言，不依赖任何第三方库，只用标准库的 malloc、free、realloc。
• 不追求花哨，但要做到结构清晰、语义明确，每个 API 都能被可靠调用。
• 把栈从"课本概念"变成"真实可用的组件"，顺带把动态数组、内存管理、错误处理这些硬功夫练一遍。

做完之后我最大的感受是：C 语言实现栈，真正的难点不在"压栈""弹栈"这两个动词，而在"栈为空了怎么办""容量不够了怎么办""内存分配失败了怎么办"。这些边界情况才是检验一个开发者是否靠谱的地方。

1.2 数组版还是链表版：选型背后的考量

栈的实现方式有两大阵营：数组版（顺序栈）和链表版（链栈）。我在这个项目里先做了数组版，主要原因有三个。

第一，数组版在缓存局部性上有天然优势。数组里的元素在内存中是连续的，访问栈顶元素时 CPU 缓存命中率明显更高。链表的每个节点都是单独 malloc 出来的，内存地址离散，频繁访问时会有更多缓存缺失。虽然栈的操作量通常不大，但这个差异在大量 push/pop 的场景下还是能感知到的。

第二，数组版的代码逻辑更集中，非常适合用来讲清楚栈的核心机制。创建、扩容、压栈、弹栈，所有关键操作都集中在几个函数里，调试起来非常直观。链表版多了一层"节点指针"的管理，新手容易把注意力分散到链表本身，反而忽略了栈本身的语义。

第三，数组版加上动态扩容之后，几乎就是一个完整的"动态数组"组件，这个技能是可以直接迁移到队列、哈希表底层存储等场景的。学会一次，收益很多。

链表版当然也有自己的价值：没有扩容问题、栈的大小不受连续内存限制、不会因为 realloc 导致大批量元素拷贝。这些我后面会作为扩展方向提一下。

1.3 失败的教训：从"写出一堆代码"到"写出清晰代码"

我最初写这个栈，是直接莽的。在一个文件里堆了一百多行代码，没有头文件，没有错误码设计，push 函数遇到内存不足直接无限循环重试。运行起来大部分时间是正常的，但遇到容量边界的时候，真的会让人心态爆炸。

后来我重新拆了一版，这才发现一个清晰的设计应该包含这三层：

• 数据类型层：用结构体表示栈的"状态"，包括数据区指针、元素个数、容量。
• 操作函数层：所有对栈的读写都通过函数进行，不直接操作结构体内部字段。
• 错误处理层：每个函数有明确的返回值约定，调用方能区分"成功""参数无效""内存不足""栈空"这些不同情况。

这个分层思路适用于很多从零实现的数据结构。别一开始就陷入代码细节，先把结构想清楚，后面写起来会快得多。

2. 核心结构定义与 API 设计

2.1 Stack 结构体：字段怎么定才不别扭

结构体是栈的"地基"，字段设计直接决定后续代码好不好写。我用的是这一版：

c复制typedef struct {
    int *data;      // 指向动态数组的指针
    int top;        // 栈顶索引，也代表当前元素个数
    int capacity;   // 当前容量，最多能容纳的元素数
} Stack;

这里最关键的一个决策是 top 的语义：它表示的是"当前栈顶元素的下标"还是"元素个数"。

我选择了让 top 表示元素个数，也就是说，top 总是等于栈里有多少个元素。压栈时执行 data[top++] = value，弹栈时执行 value = data[--top]。这样设计的好处是：判断栈空只需要检查 top == 0，获取元素个数直接返回 top，语义非常自然。

如果让 top 表示栈顶元素的下标，那空栈时 top 就得是 -1，栈不为空时 top 才指向最后一个元素。这种设计也很常见，C 语言很多教科书都这么写。两者都能用，但一定要在项目里统一约定，不要在某个函数里用一套、另一个函数又用另一套。我在初版代码里就栽过这个跟头，push 用"元素个数"语义，pop 却按"下标"语义写，结果数据错位得一塌糊涂。

2.2 API 清单：哪些函数必须提供

一个好的栈组件，对外暴露的函数应该越少越好、语义越明确越好。我这个版本提供了七个函数：

你可能注意到了，stack_pop 和 stack_peek 都用了一个额外的指针参数 value，而不是直接返回 int。这是因为 C 语言一个函数只能有一个返回值，如果直接返回弹出的元素值，就没法同时返回"操作是否成功"这个信息了。用指针参数把结果"带出来"，返回值专门表达状态，这是 C 语言里非常经典的一种做法。

2.3 错误码设计：不要把所有失败都混为一谈

我见过不少新手写的栈，push 失败就返回 -1，pop 栈空也返回 -1，参数错误还是返回 -1，这样调用方拿到 -1 之后完全不知道发生了什么。

更合理的做法是区分错误类型。C 语言里常见的有几种方案：用不同的负数错误码、用宏定义枚举、或者用全局错误标志。对于这个项目，我用了一个简单但够用的策略：

• 内存分配失败、参数为 NULL、栈空，这三种情况分别返回不同的错误码。
• 用一个小的错误码集合，定义在头文件里：

c复制#define STACK_OK 0
#define STACK_ERR_PARAM -1
#define STACK_ERR_EMPTY -2
#define STACK_ERR_MEMORY -3

这样调用方在排查问题时，看一眼返回值就知道是哪种情况。比如括号匹配算法里，遇到栈空还强行 pop，返回的 STACK_ERR_EMPTY 直接告诉你"右括号没有对应的左括号"，问题定位非常快。

错误码的具体数值没有硬性要求，但是要保证它们不与"有效的元素个数"等正常返回结果混淆。这也是为什么 stack_is_empty 在参数无效时返回了 -1，而不是 0，因为 0 本身是"非空"的合法值，混在一起就没法分辨了。

3. 实操过程与核心环节实现

3.1 头文件先行：stack.h 与调用方约定接口

写任何可复用的 C 组件，头文件都值得先写。头文件的职责很纯粹：声明结构体和所有 API，加上必要的错误码和容错声明。把它先定下来，就好比跟调用方签了一份合同，后面实现哪个函数都不怕跑偏。

c复制#ifndef STACK_H
#define STACK_H

#define STACK_OK 0
#define STACK_ERR_PARAM -1
#define STACK_ERR_EMPTY -2
#define STACK_ERR_MEMORY -3

typedef struct {
    int *data;
    int top;
    int capacity;
} Stack;

Stack *stack_create(void);
void stack_destroy(Stack *s);
int stack_push(Stack *s, int value);
int stack_pop(Stack *s, int *value);
int stack_peek(Stack *s, int *value);
int stack_is_empty(Stack *s);
int stack_size(Stack *s);

#endif

头文件里加了 #ifndef STACK_H / #define STACK_H / #endif 这个宏保护，是为了防止在多个源文件里重复包含导致的重定义错误。虽然是老生常谈，但如果你的工程里有多个 .c 文件都引用了同一个头文件，这个保护缺了就会在链接时报出一堆让人摸不着头脑的错。

3.2 创建与销毁：内存管理的两条铁律

创建和销毁是一对"镜像操作"。创建时分配内存，销毁时释放内存，前后一一对应，这是 C 语言内存管理最核心的一条纪律。

c复制Stack *stack_create(void) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    if (s == NULL) {
        return NULL;
    }
    s->data = NULL;
    s->top = 0;
    s->capacity = 0;
    return s;
}

void stack_destroy(Stack *s) {
    if (s == NULL) {
        return;
    }
    free(s->data);
    free(s);
}

这里有两个容易被忽略的细节。

第一，stack_create 里给 data 初始化为 NULL、容量初始化为 0，是有意的。这意味着我们创建一个空栈时完全不预分配内存。等第一次 push 时再触发扩容，自动申请初始容量。这种"惰性分配"策略让空栈的创建开销极小，也让代码结构更统一——扩容逻辑只需要在一个地方写好就行。

第二，stack_destroy 里为什么可以放心 free(s->data)，即使它可能是 NULL？因为 C 标准明确规定了 free(NULL) 是合法的，什么都不会发生。所以即便一个栈被创建后立即销毁，程序也不会有任何问题。

销毁之后再调用其它 API 属于"使用悬空指针"，属于调用方的责任，设计上我不做额外保护。如果真的需要防止这类误用，可以在销毁时把 Stack 指针本身置为 NULL，但这需要调用方配合。

3.3 压栈与扩容：容量不够时怎么处理

压栈是整个组件的核心。每次压栈之前都要检查容量，容量不足就扩容，扩容成功后再执行写入。

c复制int stack_push(Stack *s, int value) {
    if (s == NULL) {
        return STACK_ERR_PARAM;
    }

    if (s->top >= s->capacity) {
        int new_capacity = s->capacity == 0 ? 4 : s->capacity * 2;
        int *new_data = (int *)realloc(s->data, sizeof(int) * new_capacity);
        if (new_data == NULL) {
            return STACK_ERR_MEMORY;
        }
        s->data = new_data;
        s->capacity = new_capacity;
    }

    s->data[s->top] = value;
    s->top++;
    return STACK_OK;
}

里面的扩容逻辑值得单独拆开讲。

为什么初始容量选 4？这个值不是拍脑袋定的。太小会导致频繁扩容，比如初始为 1，那每压一个元素就 realloc 一次，大量拷贝操作白白消耗性能。太大又会浪费内存，比如初始为 1024，如果一个栈只用来存 10 个数，那 1000 多个 int 的空间就全部浪费了。我在实践里觉得 4 或 8 作为起步容量比较平衡，既保证实际使用中不会频繁扩容，又不会一上来就吃掉太多内存。

为什么扩容倍数选 2 而不是 1.5？这里有一个摊销复杂度的逻辑。按 2 倍扩容时，假设最终容量达到 N，那总拷贝次数大致是 1 + 2 + 4 + 8 + ... + N/2，等比数列求和，约为 N - 1。也就是说，向一个最终容量为 N 的栈里压入 N 个元素，所有扩容过程中的元素拷贝总和大约只是 N 的量级。均摊到每一次 push，时间复杂度是 O(1)，平均下来非常稳定。

之所以不选 1.5 倍，倒不是说不行。1.5 倍扩容有一个独有优势：扩容后旧容量会被新的更小容量较多次"复用"，配合内存分配器的行为，有时能更有效地利用释放出来的内存块。但 2 倍在倍增规律上更简单、在很多嵌入式场景下的内存对齐行为也更可预测。对于教学和通用场景，2 倍足够。

realloc 本身是比较有讲究的。它的行为是：尝试在原内存块上直接扩展，如果当前位置后面有足够的空闲空间，则原地扩容，返回原来的指针；如果不够，它会另外找一块足够大的连续内存，把旧数据复制过去，再释放旧内存块。所以我们不能直接用 s->data = realloc(...) 覆盖原指针，万一 realloc 失败返回 NULL，原来的指针就被覆盖丢了，内存就泄漏了。正确做法是先用一个临时变量 new_data 接收结果，确认不是 NULL 后再赋回 s->data。

3.4 弹栈与查看：空栈保护是必须的

c复制int stack_pop(Stack *s, int *value) {
    if (s == NULL || value == NULL) {
        return STACK_ERR_PARAM;
    }
    if (s->top <= 0) {
        return STACK_ERR_EMPTY;
    }

    *value = s->data[--s->top];
    return STACK_OK;
}

int stack_peek(Stack *s, int *value) {
    if (s == NULL || value == NULL) {
        return STACK_ERR_PARAM;
    }
    if (s->top <= 0) {
        return STACK_ERR_EMPTY;
    }

    *value = s->data[s->top - 1];
    return STACK_OK;
}

这两个函数有一个共同点：都必须防御空栈。从空栈里 pop 或者 peek 是没有意义的，我选择了返回 STACK_ERR_EMPTY，而不是继续执行然后访问一个不确定的内存位置。在 C 语言里，"宁可明确报错，也不产生未定义行为"是保底原则，因为未定义行为往往会在程序里潜伏很久，直到某个数据正好踩到边界时才爆炸。

还有一个细节是：pop 里用 --s->top 既把 top 减了 1，又用减法后的结果作为下标去取元素。这样 top 在逻辑上始终等于"元素个数"，取到的也正是最后一个元素的索引。如果反过来写成 s->data[s->top--]，那取到的是 top 减 1 之前的那个位置，也就是越界了，程序跑起来多半会在某个随机时刻崩掉。

弹出后要不要把 data[top] 位置的值清零？我的习惯是不清零。原因很简单：栈的语义是"该位置以后不会再被读取"，下一次 push 时数据会被直接覆盖，清理这个位置不仅浪费 CPU 周期，还可能让阅读代码的人产生误解，以为这个位置还有什么特殊意义。

3.5 辅助函数：判空、取大小、打印调试

c复制int stack_is_empty(Stack *s) {
    if (s == NULL) {
        return STACK_ERR_PARAM;
    }
    return s->top == 0;
}

int stack_size(Stack *s) {
    if (s == NULL) {
        return STACK_ERR_PARAM;
    }
    return s->top;
}

这两个函数没什么难度，核心就一句话：top 是元素个数，所以判空和取大小都直接基于它，不需要遍历。

我额外建议写一个只用于调试的函数，比如 stack_debug_print，从栈底到栈顶打印所有元素。这个函数在实际排查问题时价值很高——你可以用它观察压栈顺序和弹栈顺序，验证逻辑是否符合预期。这种"仅供调试用"的辅助函数不用写进头文件，放在实现文件里加上 #ifdef 之类的编译条件就行。

4. 经典应用实战：把栈用起来才是真理解

4.1 应用一：括号匹配检测

写数据结构的组件，如果不配一两个真实应用场景，就相当于练了拳法但没上过场。括号匹配是我最喜欢的一个入门案例，因为它逻辑清晰、难度适中，而且能把这个栈组件的 API 全部串起来。

需求很简单：给定一个只包含 ()、[]、{} 的字符串，判断括号是否全部正确配对。比如 "()" 和 "([]){}" 匹配，"(]"、"([)]" 不匹配。

算法思路从零推导其实很自然：遇到左括号就压栈，遇到右括号就弹栈并检查类型是否匹配。如果弹栈时栈已经空了，说明右括号多了；到字符串结尾时栈还没有空，说明左括号多了。

c复制int check_brackets(const char *str) {
    Stack *s = stack_create();
    if (s == NULL) {
        return 0;
    }

    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            if (stack_push(s, ch) != STACK_OK) {
                stack_destroy(s);
                return 0;
            }
        } else if (ch == ')' || ch == ']' || ch == '}') {
            int top_char;
            if (stack_pop(s, &top_char) != STACK_OK) {
                stack_destroy(s);
                return 0;
            }
            if ((ch == ')' && top_char != '(') ||
                (ch == ']' && top_char != '[') ||
                (ch == '}' && top_char != '{')) {
                stack_destroy(s);
                return 0;
            }
        }
    }

    int ok = stack_is_empty(s);
    stack_destroy(s);
    return ok;
}

这段代码里有几个处理细节值得注意。

第一，压栈时遇到内存分配失败，我选择直接销毁栈并返回 0。虽然 0 在这里表示"匹配失败"，但更准确的说法是"无法判断是否匹配"。严格来讲应该区分对待，不过为了代码简单，对这个场景我做了合并。

第二，进行比较时，用的是右括号 ch 和栈顶左括号 top_char 配对，而不是反过来。很多人习惯写成 if (top_char == '(' && ch != ')')，也可以，但直接以 ch 为主体去判断，逻辑上更贴近"我看到了一个右括号，它应该与栈顶匹配"的心智模型。

第三，只要有一次不匹配，我就提前 stack_destroy(s) 并返回，而不是继续扫描。这样做既省掉了无效的遍历，也避免了函数返回时忘记销毁栈导致的内存泄漏。

4.2 应用二：后缀表达式求值

后缀表达式（也叫逆波兰表达式）是栈的另一个经典应用。中缀表达式 3 + 4 * 2 人要用人脑考虑优先级，但转换成后缀 3 4 2 * + 后，计算机就可以用非常简单的方式完成求值。

求值规则只有两条：遇到数字压栈；遇到运算符就弹出两个元素，先弹出的是右操作数，后弹出的是左操作数，计算结果再压回栈。

c复制int evaluate_suffix(const char **tokens, int token_count) {
    Stack *s = stack_create();
    if (s == NULL) {
        return 0;
    }

    for (int i = 0; i < token_count; i++) {
        if (isdigit(tokens[i][0])) {
            int num = atoi(tokens[i]);
            if (stack_push(s, num) != STACK_OK) {
                stack_destroy(s);
                return 0;
            }
        } else {
            int rhs, lhs;
            if (stack_pop(s, &rhs) != STACK_OK || stack_pop(s, &lhs) != STACK_OK) {
                stack_destroy(s);
                return 0;
            }
            int result;
            switch (tokens[i][0]) {
                case '+': result = lhs + rhs; break;
                case '-': result = lhs - rhs; break;
                case '*': result = lhs * rhs; break;
                case '/': result = lhs / rhs; break;
                default:
                    stack_destroy(s);
                    return 0;
            }
            if (stack_push(s, result) != STACK_OK) {
                stack_destroy(s);
                return 0;
            }
        }
    }

    int final_result;
    if (stack_pop(s, &final_result) != STACK_OK || !stack_is_empty(s)) {
        stack_destroy(s);
        return 0;
    }

    stack_destroy(s);
    return final_result;
}

这个例子用到了两个容易被忽略的细节。

一是操作数的顺序。表达式是 3 4 - 时，先弹出的是 4（右操作数），后弹出的是 3（左操作数），计算应该是 3 - 4 而不是 4 - 3。很多人第一次写这里都会搞反，尤其是减号和除号，顺序错了结果就完全不同。

二是求值结束后必须检查栈的状态。正确的结果应该是"栈里恰好剩一个元素"，如果多弹出来一个，说明表达式里数字多了、运算符少了，表达式本身是错的。这个检查看似多余，其实是判断输入是否合法的关键一步。

4.3 应用三：进制转换

十进制转二进制，用栈来做的思路是把每次除以 2 的余数压栈，最后全部弹出拼成结果。这个例子特别适合验证栈的"后进先出"特性——最先压进去的余数是结果的最高位，最后压进去的是最低位，靠栈逆序输出正好符合要求。

c复制void decimal_to_binary(int n) {
    Stack *s = stack_create();
    if (s == NULL) {
        return;
    }

    if (n == 0) {
        stack_push(s, 0);
    }

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

    int bit;
    while (stack_pop(s, &bit) == STACK_OK) {
        printf("%d", bit);
    }
    printf("\n");

    stack_destroy(s);
}

注意我在 stack_pop 的循环条件里先调用了函数再检查返回值，这样当栈弹空时循环自然结束，不需要额外判断。这种写法在 C 语言里非常常见，代码看起来紧凑，逻辑也清晰。

这个应用本身很简单，但它很好地证明了栈的一个关键特性：逆序输出。以后遇到"正序生成但需要反着展示"的场景，比如链表反转、递归展开，都可以自然想到用栈。

5. 常见问题与排查技巧实录

5.1 高频报错速查表

这段时间反复折腾下来，我把踩过的坑总结成了一张表。遇到问题可以先对照一下。

这张表不是标准的官方错误列表，而是从实操里攒出来的真实经验。排错顺序一般是：先看崩溃还是逻辑错误，再看指针是否越界，然后看内存是否泄漏，最后再怀疑算法本身的边界条件。

5.2 内存泄漏排查：valgrind 的正确用法

C 语言开发，valgrind 几乎是必装工具。它的原理是拦截 malloc、free 等内存相关调用，在程序退出时报告所有"分配了但没释放"的内存块。

典型用法：

bash复制gcc -g -o stack_demo stack.c main.c
valgrind --leak-check=full ./stack_demo

如果输出里有类似 definitely lost: 16 bytes 这样的行，就说明有内存泄漏。16 字节很可能就是那个 Stack 结构体本身——比如你调用 stack_create() 之后在某个分支里直接 return 了，没有走到 stack_destroy。

内存泄漏的可怕之处在于它不会立刻让程序崩溃，而是慢慢消耗内存，直到系统资源耗尽。对于长期运行的服务、嵌入式设备上的守护进程，哪怕每次泄漏几个字节，累积起来也能把设备拖垮。所以养成"每次函数出口都检查销毁"的习惯特别重要。

5.3 空栈保护与未定义行为

很多 C 语言初学者会觉得"空栈保护是多余的"，因为自己写测试时总是先 push 再 pop，不会在空栈上操作。但真实项目里的调用顺序往往由外部事件决定，根本不可控。

比如括号匹配里，如果输入是 ")("，那么扫描到第一个字符 ) 时就要 pop，而栈是空的。没有空栈保护的话，s->data[--s->top] 就会在 top 已经是 0 的情况下把它减到 -1，然后读取 data[-1] 这个越界地址。C 语言里这是未定义行为，轻则读到随机值导致程序行为诡异，重则直接段错误。

我的设计里，stack_pop 和 stack_peek 都在访问数组之前先检查 s->top <= 0，发现空栈直接返回 STACK_ERR_EMPTY。这样，应用层的代码就可以依赖这个返回值来做判断，而不是赌它不会出事。

5.4 调试经验：善用打印与断言

调试栈相关的问题，我个人的习惯是三步走。

第一步，写一个 stack_debug_print 函数，每次可疑操作后打印整个栈的内容。这个方法治好了我很多次"怎么想都想不明白的逻辑错误"——看一眼栈内状态，问题往往一目了然。

第二步，在关键位置加断言。比如在 stack_pop 开头加一个条件编译的断言：

c复制#ifdef STACK_DEBUG
assert(s->top > 0);
#endif

这样只在调试版本生效，发布版本完全不增加开销。

第三步，用极小的测试用例手动模拟执行。比如创建空栈、依次 push 1、2、3、再 pop 一次，在纸上把 top 和 capacity 的变化写下来，再对比代码实际执行结果。这个方法虽然笨，但对数据结构这类逻辑严密的任务非常管用。

5.5 我踩过的一个特别坑：扩容时没保存旧容量

有一次我在重构扩容逻辑时，脑子一热写了下面这段代码：

c复制if (s->top >= s->capacity) {
    s->capacity *= 2;
    s->data = (int *)realloc(s->data, sizeof(int) * s->capacity);
}

表面上没问题：容量翻倍，然后用新容量申请内存。实际上问题很大。

如果 realloc 失败，s->data 会被赋成 NULL，而 s->capacity 已经翻倍了。这时候再调用 stack_push，就会继续执行"检查容量"的逻辑——因为 top 小于已经翻倍的 capacity，所以不会触发扩容，直接尝试写入 s->data[s->top]，而对一个 NULL 指针执行写入，是必然崩溃。

这个问题的根源在于：我违反了"先用临时变量接收 realloc 结果"的原则，并且把 capacity 的更新放在了内存申请之前。正确的做法就像 3.3 节展示的那样，先计算 new_capacity，用临时变量接收 realloc 的结果，确认成功后再一起更新 data 和 capacity。这里我吃了一次亏，写了这么多代码之后才真正理解教科书里"临时变量不能省"这句话的分量。

6. 这个项目还能怎么延伸

栈的这个版本做完，后面还有很多变体值得尝试。我列几个我自己想做的方向。

最小栈：除了普通栈的 push/pop/peek，额外提供一个 O(1) 的 get_min 方法返回当前栈内最小值。做法是维护两个栈，一个存数据，另一个同步存"当前最小值"。每次 push 时比较新值和当前最小值，把较小值压入最小值栈。这样弹出时两个栈同步弹出一个，栈顶永远是最小值。

链表版栈：没有扩容问题，也不用搬移数据。但每个元素多一个 next 指针，空间开销变大。适合元素大小差异较大、总数量无法预估的场景。实现时不需要 capacity 字段，top 变成一个节点指针，栈空就是 top == NULL。

线程安全版：如果栈要被多个线程并发访问，就需要加锁。最粗犷的做法是让 push 和 pop 都加上互斥锁，好处是安全，坏处是并发性能受影响。更精细的算法比如无锁栈，是基于 CAS 原子操作实现的，复杂度高很多，但也是真正工业级组件里会用到的技术。

从零写栈最大的价值不是"栈"本身，而是把它当作一次小型的工程实践：定义接口、处理边界、管理内存、调试排查、迭代优化，这一整套流程在以后写任何代码时都能用上。我个人的体会是，数据结构不能只看不写，看十遍不如自己从空文件开始写一遍。写不通的时候，再去翻书、去看别人的代码，那种"原来这里还有个坑"的感觉，比死记硬背教科书深刻得多。