作为一名常年和数据结构和算法打交道的开发者我深知“栈”这个东西在面试和实际工程里的分量。但很多初学者在刚接触时总容易把它和“堆”搞混或者背熟了“后进先出”的定义一写代码就卡壳。所以今天这篇内容我不打算绕弯子直接把栈的底层逻辑、两种主流实现方式数组和链表、以及基于栈的经典应用场景全部拆开揉碎配上可以直接拿去用的代码希望能帮你把这块硬骨头啃下来。这篇文章适合正在上数据结构课程的同学、准备算法面试的求职者以及想补一补基础的程序员。我会从最核心的物理结构讲起再逐步过渡到抽象的逻辑行为最后落到实际的代码和避坑经验上。如果你能耐心看完并亲手把代码敲一遍我敢说栈这个知识点就算真正过关了。1. 栈的核心逻辑为什么说它像一叠盘子在动手写代码之前我们必须把栈的本质聊透。数据结构的核心无非就两件事数据的物理存储结构和数据的逻辑访问规则。物理存储结构决定了数据怎么在内存里放着而逻辑访问规则决定了外部代码该怎么去操作这些数据。栈的逻辑规则可以用一句话概括后进先出。这个概念在生活里最贴切的类比就是餐厅里那种弹簧托架上的一叠盘子。服务员收盘子或者取盘子永远只能接触到最顶上的那一个。如果你想要最底下的那个盘子就得把上面所有盘子一个个先拿走。这个操作顺序在计算机里有一个比较正式的名字叫LIFO也就是Last In First Out。这种限制恰恰是栈的价值所在。它把自由度降低换来的是极低的时间复杂度和极高的操作确定性。所有的插入入栈和删除出栈操作都只发生在栈顶这一个位置。这意味着我们不需要像数组那样为了找到一个元素而在内存里来回扫描也不需要像链表那样为了删除一个节点而小心翼翼地维护前后指针的指向。栈的一切操作时间复杂度都是O(1)。很多人会有个疑问既然它功能这么简单为什么在算法和系统底层里无处不在答案就在于栈天然适合处理“需要暂时保存状态然后在未来某个时刻以相反顺序恢复状态”的场景。函数调用过程中的参数和返回地址需要保存浏览器看你访问过的页面记录需要回退编译器要检查你写的括号是否匹配……这些场景的共同点都是存在一种“嵌套”和“回溯”的性质而栈的逻辑规则正好与这种性质严丝合缝。再往深了说栈有两种物理实现路线。一种是基于数组我们称之为顺序栈一种是基于链表我们称之为链式栈。这两种路线各有优劣没有绝对的好坏只有“合不合适”的问题。接下来我会分别拆解这两条路线的实现细节和选择标准这也是面试里极其高频的考察点。2. 实现方案的前期铺垫数组与链表带给你的不同底气在写栈的代码之前先花点时间把“底子”想清楚。所谓底子就是底层用数组还是链表。这两个选择会直接影响你的栈在扩容、内存碎片、访问效率三个维度上的表现。如果选择数组你面对的是一个连续的内存空间。数组最大的优点是CPU缓存友好。因为数据在物理地址上是挨在一起的CPU在读取数据时会把相邻的数据一并加载到缓存行里这意味着入栈和出栈操作往往命中缓存速度极快。数组的缺点是当栈容量不够需要扩容时你得重新开辟一块更大的内存然后把旧数据一个个拷贝过去。这个扩容过程的时间复杂度虽然是O(n)但好在它发生的频率并不高均摊下来性能依然可以接受。如果选择链表你面对的是一个个孤立的节点节点之间通过指针连接。链表的好处是不需要考虑扩容问题。因为它是动态的来一个数据就分配一个节点内存利用率理论上更高。但缺点也很明显链表节点的内存地址是散落的无法利用CPU缓存的预取机制同时每创建一个节点都要额外分配内存多了指针的读写开销。在大规模、高频的栈操作场景下链式栈往往不如顺序栈来得利索。所以我的个人经验是如果没有特殊的内存碎片考量默认优先选择数组实现栈。不仅因为性能更好、代码更短更重要的是顺序栈在算法题中几乎可以覆盖90%以上的应用场景。链式栈更多出现在项目设计需要灵活内存管理的场景比如一些无锁并发结构的设计证明中。但这里要特别提一个细节如果你选择链式栈一定要小心“头插法”和“尾插法”的区别。栈的入栈和出栈都发生在栈顶所以我们应该用头插法来构造链表栈。也就是说每次新入栈的节点都插到链表头部这样栈顶就是链表的头节点出栈时只需要把头节点摘下来返回即可。如果误用了尾插法那么出栈操作就需要遍历到链表尾部复杂度直接从O(1)退化到O(n)这样就完全丧失了栈的高效性。3. 手写代码基于动态数组的顺序栈从零实现接下来进入正题。我会先用C语言实现一个基于动态数组的顺序栈。选择C语言的原因是因为它足够底层没有像STL或者Java集合框架那样帮你封装好一切你能够清晰看到每一步的内存操作。理解了C语言版本后面再看其他语言的实现会轻松很多。3.1 结构体定义与容量管理机制首先我们定义一个栈的结构体里面需要包含三个核心成员数据指针、栈顶索引、容量。栈顶索引在数组实现中本质上就是“当前栈内元素的数量”也可以理解为“下一个入栈元素应该放的位置”。typedef struct { int *data; // 动态数组指针指向堆上分配的内存 int top; // 栈顶索引-1表示栈空 int capacity; // 当前分配的容量 } SeqStack;这里的初始容量我一般习惯设置为1024。如果你确定了数据的规模范围也可以直接初始化成你需要的大小。初始化容量太小会导致频繁扩容太大则会浪费内存。所以一个合理的初始容量是顺序栈性能的一项隐形指标。接下来是扩容机制。顺序栈的扩容逻辑和动态数组完全一样当top等于capacity减1时即栈满就把容量扩大到原来的两倍。两倍是一个工程上公认比较合理的增长倍数它保证了扩容操作的均摊时间复杂度是O(1)。如果每次只增加一个单位那么频繁的扩容会导致极低的效率如果增长倍数太大比如10倍虽然扩容次数少了但内存浪费会很严重。void expand(SeqStack *stack) { if (stack-top 1 stack-capacity) { return; // 空间足够无需扩容 } int new_capacity stack-capacity * 2; int *new_data (int *)malloc(sizeof(int) * new_capacity); if (new_data NULL) { printf(内存分配失败\n); exit(1); } // 拷贝旧数据到新区域 for (int i 0; i stack-top; i) { new_data[i] stack-data[i]; } free(stack-data); // 释放旧内存 stack-data new_data; stack-capacity new_capacity; }3.2 关键操作的边界条件与返回值约定栈的五大核心操作是初始化、判空、入栈、出栈、取栈顶元素。每个操作都有它自己的边界条件你必须要在编码时敏锐地处理它们。初始化很简单就是分配内存并设置初始值。这里有个小坑很多人会忘记初始化top为-1导致后续判断出错。void init(SeqStack *stack, int capacity) { stack-data (int *)malloc(sizeof(int) * capacity); stack-top -1; stack-capacity capacity; } int isEmpty(SeqStack *stack) { return stack-top -1; }入栈操作push需要先判断是否扩容然后先移动top索引再写入数据。这里要注意顺序也可以先写入再移动索引但为了避免逻辑混乱建议统一为先移动、再赋值。void push(SeqStack *stack, int value) { expand(stack); stack-top; stack-data[stack-top] value; }出栈操作pop是一个容易出错的地方因为它涉及两个动作取出栈顶值然后top索引下移。如果你先下移索引就取不到栈顶元素了如果你先取元素随后的索引下移要确保安全。更关键的是出栈时我们需要处理“空栈”的情况。如果栈是空的你还想弹出元素那这就属于一个越界操作。对于这种异常场景业界有两种常见做法一种是返回一个约定好的错误值比如-1另一种是通过输出参数返回结果同时用函数返回值指示操作是否成功。我强烈推荐第二种做法因为用错误值来兼作数据和状态在很多真实场景下是不可靠的。比如如果这个栈存的就是整数而你恰好要入栈一个-1那这个-1到底是正常数据还是空栈标记无法区分。int pop(SeqStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空无法出栈\n); return 0; // 0表示失败 } *value stack-data[stack-top]; stack-top--; return 1; // 1表示成功 }取栈顶元素peek和pop的区别在于peek只读取栈顶元素栈的状态不发生任何变化。这个操作常用于查看当前状态而无需立即移除它。在括号匹配场景中我们就经常用peek来检查当前栈顶的括号是否和当前遇到的右括号成对。int peek(SeqStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空无法读取栈顶元素\n); return 0; } *value stack-data[stack-top]; return 1; }等所有操作完成后别忘了释放堆内存。这也是一个常被忽略的坑单纯用完之后不调用free在长期运行的程序中会造成内存泄漏导致程序占用内存越来越大。正确的释放逻辑是先释放data指针指向的堆内存再重置各字段。void destroy(SeqStack *stack) { if (stack-data ! NULL) { free(stack-data); stack-data NULL; } stack-top -1; stack-capacity 0; }可以看到基于数组的顺序栈整体代码量不大逻辑也非常直观但它考察的是你对数组索引边界的敏感度、动态内存管理的熟练度还有异常处理的严谨度。这三个点都是在面试中会被细致追问的细节。4. 链式栈的清爽实现头插法带来的灵动体验说完了数组实现我们再看看链表实现。如果说数组栈的精髓在于“索引计算”那么链式栈的精髓就在于“指针翻转”。4.1 节点的初始化与栈的构造链表的基本单元是节点。每个节点包含数据域和指针域。链式栈的栈顶就是链表的头节点因此我们需要维护一个指向头节点的指针。栈为空时这个指针为NULL。typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *top; // 栈顶指针指向链表头节点 } LinkedStack;初始化时只需要将top置为NULL即可。这里不需要像顺序栈那样提前分配内存链表的内存是按需分配因此初始化动作非常简单。void init(LinkedStack *stack) { stack-top NULL; } int isEmpty(LinkedStack *stack) { return stack-top NULL; }4.2 入栈出栈的指针变换逻辑链式栈的入栈操作本质上就是一次“头插法”的链表插入。先创建一个新节点如果内存分配失败则返回错误然后将新节点的next指针指向当前栈顶最后更新栈顶指针让它指向新节点。int push(LinkedStack *stack, int value) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) { printf(内存分配失败\n); return 0; } node-data value; node-next stack-top; // 新节点的后继指向旧栈顶 stack-top node; // 栈顶更新为新节点 return 1; }这个过程中指针的赋值顺序非常重要。很多人第一次写链表插入时会把node-next stack-top和stack-top node这两行写反导致新节点自己指向自己形成一种“幽灵环”整个链表就断线了。这里面一个相对稳妥的思考方式先处理新节点的指针指向再更新栈顶指针。因为如果你先更新了stack-top你就丢失了旧栈顶的地址新节点的next就无法正确连上旧节点了。出栈操作则是对应头节点的删除操作。我们需要临时保存旧栈顶节点读取它的数据然后将栈顶指针下移指向下一个节点最后释放旧节点的内存。int pop(LinkedStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空无法出栈\n); return 0; } Node *tmp stack-top; *value tmp-data; stack-top tmp-next; // 栈顶移动到下一个节点 free(tmp); // 释放旧栈顶 return 1; }这里有一个隐性的内存管理知识如果你在出栈时忘记free这一句那么被弹出的节点就成了“孤儿节点”它占用的内存没有被回收引用它的指针又不存在了系统无法自动回收它这就发生了内存泄漏。在非垃圾回收语言里这是一个必须高度警惕的问题。取栈顶元素则更简单只需要判断非空然后返回top-data即可不需要移动指针也不需要释放任何内存。int peek(LinkedStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空\n); return 0; } *value stack-top-data; return 1; }链式栈的销毁逻辑需要循环释放所有节点。这里要注意你不能在free一个节点的同时去访问它的next因为free之后这个节点的内存就已经被回收了里面的指针数据不可信。正确的做法是用一个临时指针先保存next再free当前节点。void destroy(LinkedStack *stack) { Node *current stack-top; while (current ! NULL) { Node *next current-next; free(current); current next; } stack-top NULL; }链式栈的代码在逻辑上和顺序栈略有不同但本质上都是O(1)的入栈和出栈。它的优势是完全不需要考虑扩容问题入栈时只受系统可用内存限制因此在数据量不确定或内存碎片不是主要矛盾的情况下链式栈更灵活。5. 两种实现的硬核对比从性能到代码可读性的取舍当你掌握了两种实现之后很自然会遇到一个问题到底该用哪种我这边的建议是看场景选方案。为了更直观点我把两种实现的关键差异整理成下面的表格方便对照。数组栈的优势主要体现在速度与缓存友好性上而链式栈的优势主要体现在灵活的内存管理上。如果你的程序频繁创建和销毁栈并且不知道峰值数据量那么链式栈能够省下大量扩容和心跳检测的逻辑。如果你的程序追求极致性能并且数据量在可预见的范围内是可控的那么数组栈肯定是更合适的。这里提醒一下数组栈的扩容操作本身是一次性开销虽然均摊后很低但在对时间极其敏感、不允许任何毛刺的嵌入式环境里这个偶发的扩容拷贝也可能成为你不愿意看到的延迟点。对比维度顺序栈数组实现链式栈链表实现入栈/出栈时间复杂度O(1)O(1)需考虑扩容需要动态2倍扩容不需要天然动态内存空间占用紧凑只有数据额外存储指针缓存友好性优秀物理连续较差地址分散异常处理复杂度需处理栈满扩容失败需处理节点分配失败典型应用场景表达式求值、括号匹配、函数调用栈深度优先遍历、内存分配器、动态任务栈除了性能代码的可读性也是一个值得权衡的因素。数组栈的实现虽然短但是它的“扩容”核心逻辑容易让初学者混淆链式栈的代码结构清晰指针操作更能帮助理解链表结构本身。我自己在教学过程中观察到部分同学在教材上能看懂代码但一到自己动手写链式栈就卡壳。如果你也是这种情况建议多写几遍或者把链表本身的操作头插法和头删法练习熟再来看栈就会觉得薄薄一层窗户纸。6. 栈的经典应用实践从括号匹配到表达式求值栈的代码写完了如果不应用到实际问题里难免会觉得它只是个“数据结构练习”。下面我挑两个比较经典的应用场景分别是括号匹配和表达式求值用它们来检验上面写的栈是否够格进入实战环节。6.1 括号匹配状态保存与回退的绝佳示例括号匹配也叫括号配对检测。你在代码里写了这么一行表达式{[()]}。编译器如何知道这串括号是合法的关键在于计算机扫描时遇到左括号就入栈遇到右括号时就要从栈顶取一个左括号来匹配。如果栈顶的左括号和当前右括号不配对或者当栈已经是空的却还遇到右括号就说明这个字符串是不合法的。我们写个函数实现这个逻辑。这里用到的就是上面实现的链式栈。如果栈里存放的是字符类型别忘了把之前代码里的int换成char。int isMatching(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } int isValid(char *s) { SeqStack stack; init(stack, 128); for (int i 0; s[i] ! \0; i) { char c s[i]; if (c ( || c [ || c {) { push(stack, c); } else if (c ) || c ] || c }) { char top; if (!pop(stack, top)) { return 0; // 栈空却遇到右括号不匹配 } if (!isMatching(top, c)) { return 0; // 左右括号类型不一致 } } } int empty isEmpty(stack); destroy(stack); return empty; }整个过程是一个状态机式的推进左括号压入时等于把当前状态存档右括号弹出时等于验证并回溯。这种“存档—回溯”的逻辑正是栈最核心的魅力所在。很多更复杂的算法比如深度优先搜索DFS、回溯法求解八皇后、走迷宫等核心思想都源于这个简单的机制。6.2 表达式求值中缀转后缀与后缀计算表达式求值是一个非常经典的算法场景。常见的表达式叫中缀表达式比如3 5 * 2。人脑一看就知道乘法的优先级高于加法但计算机不这么理解。它要把中缀表达式转换成后缀表达式也叫逆波兰表达式转换完的结果是3 5 2 * 。后缀表达式的特点是操作数在前运算符在后并且完全没有括号。计算机在计算后缀表达式时需要一个栈遇到数字就入栈遇到运算符就弹出两个数字然后做运算把结果重新压入栈。中缀转后缀的算法也叫调度场算法它的核心就是一个运算符栈。规则如下遇到操作数直接输出。遇到左括号入栈。遇到右括号弹出栈顶运算符直到遇到左括号。遇到运算符与栈顶运算符比较优先级如果栈顶优先级不低于当前运算符则弹出栈顶直到栈空或栈顶优先级低于当前运算符并将当前运算符入栈。我这里不展开完整的代码因为篇幅太长但你可以对照这个规则自己写一遍。这个过程非常锻炼你对栈的运用能力和对算法分支条件的细心程度。我之前在实现时就被“运算符优先级比较”这个环节坑过规则里有一句“同优先级左结合”这意味着当栈顶运算符和当前运算符优先级相等时你也需要弹出栈顶而不是直接把当前运算符压栈。如果写反了最终的计算结果就会错误且很难在少量测试用例中暴露出来。表达式求值的完整实现涉及多个函数包括运算顺序处理、栈的应用等。但只要你把栈的入库出库逻辑理解透这个算法写下来并不会特别复杂反而会觉得很顺滑。7. 实操中的典型踩坑与排查技巧速查代码写得多了遇到坑是不可避免的。我在早期学习和写项目的过程中在栈这块就踩过不少雷。这里我把几个高频、常见的坑集中整理成表格你在自己动手时可以重点对照检查。症状排查方向解决要点程序崩溃或段错误出栈时访问了空栈出栈和peek前必须显式判空数据错乱或输出异常值扩容时没有把旧数据完整拷贝检查扩容拷贝循环边界内存泄漏内存占用持续增长链式栈出栈后节点未释放pop和destroy时未free节点链表断线或死循环入栈出栈指针顺序写反头插法先改新节点next再改栈顶运行结果不正确表达式求值运算符优先级判断逻辑写错同优先级需要弹栈左结合除了表格里这些还有两个我个人觉得特别容易让人栽跟头的地方值得拿出来单独说一说。第一个是栈容量管理。有些初学者喜欢用一个固定大小的数组实现栈不去考虑扩容。这种做法在测试用例少时看着没问题一旦数据量稍大栈很快就被填满再入栈就崩了。解决方式有两个一是实现自动扩容的动态数组栈这在上面已经写过二是在入栈前调用一个isFull函数做检查并明确报错。我个人的经验是刷题时可以随便用固定大小但在实际项目里动态扩容是必须具备的基础能力。第二个是与“栈溢出”这个概念区分开。在数据结构里“栈溢出”通常指程序运行时系统调用栈超过了限制这往往是递归太深导致的。但是在数据结构书里也常把数组栈容量不够称为“栈溢出”。两个场景不同一个是内存崩溃一个是逻辑容量不足。理解它们的差异能让你在排查问题时少走弯路。8. 基于栈的进阶思路与个人经验总结最后我想分享一点我对栈这个数据结构更深层的思考。很多同学学数据结构时往往陷在具体的代码实现里背了定义、背了操作却忽略了它背后代表的思维方式。栈的本质是一种“递归”的表达方式。递归意味着一个问题可以被分解成同构的子问题并且在处理完子问题后需要回到上一层。而栈恰好就保存了这每一层子问题的状态。所以当你下次再遇到一个算法题时不妨先问问自己这个问题是否存在“嵌套”或“回溯”的影子如果有栈很可能就是一个值得考虑的方案。比如树的遍历中的非递归遍历很多都是用栈来模拟递归调用图算法中的深度优先遍历也是基于栈的甚至操作系统的函数调用本身也是靠系统栈支撑的。回过头来栈的代码实现本身并不难难的是理解它为什么这么设计以及在不同场景下如何取舍。我学习栈的过程里有过不少困惑但当我亲手把数组栈和链式栈各写三遍再把括号匹配、表达式求值这几个经典题目刷完内心对栈的理解就真正上了一个台阶。这篇文章带你从栈的逻辑本质、两种实现方案、代码细节、应用到避坑经验都过了一遍。我建议你最好不要只停留在阅读层面而是打开编辑器把数组栈实现一遍再改成链式栈实现一遍然后去力扣或者其他平台找几道相关的题目练手。只要把这两个实现和三个应用吃透我可以负责任地说数据结构这个关卡里栈这一关你就稳了。 
长河君 · 2026/10/22 15:43:04 · 阅读 1.2k 栈的底层逻辑与两种实现：数组栈和链表栈，从原理到代码实战
作为一名常年和数据结构和算法打交道的开发者我深知“栈”这个东西在面试和实际工程里的分量。但很多初学者在刚接触时总容易把它和“堆”搞混或者背熟了“后进先出”的定义一写代码就卡壳。所以今天这篇内容我不打算绕弯子直接把栈的底层逻辑、两种主流实现方式数组和链表、以及基于栈的经典应用场景全部拆开揉碎配上可以直接拿去用的代码希望能帮你把这块硬骨头啃下来。这篇文章适合正在上数据结构课程的同学、准备算法面试的求职者以及想补一补基础的程序员。我会从最核心的物理结构讲起再逐步过渡到抽象的逻辑行为最后落到实际的代码和避坑经验上。如果你能耐心看完并亲手把代码敲一遍我敢说栈这个知识点就算真正过关了。1. 栈的核心逻辑为什么说它像一叠盘子在动手写代码之前我们必须把栈的本质聊透。数据结构的核心无非就两件事数据的物理存储结构和数据的逻辑访问规则。物理存储结构决定了数据怎么在内存里放着而逻辑访问规则决定了外部代码该怎么去操作这些数据。栈的逻辑规则可以用一句话概括后进先出。这个概念在生活里最贴切的类比就是餐厅里那种弹簧托架上的一叠盘子。服务员收盘子或者取盘子永远只能接触到最顶上的那一个。如果你想要最底下的那个盘子就得把上面所有盘子一个个先拿走。这个操作顺序在计算机里有一个比较正式的名字叫LIFO也就是Last In First Out。这种限制恰恰是栈的价值所在。它把自由度降低换来的是极低的时间复杂度和极高的操作确定性。所有的插入入栈和删除出栈操作都只发生在栈顶这一个位置。这意味着我们不需要像数组那样为了找到一个元素而在内存里来回扫描也不需要像链表那样为了删除一个节点而小心翼翼地维护前后指针的指向。栈的一切操作时间复杂度都是O(1)。很多人会有个疑问既然它功能这么简单为什么在算法和系统底层里无处不在答案就在于栈天然适合处理“需要暂时保存状态然后在未来某个时刻以相反顺序恢复状态”的场景。函数调用过程中的参数和返回地址需要保存浏览器看你访问过的页面记录需要回退编译器要检查你写的括号是否匹配……这些场景的共同点都是存在一种“嵌套”和“回溯”的性质而栈的逻辑规则正好与这种性质严丝合缝。再往深了说栈有两种物理实现路线。一种是基于数组我们称之为顺序栈一种是基于链表我们称之为链式栈。这两种路线各有优劣没有绝对的好坏只有“合不合适”的问题。接下来我会分别拆解这两条路线的实现细节和选择标准这也是面试里极其高频的考察点。2. 实现方案的前期铺垫数组与链表带给你的不同底气在写栈的代码之前先花点时间把“底子”想清楚。所谓底子就是底层用数组还是链表。这两个选择会直接影响你的栈在扩容、内存碎片、访问效率三个维度上的表现。如果选择数组你面对的是一个连续的内存空间。数组最大的优点是CPU缓存友好。因为数据在物理地址上是挨在一起的CPU在读取数据时会把相邻的数据一并加载到缓存行里这意味着入栈和出栈操作往往命中缓存速度极快。数组的缺点是当栈容量不够需要扩容时你得重新开辟一块更大的内存然后把旧数据一个个拷贝过去。这个扩容过程的时间复杂度虽然是O(n)但好在它发生的频率并不高均摊下来性能依然可以接受。如果选择链表你面对的是一个个孤立的节点节点之间通过指针连接。链表的好处是不需要考虑扩容问题。因为它是动态的来一个数据就分配一个节点内存利用率理论上更高。但缺点也很明显链表节点的内存地址是散落的无法利用CPU缓存的预取机制同时每创建一个节点都要额外分配内存多了指针的读写开销。在大规模、高频的栈操作场景下链式栈往往不如顺序栈来得利索。所以我的个人经验是如果没有特殊的内存碎片考量默认优先选择数组实现栈。不仅因为性能更好、代码更短更重要的是顺序栈在算法题中几乎可以覆盖90%以上的应用场景。链式栈更多出现在项目设计需要灵活内存管理的场景比如一些无锁并发结构的设计证明中。但这里要特别提一个细节如果你选择链式栈一定要小心“头插法”和“尾插法”的区别。栈的入栈和出栈都发生在栈顶所以我们应该用头插法来构造链表栈。也就是说每次新入栈的节点都插到链表头部这样栈顶就是链表的头节点出栈时只需要把头节点摘下来返回即可。如果误用了尾插法那么出栈操作就需要遍历到链表尾部复杂度直接从O(1)退化到O(n)这样就完全丧失了栈的高效性。3. 手写代码基于动态数组的顺序栈从零实现接下来进入正题。我会先用C语言实现一个基于动态数组的顺序栈。选择C语言的原因是因为它足够底层没有像STL或者Java集合框架那样帮你封装好一切你能够清晰看到每一步的内存操作。理解了C语言版本后面再看其他语言的实现会轻松很多。3.1 结构体定义与容量管理机制首先我们定义一个栈的结构体里面需要包含三个核心成员数据指针、栈顶索引、容量。栈顶索引在数组实现中本质上就是“当前栈内元素的数量”也可以理解为“下一个入栈元素应该放的位置”。typedef struct { int *data; // 动态数组指针指向堆上分配的内存 int top; // 栈顶索引-1表示栈空 int capacity; // 当前分配的容量 } SeqStack;这里的初始容量我一般习惯设置为1024。如果你确定了数据的规模范围也可以直接初始化成你需要的大小。初始化容量太小会导致频繁扩容太大则会浪费内存。所以一个合理的初始容量是顺序栈性能的一项隐形指标。接下来是扩容机制。顺序栈的扩容逻辑和动态数组完全一样当top等于capacity减1时即栈满就把容量扩大到原来的两倍。两倍是一个工程上公认比较合理的增长倍数它保证了扩容操作的均摊时间复杂度是O(1)。如果每次只增加一个单位那么频繁的扩容会导致极低的效率如果增长倍数太大比如10倍虽然扩容次数少了但内存浪费会很严重。void expand(SeqStack *stack) { if (stack-top 1 stack-capacity) { return; // 空间足够无需扩容 } int new_capacity stack-capacity * 2; int *new_data (int *)malloc(sizeof(int) * new_capacity); if (new_data NULL) { printf(内存分配失败\n); exit(1); } // 拷贝旧数据到新区域 for (int i 0; i stack-top; i) { new_data[i] stack-data[i]; } free(stack-data); // 释放旧内存 stack-data new_data; stack-capacity new_capacity; }3.2 关键操作的边界条件与返回值约定栈的五大核心操作是初始化、判空、入栈、出栈、取栈顶元素。每个操作都有它自己的边界条件你必须要在编码时敏锐地处理它们。初始化很简单就是分配内存并设置初始值。这里有个小坑很多人会忘记初始化top为-1导致后续判断出错。void init(SeqStack *stack, int capacity) { stack-data (int *)malloc(sizeof(int) * capacity); stack-top -1; stack-capacity capacity; } int isEmpty(SeqStack *stack) { return stack-top -1; }入栈操作push需要先判断是否扩容然后先移动top索引再写入数据。这里要注意顺序也可以先写入再移动索引但为了避免逻辑混乱建议统一为先移动、再赋值。void push(SeqStack *stack, int value) { expand(stack); stack-top; stack-data[stack-top] value; }出栈操作pop是一个容易出错的地方因为它涉及两个动作取出栈顶值然后top索引下移。如果你先下移索引就取不到栈顶元素了如果你先取元素随后的索引下移要确保安全。更关键的是出栈时我们需要处理“空栈”的情况。如果栈是空的你还想弹出元素那这就属于一个越界操作。对于这种异常场景业界有两种常见做法一种是返回一个约定好的错误值比如-1另一种是通过输出参数返回结果同时用函数返回值指示操作是否成功。我强烈推荐第二种做法因为用错误值来兼作数据和状态在很多真实场景下是不可靠的。比如如果这个栈存的就是整数而你恰好要入栈一个-1那这个-1到底是正常数据还是空栈标记无法区分。int pop(SeqStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空无法出栈\n); return 0; // 0表示失败 } *value stack-data[stack-top]; stack-top--; return 1; // 1表示成功 }取栈顶元素peek和pop的区别在于peek只读取栈顶元素栈的状态不发生任何变化。这个操作常用于查看当前状态而无需立即移除它。在括号匹配场景中我们就经常用peek来检查当前栈顶的括号是否和当前遇到的右括号成对。int peek(SeqStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空无法读取栈顶元素\n); return 0; } *value stack-data[stack-top]; return 1; }等所有操作完成后别忘了释放堆内存。这也是一个常被忽略的坑单纯用完之后不调用free在长期运行的程序中会造成内存泄漏导致程序占用内存越来越大。正确的释放逻辑是先释放data指针指向的堆内存再重置各字段。void destroy(SeqStack *stack) { if (stack-data ! NULL) { free(stack-data); stack-data NULL; } stack-top -1; stack-capacity 0; }可以看到基于数组的顺序栈整体代码量不大逻辑也非常直观但它考察的是你对数组索引边界的敏感度、动态内存管理的熟练度还有异常处理的严谨度。这三个点都是在面试中会被细致追问的细节。4. 链式栈的清爽实现头插法带来的灵动体验说完了数组实现我们再看看链表实现。如果说数组栈的精髓在于“索引计算”那么链式栈的精髓就在于“指针翻转”。4.1 节点的初始化与栈的构造链表的基本单元是节点。每个节点包含数据域和指针域。链式栈的栈顶就是链表的头节点因此我们需要维护一个指向头节点的指针。栈为空时这个指针为NULL。typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *top; // 栈顶指针指向链表头节点 } LinkedStack;初始化时只需要将top置为NULL即可。这里不需要像顺序栈那样提前分配内存链表的内存是按需分配因此初始化动作非常简单。void init(LinkedStack *stack) { stack-top NULL; } int isEmpty(LinkedStack *stack) { return stack-top NULL; }4.2 入栈出栈的指针变换逻辑链式栈的入栈操作本质上就是一次“头插法”的链表插入。先创建一个新节点如果内存分配失败则返回错误然后将新节点的next指针指向当前栈顶最后更新栈顶指针让它指向新节点。int push(LinkedStack *stack, int value) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) { printf(内存分配失败\n); return 0; } node-data value; node-next stack-top; // 新节点的后继指向旧栈顶 stack-top node; // 栈顶更新为新节点 return 1; }这个过程中指针的赋值顺序非常重要。很多人第一次写链表插入时会把node-next stack-top和stack-top node这两行写反导致新节点自己指向自己形成一种“幽灵环”整个链表就断线了。这里面一个相对稳妥的思考方式先处理新节点的指针指向再更新栈顶指针。因为如果你先更新了stack-top你就丢失了旧栈顶的地址新节点的next就无法正确连上旧节点了。出栈操作则是对应头节点的删除操作。我们需要临时保存旧栈顶节点读取它的数据然后将栈顶指针下移指向下一个节点最后释放旧节点的内存。int pop(LinkedStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空无法出栈\n); return 0; } Node *tmp stack-top; *value tmp-data; stack-top tmp-next; // 栈顶移动到下一个节点 free(tmp); // 释放旧栈顶 return 1; }这里有一个隐性的内存管理知识如果你在出栈时忘记free这一句那么被弹出的节点就成了“孤儿节点”它占用的内存没有被回收引用它的指针又不存在了系统无法自动回收它这就发生了内存泄漏。在非垃圾回收语言里这是一个必须高度警惕的问题。取栈顶元素则更简单只需要判断非空然后返回top-data即可不需要移动指针也不需要释放任何内存。int peek(LinkedStack *stack, int *value) { if (isEmpty(stack)) { printf(错误栈为空\n); return 0; } *value stack-top-data; return 1; }链式栈的销毁逻辑需要循环释放所有节点。这里要注意你不能在free一个节点的同时去访问它的next因为free之后这个节点的内存就已经被回收了里面的指针数据不可信。正确的做法是用一个临时指针先保存next再free当前节点。void destroy(LinkedStack *stack) { Node *current stack-top; while (current ! NULL) { Node *next current-next; free(current); current next; } stack-top NULL; }链式栈的代码在逻辑上和顺序栈略有不同但本质上都是O(1)的入栈和出栈。它的优势是完全不需要考虑扩容问题入栈时只受系统可用内存限制因此在数据量不确定或内存碎片不是主要矛盾的情况下链式栈更灵活。5. 两种实现的硬核对比从性能到代码可读性的取舍当你掌握了两种实现之后很自然会遇到一个问题到底该用哪种我这边的建议是看场景选方案。为了更直观点我把两种实现的关键差异整理成下面的表格方便对照。数组栈的优势主要体现在速度与缓存友好性上而链式栈的优势主要体现在灵活的内存管理上。如果你的程序频繁创建和销毁栈并且不知道峰值数据量那么链式栈能够省下大量扩容和心跳检测的逻辑。如果你的程序追求极致性能并且数据量在可预见的范围内是可控的那么数组栈肯定是更合适的。这里提醒一下数组栈的扩容操作本身是一次性开销虽然均摊后很低但在对时间极其敏感、不允许任何毛刺的嵌入式环境里这个偶发的扩容拷贝也可能成为你不愿意看到的延迟点。对比维度顺序栈数组实现链式栈链表实现入栈/出栈时间复杂度O(1)O(1)需考虑扩容需要动态2倍扩容不需要天然动态内存空间占用紧凑只有数据额外存储指针缓存友好性优秀物理连续较差地址分散异常处理复杂度需处理栈满扩容失败需处理节点分配失败典型应用场景表达式求值、括号匹配、函数调用栈深度优先遍历、内存分配器、动态任务栈除了性能代码的可读性也是一个值得权衡的因素。数组栈的实现虽然短但是它的“扩容”核心逻辑容易让初学者混淆链式栈的代码结构清晰指针操作更能帮助理解链表结构本身。我自己在教学过程中观察到部分同学在教材上能看懂代码但一到自己动手写链式栈就卡壳。如果你也是这种情况建议多写几遍或者把链表本身的操作头插法和头删法练习熟再来看栈就会觉得薄薄一层窗户纸。6. 栈的经典应用实践从括号匹配到表达式求值栈的代码写完了如果不应用到实际问题里难免会觉得它只是个“数据结构练习”。下面我挑两个比较经典的应用场景分别是括号匹配和表达式求值用它们来检验上面写的栈是否够格进入实战环节。6.1 括号匹配状态保存与回退的绝佳示例括号匹配也叫括号配对检测。你在代码里写了这么一行表达式{[()]}。编译器如何知道这串括号是合法的关键在于计算机扫描时遇到左括号就入栈遇到右括号时就要从栈顶取一个左括号来匹配。如果栈顶的左括号和当前右括号不配对或者当栈已经是空的却还遇到右括号就说明这个字符串是不合法的。我们写个函数实现这个逻辑。这里用到的就是上面实现的链式栈。如果栈里存放的是字符类型别忘了把之前代码里的int换成char。int isMatching(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } int isValid(char *s) { SeqStack stack; init(stack, 128); for (int i 0; s[i] ! \0; i) { char c s[i]; if (c ( || c [ || c {) { push(stack, c); } else if (c ) || c ] || c }) { char top; if (!pop(stack, top)) { return 0; // 栈空却遇到右括号不匹配 } if (!isMatching(top, c)) { return 0; // 左右括号类型不一致 } } } int empty isEmpty(stack); destroy(stack); return empty; }整个过程是一个状态机式的推进左括号压入时等于把当前状态存档右括号弹出时等于验证并回溯。这种“存档—回溯”的逻辑正是栈最核心的魅力所在。很多更复杂的算法比如深度优先搜索DFS、回溯法求解八皇后、走迷宫等核心思想都源于这个简单的机制。6.2 表达式求值中缀转后缀与后缀计算表达式求值是一个非常经典的算法场景。常见的表达式叫中缀表达式比如3 5 * 2。人脑一看就知道乘法的优先级高于加法但计算机不这么理解。它要把中缀表达式转换成后缀表达式也叫逆波兰表达式转换完的结果是3 5 2 * 。后缀表达式的特点是操作数在前运算符在后并且完全没有括号。计算机在计算后缀表达式时需要一个栈遇到数字就入栈遇到运算符就弹出两个数字然后做运算把结果重新压入栈。中缀转后缀的算法也叫调度场算法它的核心就是一个运算符栈。规则如下遇到操作数直接输出。遇到左括号入栈。遇到右括号弹出栈顶运算符直到遇到左括号。遇到运算符与栈顶运算符比较优先级如果栈顶优先级不低于当前运算符则弹出栈顶直到栈空或栈顶优先级低于当前运算符并将当前运算符入栈。我这里不展开完整的代码因为篇幅太长但你可以对照这个规则自己写一遍。这个过程非常锻炼你对栈的运用能力和对算法分支条件的细心程度。我之前在实现时就被“运算符优先级比较”这个环节坑过规则里有一句“同优先级左结合”这意味着当栈顶运算符和当前运算符优先级相等时你也需要弹出栈顶而不是直接把当前运算符压栈。如果写反了最终的计算结果就会错误且很难在少量测试用例中暴露出来。表达式求值的完整实现涉及多个函数包括运算顺序处理、栈的应用等。但只要你把栈的入库出库逻辑理解透这个算法写下来并不会特别复杂反而会觉得很顺滑。7. 实操中的典型踩坑与排查技巧速查代码写得多了遇到坑是不可避免的。我在早期学习和写项目的过程中在栈这块就踩过不少雷。这里我把几个高频、常见的坑集中整理成表格你在自己动手时可以重点对照检查。症状排查方向解决要点程序崩溃或段错误出栈时访问了空栈出栈和peek前必须显式判空数据错乱或输出异常值扩容时没有把旧数据完整拷贝检查扩容拷贝循环边界内存泄漏内存占用持续增长链式栈出栈后节点未释放pop和destroy时未free节点链表断线或死循环入栈出栈指针顺序写反头插法先改新节点next再改栈顶运行结果不正确表达式求值运算符优先级判断逻辑写错同优先级需要弹栈左结合除了表格里这些还有两个我个人觉得特别容易让人栽跟头的地方值得拿出来单独说一说。第一个是栈容量管理。有些初学者喜欢用一个固定大小的数组实现栈不去考虑扩容。这种做法在测试用例少时看着没问题一旦数据量稍大栈很快就被填满再入栈就崩了。解决方式有两个一是实现自动扩容的动态数组栈这在上面已经写过二是在入栈前调用一个isFull函数做检查并明确报错。我个人的经验是刷题时可以随便用固定大小但在实际项目里动态扩容是必须具备的基础能力。第二个是与“栈溢出”这个概念区分开。在数据结构里“栈溢出”通常指程序运行时系统调用栈超过了限制这往往是递归太深导致的。但是在数据结构书里也常把数组栈容量不够称为“栈溢出”。两个场景不同一个是内存崩溃一个是逻辑容量不足。理解它们的差异能让你在排查问题时少走弯路。8. 基于栈的进阶思路与个人经验总结最后我想分享一点我对栈这个数据结构更深层的思考。很多同学学数据结构时往往陷在具体的代码实现里背了定义、背了操作却忽略了它背后代表的思维方式。栈的本质是一种“递归”的表达方式。递归意味着一个问题可以被分解成同构的子问题并且在处理完子问题后需要回到上一层。而栈恰好就保存了这每一层子问题的状态。所以当你下次再遇到一个算法题时不妨先问问自己这个问题是否存在“嵌套”或“回溯”的影子如果有栈很可能就是一个值得考虑的方案。比如树的遍历中的非递归遍历很多都是用栈来模拟递归调用图算法中的深度优先遍历也是基于栈的甚至操作系统的函数调用本身也是靠系统栈支撑的。回过头来栈的代码实现本身并不难难的是理解它为什么这么设计以及在不同场景下如何取舍。我学习栈的过程里有过不少困惑但当我亲手把数组栈和链式栈各写三遍再把括号匹配、表达式求值这几个经典题目刷完内心对栈的理解就真正上了一个台阶。这篇文章带你从栈的逻辑本质、两种实现方案、代码细节、应用到避坑经验都过了一遍。我建议你最好不要只停留在阅读层面而是打开编辑器把数组栈实现一遍再改成链式栈实现一遍然后去力扣或者其他平台找几道相关的题目练手。只要把这两个实现和三个应用吃透我可以负责任地说数据结构这个关卡里栈这一关你就稳了。