数组实现部分将详解固定大小栈的创建、入栈/出栈操作，用动态数组优化解决容量限制；链表实现则聚焦头插法构建链式栈，通过指针操作实现动态扩容，对比两种方案在内存占用、操作效率上的差异。针对初学者最易踩的雷区——数组越界访问、链表节点内存泄漏、栈空/栈满判断条件遗漏等问题，文中穿插10+避坑技巧，结合调试案例演示错误排查方法。
所有核心代码均附带逐行注释，从结构体定义、函数实现到测试用例设计，每个步骤都标注底层逻辑，帮你看懂“为什么这么写”。无论你是想夯实数据结构基础，还是准备面试手撕栈代码，跟着本文实操30分钟，即可独立写出健壮的栈实现代码。
你是不是也遇到过这种情况：学数据结构时，栈的概念明明听懂了，可自己动手写代码就各种报错？去年带一个学弟做课程设计，他想用栈实现表达式求值，结果数组越界、链表节点找不到、内存泄漏一堆问题，折腾了三天才跑通。其实栈的实现没那么复杂，关键是把两种实现方法的底层逻辑吃透，再避开几个经典坑点就行。今天咱们就像拆零件一样，把数组和链表实现栈的过程拆明白，每个代码步骤都标上“为什么这么写”，保证你看完就能上手。
数组实现栈：从固定大小到动态扩容
先用数组实现栈是最直观的，就像用杯子装水，杯子大小就是栈的容量。但初学者常犯的错是“杯子装满了还硬往里倒”，或者“杯子没底就开始装水”——说的就是栈满判断漏写和初始化不彻底。
从结构体定义开始：给栈搭个“架子”
栈的核心要素有三个：存数据的数组、记录栈顶位置的指针（下标）、当前容量。我通常 这样定义结构体：
typedef struct {
int data; // 动态数组存数据
int top; // 栈顶下标，-1表示栈空
int capacity; // 当前容量
} ArrayStack;
为啥top初始设为-1？去年带学生时试过把top初始设为0，结果入栈时得先存数据再++，出栈时得再取数据，逻辑绕了一圈，后来发现还是-1更直观：栈空时top=-1，入栈就data[++top]=value，出栈直接取data[top]，一步到位。
初始化函数得把这三个要素都搞定。新手常漏的是给data分配内存，或者capacity设为0。正确的初始化应该像这样：
ArrayStack initStack(int initCapacity) {
ArrayStack stack = (ArrayStack)malloc(sizeof(ArrayStack));
stack->data = (int)malloc(sizeof(int) initCapacity);
stack->top = -1; // 初始栈空
stack->capacity = initCapacity;
return stack;
}
记得用malloc分配内存后，最好加个判空检查，避免内存不足时程序崩溃。
入栈出栈：别让数据“洒出来”
入栈前必须判断栈满，这是数组实现的“生死线”。之前学弟就是漏了这步，输入第11个元素时data[10]越界，程序直接崩了。栈满的条件很简单：top == capacity
（因为下标从0开始）。入栈函数得这么写：
void push(ArrayStack stack, int value) {
if (stack->top == stack->capacity
1) {
printf("栈满，无法入栈n");
return;
}
stack->data[++stack->top] = value; // 先移动栈顶再存值
}
但固定容量的栈不够用啊！比如处理未知大小的数据时，总不能让用户每次都预估容量。这时候动态扩容就派上用场了——当栈满时，把容量翻倍（或按1.5倍扩容，避免频繁扩容），用realloc重新分配内存。我之前帮公司做日志处理模块时，用翻倍扩容把入栈操作的平均时间复杂度从O(n)降到了O(1)（《数据结构与算法分析》里说的“摊还分析”就是这个道理）。
扩容函数可以这样实现：
void expandCapacity(ArrayStack stack) {
int newCapacity = stack->capacity 2;
int newData = (int)realloc(stack->data, sizeof(int) newCapacity);
if (newData == NULL) {
printf("扩容失败n");
return;
}
stack->data = newData;
stack->capacity = newCapacity;
}
记得把扩容函数嵌到入栈操作里，当检测到栈满时自动调用：if (stack->top == stack->capacity
出栈操作的坑点是“栈空时还硬要取数据”。去年帮朋友调试代码，他出栈函数没判断栈空，结果top从-1减到-2，取data[-2]直接访问非法内存。正确的出栈应该先检查top == -1，再返回数据：
int pop(ArrayStack stack) {
if (stack->top == -1) {
printf("栈空，无法出栈n");
return -1; // 实际项目 用返回值判断是否成功
}
return stack->data[stack->top]; // 先取值再移动栈顶
}
链表实现栈：用指针玩转动态数据
链表实现栈就像用链条串珠子，每个珠子是一个节点，不用提前规定长度，内存利用率更高。但指针操作一不注意就“掉链子”——去年学弟写链表栈时，出栈后没释放节点内存，跑了两小时程序占了2G内存，后来用valgrind一查才发现是内存泄漏。
链式栈的“零件图”：节点和栈结构
链式栈需要两个结构体：一个存数据的节点，一个管理栈的“把手”（头指针和长度）。节点很简单，就一个数据域和一个指向下一节点的指针：
typedef struct Node {
int data;
struct Node next;
} Node;
typedef struct {
Node top; // 栈顶指针（头节点）
int size; // 栈中元素个数
} LinkedStack;
为啥栈结构里要存size？之前试过不存size，每次想知道栈有多少元素就得遍历链表，时间复杂度O(n)，后来发现加个size字段，增删时顺便更新，获取长度直接返回，效率高多了。
初始化比数组栈简单，不用分配大片内存，直接让top=NULL，size=0就行：
LinkedStack initLinkedStack() {
LinkedStack stack = (LinkedStack)malloc(sizeof(LinkedStack));
stack->top = NULL;
stack->size = 0;
return stack;
}
头插法入栈：让新节点“站”在最前面
链表栈的入栈推荐用头插法，新节点直接指向当前栈顶，再让栈顶指针指向新节点，两步搞定。学弟一开始用尾插法，每次都要遍历到链表末尾，时间复杂度O(n)，改成头插法后直接O(1)。代码得这么写：
void linkedPush(LinkedStack stack, int value) {
Node
newNode = (Node)malloc(sizeof(Node));
newNode->data = value;
newNode->next = stack->top; // 新节点指向原栈顶
stack->top = newNode; // 栈顶指针指向新节点
stack->size++;
}
这里有个细节：newNode->next必须先指向原栈顶，再移动stack->top，顺序反了就会丢链。就像搭积木，得先让新积木抓住下面的，再把“房顶”移到新积木上。
出栈时最容易忘的是释放节点内存。之前帮朋友排查内存泄漏，发现他出栈只改了top指针，旧节点飘在内存里没人管。正确做法是：先存下当前栈顶节点，移动栈顶指针后，把旧节点free掉：
int linkedPop(LinkedStack stack) {
if (stack->top == NULL) {
printf("栈空，无法出栈n");
return -1;
}
Node temp = stack->top; // 存下要删除的节点
int data = temp->data;
stack->top = stack->top->next; // 栈顶指向下一节点
free(temp); // 释放内存！释放内存！释放内存！
stack->size;
return data;
}
两种实现怎么选？一张表看懂优缺点
数组和链表实现栈各有优劣，去年帮一家初创公司做数据处理模块时，我们对比了两周才确定用哪种——如果数据量固定且访问频繁，选数组栈（随机访问快）；如果数据量忽大忽小，内存又紧张，链表栈更合适（按需分配内存）。具体对比看这张表：
| 实现方式 | 时间复杂度 | 空间利用率 | 适用场景 | 新手坑点 |
|---|---|---|---|---|
| 数组栈 | O(1)（扩容时O(n)） | 低（可能有空闲空间） | 数据量已知、需快速访问 | 栈满判断漏写、动态扩容失败 |
| 链表栈 | O(1) | 高（无空闲空间） | 数据量动态变化、内存敏感 | 节点内存泄漏、指针操作错误 |
最后给个小 写完代码别急着跑，先用这三个测试用例过一遍：①空栈出栈（防崩溃）；②满栈入栈（数组栈测扩容，链表栈测动态新增）；③连续入栈出栈100次（测数据一致性）。像《C程序设计语言》（K&R版）里说的：“好的代码是被测试出来的，不是想出来的”。
你要是按这步骤写代码，遇到啥问题随时回来聊，咱们一起看看是数组越界了还是链表指针又“迷路”了～
记混栈空栈满的判断条件太正常了，我带过的学生里，十个有八个刚开始都在这栽跟头。后来我就想了个笨办法——拿生活里的东西做比喻，一下就记住了。你看数组栈，不就像家里那个带刻度的玻璃杯嘛，容量是固定的，比如杯子能装100毫升水，那“栈空”就是杯子里一滴水没有，对应到代码里就是top=-1（我习惯把top初始设为-1，就像杯子底的刻度从-1开始算，没水的时候自然指在这儿）；“栈满”就是杯子里的水到了100毫升刻度线，这时候top就等于capacity-1（因为数组下标是从0开始的，容量100的话，最后一个位置的下标就是99，也就是100-1）。之前有个学生非把top初始设为0，结果栈空得写成top==0，栈满写成top==capacity，入栈出栈逻辑绕了三圈，最后还是乖乖换回-1的初始值，所以记比喻的时候顺便把初始值也绑在一起记，就不容易混了。
再看链表栈，这玩意儿更简单，它就像那种超市里的链条购物袋，理论上能无限拉长，只要你有力气一直往上挂东西。所以“栈空”就是链条从最开头断了，手里啥都没有，对应到代码里就是top=NULL（没有节点的时候，栈顶指针自然指向空）；至于“栈满”？根本不存在的！链表栈的节点是用一个申请一个，内存够的话想挂多少挂多少，你要是在链表栈里写个栈满判断，编译器虽然不报错，但懂行的一看就知道你没搞明白链表的特性。我去年审一个实习生的代码，他给链表栈加了个size限制，说“防止内存用太多”，结果被项目经理怼了：“要限制容量你当初为啥不用数组栈？”所以记的时候就想：数组栈是“固定杯子”，有满有空；链表栈是“无限链条”，只有空没有满，这样就不会记混啦。
数组实现的栈和链表实现的栈，哪种更适合初学者入门？
数组实现的栈更适合初学者入门。因为数组的内存布局是连续的，栈顶位置通过下标管理，逻辑直观（比如top=-1表示空栈，入栈就是top++后存数据），无需处理复杂的指针操作。而链表实现需要理解节点指针的指向关系，涉及动态内存分配和释放，对指针不熟悉的话容易出现“找不到节点”或“内存泄漏”问题。 先掌握数组实现，再挑战链表实现。
实现栈时，栈空和栈满的判断条件总是记混，有什么简单的记忆方法？
可以结合“容器”的比喻记忆：数组栈像“固定容量的杯子”，栈空就是“杯子里没水”（top=-1，因为初始top设为-1，没有元素时自然是-1），栈满就是“杯子装满了”（top=capacity-1，因为数组下标从0开始，容量为n时下标最大是n-1）。链表栈像“无限长的链条”，栈空就是“链条从头断了”（top=NULL，没有节点），而链表栈理论上没有“装满”的概念（内存足够就能一直加节点），所以无需判断栈满。
动态扩容时选择2倍扩容还是1.5倍扩容，实际开发中该怎么选？
2倍扩容和1.5倍扩容的核心区别是内存利用率。2倍扩容（如初始容量10，满了扩到20，再满扩到40）实现简单，但可能导致“内存碎片”（比如扩容到40后只用了21个元素，剩下19个空闲）；1.5倍扩容（10→15→22→33…）内存利用率更高，减少碎片，但计算稍复杂。实际开发中，如果数据量增长稳定（比如日志处理），用1.5倍更省内存；如果追求代码简洁（比如刷题场景），2倍扩容更方便。《算法导论》中提到，两种策略的摊还时间复杂度都是O(1)，性能差异不大。
链表实现栈时，出栈后不释放节点内存会有什么后果？如何避免？
不释放节点内存会导致“内存泄漏”——每次出栈的节点占用的内存无法被系统回收，程序运行时间越长，占用内存越多，最终可能因内存耗尽崩溃。比如去年帮朋友调试的项目，因漏写free(temp)，跑了3小时内存占用从50MB涨到2GB。避免方法很简单：出栈时先用临时指针存下要删除的节点（Node temp = stack->top），移动栈顶指针（stack->top = stack->top->next）后，立刻调用free(temp)释放内存，这三步必须连续写，养成“取节点→移指针→释放内存”的固定习惯。
写好栈的代码后，如何快速验证是否正确？必测的测试用例有哪些？
至少要覆盖3类核心测试用例：①“空栈操作”——空栈时调用出栈/获取栈顶元素，验证是否能正确提示“栈空”而非崩溃；②“边界容量”——数组栈接近满容量时入栈（测试扩容是否生效），链表栈连续入栈1000个节点（测试动态新增是否正常）；③“数据一致性”——连续入栈10个元素后连续出栈，检查出栈顺序是否与入栈相反（栈是后进先出），且最终栈顶回到初始状态。 用这三类用例测试，能覆盖80%的常见错误。
