C 链栈这个东西我是在啃完指针和类之后才真正用明白的。以前刷算法题栈多半用数组模拟简单是简单可一旦数据量没法提前估准要么预判尺寸踩内存要么反复扩容白耗性能。链栈就是为这种场景准备的用链表把元素串起来来一个就 new 一个节点完全不关心上限。这篇内容想从一个手写实现的角度把链栈的结构设计、完整代码、常见内存陷阱一次讲透。适合刚学完 C 基础的初学者也适合面试前想快速巩固栈实现细节的开发者。1. 链栈整体设计与思路拆解1.1 链栈是什么什么时候非它不可栈是一种只允许在一端进行插入和删除的线性表这一端叫栈顶另一端叫栈底。链栈就是用链表作为底层存储的栈入栈和出栈都发生在链表头部因此天然具备 O(1) 的入栈、出栈、取栈顶能力。我说个最常见的坑你写一个网络协议解析器收到的数据包里有若干条子记录条数由报文内容决定。你根本不知道最多会有多少条开一个 1024 大小的数组怕不够开 10 万个又怕浪费。这时候顺序栈的固定容量就成了累赘。有人会说我用动态数组 vector 不就行了可以但 vector 扩容时要把旧数据搬到新内存搬移本身有代价还会产生内存碎片。链栈的思路是按需分配来一条数据就 new 一个节点用完了再释放数据规模无论多大只要堆内存够就永远不会溢出。栈的典型应用远不止协议解析。函数调用栈、括号匹配、表达式求值、数制转换、浏览器的前进后退、文本编辑器的撤销重做、深度优先搜索的辅助结构全部是栈的天下。在这些场景里你很难预估操作深度的上限用链栈从设计上就消除了栈满这个状态。从学习的角度看链栈是理解指针操作的绝佳载体。它比链表更简单因为只操作头部避开了单链表最麻烦的找前驱问题它又比简单的数组栈更接近底层你能直观感受到 new 和 delete 的配对关系、悬空指针的成因、内存泄漏的隐蔽性。所以我一直建议初学者不要只满足于std::stack至少手写一遍链栈。1.2 顺序栈与链栈怎么选我把两种实现的差异整理成了表格方便对照对比维度顺序栈链栈底层空间一段连续内存离散节点靠指针连接扩容方式容量不够时要搬迁数据每次入栈分配一个节点访问效率缓存局部性好指针跳转缓存命中率相对低内存占用需要预留容量可能浪费每个节点额外存一个 next 指针插入删除O(1)扩容时触发搬迁O(1)且稳定适用场景数据规模已知且稳定规模未知或波动剧烈选型逻辑很直白如果你能估算出栈的深度上限并且这个上限和实际使用量差距不大顺序栈明显更好。连续内存意味着更少的 cache miss遍历和批量操作都快。反过来如果数据规模不可预估或者栈的对象很大、频繁进出链栈更省心因为不会为了少数几次扩容而整体搬迁。还有一点容易被忽略链栈的每个节点包含 next 指针在 64 位系统下是 8 字节。如果你存的本来就是 int 这类 4 字节元素链栈实际要多花两倍的内存。这个代价能否接受得具体场景具体分析。我的习惯是刷题和写小型工具用顺序栈系统级、长时间运行且容量不可控的程序用链栈。1.3 手写链栈的三种可行方案在 C 里实现链栈至少有三种路线。第一种裸指针手写单链表。代码量最大但对理解内存管理最有效。你需要自己管理节点的构造、析构、拷贝、赋值稍不留神就是悬空指针或内存泄漏。可正是这些坑让人真正学会 C 的内存语义。第二种基于std::forward_list封装。forward_list 是 C 标准库里的单向链表用push_front模拟入栈pop_front模拟出栈front取栈顶。代码很短但封装之后你对底层发生了什么都不敏感而且 forward_list 的接口设计本来就有点别扭不如手写直观。第三种直接使用std::stackT。它的底层默认是std::deque双端队列实际是一个分段连续的结构。业务开发里我强烈建议用这个标准库容器成熟、异常安全、迭代器齐全没必要自己造轮子。但这篇文章我要讲的是第一种。原因很简单学习数据结构的意义不在于会用栈而在于理解栈。你亲手写出 push、pop、析构才能明白为什么标准库的pop不返回被弹出的元素为什么拷贝一个没写拷贝构造的容器会崩。这些知识在面试和实际调试中非常值钱。2. 核心结构定义与细节解析2.1 节点结构链表的基本单元链栈的基石是节点。每个节点保存一份用户数据和指向下一个节点的指针struct Node { T data; Node* next; };两个成员都有讲究。data直接存对象本身而不是存对象指针这样你在入栈时传一个对象进来节点构造时自动拷贝一份。如果改成T* data你就得额外管理指针指向的内存的释放每个元素会多一次堆分配性能差还容易漏。next指向下一个节点。因为是栈我们只需要单向链表不需要双向。栈顶在链表头部head 指针就是栈顶指针不需要知道栈底在哪所以单链表足够。这里有个小细节为什么我把 Node 定义在 LinkStack 类的私有区域因为 Node 是内部实现细节外部代码不应该直接操作节点。把 Node 放在 private 里可以让LinkStackT::Node不对外暴露防止有人绕过栈接口改链表结构。你也许会想放在类外那也不是不行但尽量让它成为类的私有嵌套类型语义更干净也符合封装原则。2.2 栈类的成员设计一个最小可用的链栈类至少需要两个成员Node* top_; // 栈顶指针也就是链表头指针 std::size_t size_; // 栈中元素个数top_必须存在否则不知道从哪里入栈出栈。size_可能有人觉得多余毕竟判断空栈可以直接看top_ nullptr。但是加上它在很多场合更方便取元素个数时不用遍历整个链表时间复杂度从 O(n) 降到 O(1)。比如你在调试时想打印栈内元素数量或者在写业务逻辑时需要快速判断栈的大小这个成员就很有价值。再一个问题链栈要不要带头结点我看到不少教材里的链表都带头结点理由是统一处理在空链表头部插入和在非空链表头部插入的逻辑。但对链栈来说这个理由不成立。链栈的所有操作都在头部无论链表是否为空top_指针的更新方式完全一致入栈时新节点的 next 指向旧 top再让 top 指向新节点出栈时 top 指向 next。不存在在链表中间插入时需要找前驱这种麻烦。带头结点反而会让栈对象多一个无意义的节点判断空栈的逻辑也变复杂。因此我在实现里不带头结点。2.3 内存生命周期与拷贝控制为什么重要手写链栈最绕不开的话题是内存生命周期。每个new出来的节点必须由同一个栈对象在某个时刻delete掉。如果栈对象析构时没有释放所有节点这些节点就泄漏了。如果两个栈对象共享同一串节点析构时就会释放两次直接崩溃。C 里有一条著名的规则叫三/五法则一旦类需要自定义析构函数那么大概率也需要自定义拷贝构造函数和拷贝赋值运算符因为这三个函数通常一起出现共同管理同一块资源。具体到链栈默认析构函数不会释放节点这导致内存泄漏默认拷贝构造函数执行浅拷贝两个对象的top_指向同一串节点其中一个析构后另一个再析构就是 double free。后面我会给出一份完整的拷贝控制代码这里先记住结论任何拥有裸指针资源的类都要认真考虑三/五法则而不是依赖编译器的默认行为。移动语义在 C11 之后也很重要。如果你的链栈能移动构造那么返回一个局部栈对象时就不会发生逐节点拷贝性能好很多。移动构造的本质是把对方的top_指针偷过来然后把对方的指针置空。这部分我也会在实现里补全。3. 实操过程与核心环节实现3.1 基础结构从节点到栈类先把一个最小可用的链栈类完整写出来。这份代码可以在任意 C11 及以上的编译器上编译运行#include cstddef #include stdexcept #include utility template typename T class LinkStack { private: struct Node { T data; Node* next; }; public: LinkStack() : top_(nullptr) , size_(0) { } ~LinkStack() { clear(); } void push(const T value) { Node* new_node new Node{value, top_}; top_ new_node; size_; } void pop() { if (empty()) { throw std::out_of_range(LinkStack::pop: stack is empty); } Node* old top_; top_ top_-next; delete old; --size_; } const T top() const { if (empty()) { throw std::out_of_range(LinkStack::top: stack is empty); } return top_-data; } bool empty() const { return size_ 0; } std::size_t size() const { return size_; } void clear() { while (top_ ! nullptr) { Node* old top_; top_ top_-next; delete old; } size_ 0; } private: Node* top_; std::size_t size_; };这段代码的骨架很清晰一个模板类、一个私有嵌套节点、五个核心操作。模板让它可以装 int、double、string、自定义对象复用性拉满。我在 main 里会用LinkStackstd::string演示你可以随意替换类型。3.2 入栈出栈取顶判空逐个手写顺便讲清原理入栈 push。我采用的是头插法也就是永远在新节点插到链表最前面。为什么不用尾插因为栈顶在头部头插才能保证入栈是 O(1)。如果尾插你得维护一个尾指针出栈时还要找尾节点的前驱单链表找前驱只能从头遍历效率直接变成 O(n)。头插法的更新逻辑非常干净Node* new_node new Node{value, top_}; top_ new_node; size_;注意一个顺序先 new 出节点然后在更新top_。如果new抛出异常旧的栈还保持原样不会产生坏状态这是最基本的异常安全。有些初学写法是先top_ new Node{value, top_}这句在语义上也差不多但显式写出中间变量更容易看出先分配、后连接的过程。出栈 pop。标准库stack::pop的惯例是不返回被弹出的元素我们的实现也遵循这个约定。原因是如果 pop 既要移除元素又要返回元素就会出现两难返回引用的话节点在返回后就被删除引用悬空返回拷贝的话拷贝过程可能抛异常被弹出的元素去哪了说不清。所以正确用法是先调top()拿值再调pop()移除。Node* old top_; top_ top_-next; delete old; --size_;这里移动top_一定在delete old之前。如果你先 delete 再取top_-next那就是访问一块已经释放的内存属于未定义行为通常表现为随机崩溃或读到脏数据。我在问题实录部分会专门展开。取栈顶 top。返回const T而不是值是为了避免不必要的拷贝。如果返回 T 值每次调用都会复制一个对象对大型对象来说代价不小。const修饰符表示这个方法不修改栈所以 const 对象也能调用它。const T top() const { if (empty()) { throw std::out_of_range(LinkStack::top: stack is empty); } return top_-data; }空栈时我选择抛std::out_of_range。这是防御式做法让调用者能快速定位问题。如果你在写高性能的内核代码抛异常的开销可能不可接受那可以用 assert 或者直接约定调用者保证栈非空。判空和取 size。都是 const 成员函数bool empty() const { return size_ 0; } std::size_t size() const { return size_; }empty基于size_判断复杂度 O(1)。如果只写成top_ nullptr也一样但有了size_后empty的实现会自然一些。析构和 clear。clear负责释放所有节点循环删除头部节点直到空void clear() { while (top_ ! nullptr) { Node* old top_; top_ top_-next; delete old; } size_ 0; }析构函数直接调用clear()保证栈对象在生命周期结束时自动回收所有堆内存。这一步一旦漏掉程序运行时间越长越容易内存暴涨而且是那种难以察觉的泄漏。3.3 在主函数中跑通全流程写完类之后写一个 main 验证它是否正常工作#include iostream #include string int main() { LinkStackstd::string st; st.push(first); st.push(second); st.push(third); std::cout size: st.size() \n; std::cout top: st.top() \n; while (!st.empty()) { std::cout st.top() \n; st.pop(); } return 0; }运行结果size: 3 top: third third second first可以看到入栈顺序是 first、second、third出栈顺序恰好相反这就是栈的后进先出语义。每次从栈顶取出一个元素再让它出栈直到空栈。这个循环是使用栈最经典的姿势很多算法题里的弹出全部元素都是这个模式。这里顺带讲一个使用技巧栈天然可以用来反转序列。比如你把一串字符依次压栈再依次弹出得到的顺序就是原序列的逆序。很多题目里的倒序输出括号匹配表达式求值本质都是这个特性。编译环境方面如果你在 Linux 或 macOS 上直接执行g -stdc11 -Wall -pedantic main.cpp -o main在 Windows 上如果用 Visual Studio新建控制台项目把代码贴进去即可。加-Wall能帮你在编译期揪出一些粗心错误我建议新手一直开着。3.4 补全拷贝控制让类能安全复制基础版本能跑但还不能复制。执行下面这段代码会崩LinkStackint a; a.push(10); LinkStackint b(a); // 默认拷贝构造浅拷贝因为b.top_和a.top_指向同一个节点析构时 double free。要解决这个问题得自己写拷贝构造和拷贝赋值。我用的是链式拷贝构造加 copy-and-swap 赋值LinkStack(const LinkStack other) : top_(nullptr) , size_(0) { Node** tail top_; for (Node* cur other.top_; cur ! nullptr; cur cur-next) { *tail new Node{cur-data, nullptr}; tail ((*tail)-next); size_; } } LinkStack operator(const LinkStack other) { if (this ! other) { LinkStack tmp(other); std::swap(top_, tmp.top_); std::swap(size_, tmp.size_); } return *this; }拷贝构造采用尾插法重建整条链。tail是一个指向Node*的指针初始指向top_每次新建节点后让tail指向新节点的 next 成员这样链子就能一路接下去。这个写法稍微绕一点但比维护一个prev变量更简洁也不容易写错。赋值运算符用 copy-and-swap先复制一份临时对象再交换指针和 size。临时对象会在函数结束时析构自动释放原来的节点。这样写还能顺便获得异常安全如果构造 tmp 时抛异常原来的对象纹丝不动。再补上移动构造和移动赋值C11 之后可以让链栈在返回时避免深拷贝LinkStack(LinkStack other) noexcept : top_(other.top_) , size_(other.size_) { other.top_ nullptr; other.size_ 0; } LinkStack operator(LinkStack other) noexcept { if (this ! other) { clear(); top_ other.top_; size_ other.size_; other.top_ nullptr; other.size_ 0; } return *this; }移动构造的语义是偷走对方的指针然后把对方置空。这样临时对象析构时不会释放我们已经拿走的内存。移动赋值同理先释放自己的旧节点再接住对方的节点。这里的noexcept很重要它告诉标准库这个操作不会抛异常这样std::vectorLinkStackT扩容时愿意用移动而不是拷贝性能会好很多。加到这些代码后链栈类就具备完整的资源管理能力了可以放心放进各种容器里。4. 常见问题与排查技巧实录4.1 先 delete 再取 next崩溃当场这是初写弹栈操作时最容易犯的错误错误写法长这样void pop() { Node* old top_; delete old; // 先释放 top_ top_-next; // 访问已释放内存 }释放之后top_指向的是已回收的内存top_-next读取的是一块游离内存的字节。系统未必立刻崩溃有时候那块内存的数据还留在原地程序照样能跑于是你产生这样写其实没事的错觉。等到数据量变大、堆管理器复用了内存程序才在某次 pop 时突然段错误。这种随机性非常难查。正确顺序必须是先移动指针再释放节点Node* old top_; top_ top_-next; delete old;原则就一条还没读完一个对象的数据就永远不要释放它。顺带一提clear()循环里也遵循同样的逻辑。4.2 不写析构函数泄漏无声发生如果你没定义析构函数编译器会生成一个隐式析构函数而这个隐式版本对裸指针什么都不做。也就是说你每new一个节点都不会被回收。进程长时间运行堆内存持续上涨最终可能被杀掉或 OOM。排查的办法很多。Linux 下最常用的是 valgrindvalgrind --leak-checkfull ./mainWindows 的 Visual Studio 调试环境里可以调用_CrtDumpMemoryLeaks()。注意调用时机链栈对象必须已经析构所以别把它直接写在 main 函数结尾的子代码段外。更稳的做法是把业务逻辑放进独立函数#include crtdbg.h void demo() { LinkStackint st; st.push(1); } int main() { demo(); _CrtDumpMemoryLeaks(); return 0; }demo结束的瞬间st已经析构。如果此时_CrtDumpMemoryLeaks还报泄漏说明析构或 clear 逻辑有问题。这对验证链栈实现的正确性特别有用。4.3 默认拷贝导致 double free这也是高频崩溃点。你写了一个链栈用默认拷贝构造复制了一份程序运行到结尾两个对象依次析构。第一个析构释放了整条链表第二个析构时top_还指向同一个节点于是第二次 delete 同一块内存。轻则程序崩溃重则堆元数据被破坏崩溃时机完全随机。解决方式在 3.4 已经给出写深拷贝构造和拷贝赋值。如果你明确不希望链栈被复制也可以直接删除拷贝方法LinkStack(const LinkStack) delete; LinkStack operator(const LinkStack) delete;面试时如果被问道为什么没写拷贝构造会崩大概率就是这个知识点。回答时最好能提到浅拷贝导致多个对象共享同一资源析构时多次释放一句话就能让对方知道你理解了根因。4.4 空栈操作与 const 修饰符遗漏空栈调用 pop 或 top 是未定义行为。在我的实现里pop 和 top 都主动抛std::out_of_range所以空栈操作会立刻暴露问题。如果你用标准库的std::stack空的 stack 上 pop 是不检查的调用者必须负责保证非空。这是教学实现和标准库实现的一个风格差异。const 修饰符是另一个容易踩的点。如果empty()、size()、top()没有写 const那么当你有一个 const 引用时这些方法无法调用。例如const LinkStackint ref st; if (ref.empty()) { // 编译错误empty 不是 const 成员函数 }几乎所有不修改内部状态的成员函数都应该写成 const 成员函数。写类的时候先想清楚这个方法会不会改变对象状态会改的写非 const不会改的加 const这样的类用起来才顺手。4.5 链栈问题速查表我把实战里最常遇到的几类问题整理成速查表方便你排错时一眼定位症状可能原因处理方式pop 之后程序随机崩溃先 delete 再读 next先移动 top_ 指针再释放旧节点程序内存持续增长缺析构函数或 clear 未调用补析构并确保 clear 释放所有节点复制后两端都析构时崩溃默认拷贝构造导致浅拷贝自定义深拷贝/赋值或禁止拷贝const 对象调用 empty 编译失败成员函数漏写 const所有只读接口统一加 const空栈 top 返回随机值未判空直接访问 top_接口内判空并抛异常入栈后旧数据丢失调整 top_ 前未把旧 top 接到新节点先 new 新节点让 next 指向旧 top_拷贝赋值后自身数据泄漏赋值前未释放旧节点使用 copy-and-swap 模式这张表里的坑几乎每一个我都在实际代码里踩过。最值得反复强调的还是这三条new 和 delete 必须严格配对浅拷贝是万恶之源空栈操作一定要有防御。链栈本身是个很小的结构但认真手写一遍收获远不止会写一个栈那么简单。你在 push 里学会了异常安全的构造顺序在 pop 里学会了悬空指针的预防在析构里学会了资源回收的重要性在拷贝控制里学会了深拷贝和移动语义的价值。这些能力放到任何 C 项目里都派得上用场。我建议你写完之后用 valgrind 或_CrtDumpMemoryLeaks跑一遍确认没有任何泄漏然后试着扩展几个练习给链栈加一个getMin()方法实现括号匹配或者用两个链栈模拟一个队列。等你把这些都写顺了回头看最初那个用数组模拟栈的代码会发现思路完全不一样了。