栈大概是数据结构里最“老实”的一个结构了——你放进去一叠元素它只按完全相反的顺序给你吐出来。后进先出的规则听起来简单但真要在C里用链表把它实现出来却能把指针、内存管理、拷贝控制这些C核心基本功全都串一遍。尤其是很多同学数组版栈写得飞起一到链表版就到处段错误、内存泄漏半天调不出来。这篇就用一个完整可运行的链表栈实现把设计思路、代码细节、坑位排查一次讲透。这个实现适合谁备考408或者期末复习数据结构的人正在学C、想练链表和指针的自学者还有面试前想快速把基础容器捡起来的朋友。你不需要多高深的基础理解结构体、指针和new/delete就能跟上。看完之后你得到的不仅是一段能跑的代码更是“为什么链表栈要这样设计”的完整逻辑。1. 为什么用链表实现栈先看清两种方案的底层差异1.1 数组栈的短板在哪里先别急着敲代码得弄明白为什么全世界教材都爱把“栈的链表实现”单独拎出来讲。用数组实现栈确实简单一个数组、一个top下标push就是arr[top] valpop就是top--。但数组栈有个一辈子躲不过去的问题——容量。容量小了吧数据一多就栈满得扩容。扩容就得重新申请一块更大的内存把旧数据全部拷过去再释放旧空间。这个操作是O(n)的虽然整体均摊下来还能接受但如果你写的是一个需要长时间稳定运行的底层模块某一次突然卡顿很可能就是扩容引起的。还有一点数组栈pop之后元素只是逻辑上“没了”底层数组空间还在那儿占着。你要是存的是对象还会发现对象根本没被析构内存也没真正释放只是top下标变小了而已。空间不回收、容量要预设这两个问题在嵌入式、操作系统内核这类内存敏感的场景里会非常难受。1.2 链表天然就是为“栈顶操作”准备的链表栈的思路就是绕开“连续内存”这个限制每个元素一个节点用指针串起来需要多少就分配多少。你new一个节点它就是栈顶你把节点delete掉栈顶就退回上一个节点。最关键的是栈的两种核心操作——入栈和出栈——都发生在栈顶。而链表里对头节点的插入和删除恰好也是O(1)的。这两个O(1)一碰整个方案就成立了链表栈不需要头尾都能操作的双向链表只要维护一个头指针就已经完美匹配栈的所有需求。用大白话说数组栈像是在固定大小的抽屉里叠盘子满了就得换个大抽屉还得把盘子重新摆一遍链表栈像是你手里拿了一叠盘子每次新增就随手放最上面拿走也直接从最上面抽。后进先出的特性正好对应链表头部的“高频操作”。1.3 时间复杂度对比不是谁优谁劣而是看场景操作数组栈链表栈push均摊O(1)最坏O(n)扩容拷贝严格O(1)popO(1)O(1)获取栈顶O(1)O(1)判空O(1)O(1)空间预分配启动时分配一大块可能浪费按需分配额外开销是一个next指针内存回收pop不真正释放空间pop即delete立即释放看到没链表栈几乎在所有操作上都是“稳定O(1)”代价是每个节点要多存一个next指针8字节而且频繁new/delete会有不小的内存分配开销。所以它俩不是谁替代谁的关系而是应用场景不同需要峰值性能稳定、不允许偶尔卡顿就选链表栈要求缓存友好、连续内存遍历快就选数组栈。2. 接口设计与完整代码骨架先把类结构定清楚2.1 节点结构为什么把Node定义在栈类内部链表的第一步是定义节点。我建议把节点结构体直接定义在栈类内部做成一个私有嵌套结构。template typename T class LinkedStack { private: struct Node { T data; Node* next; Node(const T val, Node* nxt nullptr) : data(val), next(nxt) {} }; Node* top_; size_t count_; public: LinkedStack() : top_(nullptr), count_(0) {} ~LinkedStack() { clear(); } // ... 其他成员函数 };把Node定义在类内部好处很明显对外完全隐藏节点细节用户不需要关心栈底层是用数组还是链表实现的同时避免外部误用Node类型防止你在写业务代码时不小心把链表结构造出环来。构造函数顺手写好后面new节点的时候就能一行搞定。Node节点里next初始化为nullptr的默认参数很关键。很多新手写链表插入时总是忘了把新节点的next置空导致变成野指针。让构造函数强制完成这个初始化可以从源头堵住这个坑。2.2 成员变量选型top指针和count计数器缺一不可栈类只有两个成员变量Node* top_和size_t count_。top_负责指向栈顶节点这是整个栈的“门户”。入栈出栈都靠它。count_负责记录元素个数这个变量不是必须的——你完全可以通过遍历链表算size但那会变成O(n)。用空间换时间多一个计数器让size()变成O(1)这在刷题和工程里都很划算所以还是加上。命名上我用了带下划线的top_和count_这是Google C风格指南里的常见做法。成员变量加个后缀一眼就能跟局部变量区分开避免在代码里出现top top_这种让人精神分裂的写法。2.3 完整可编译代码先看整体再抠细节下面把整个类贴出来我建议你先通读一遍然后我们再逐段拆解关键操作。这段代码用C11标准就能编译模板化了数据类型存int、char、自定义对象都没问题。#include iostream #include stdexcept template typename T class LinkedStack { private: struct Node { T data; Node* next; Node(const T val, Node* nxt nullptr) : data(val), next(nxt) {} }; Node* top_; size_t count_; public: LinkedStack() : top_(nullptr), count_(0) {} ~LinkedStack() { clear(); } LinkedStack(const LinkedStack other) : top_(nullptr), count_(0) { Node** link top_; for (Node* p other.top_; p ! nullptr; p p-next) { *link new Node(p-data); link ((*link)-next); count_; } } LinkedStack operator(const LinkedStack other) { if (this ! other) { LinkedStack tmp(other); std::swap(top_, tmp.top_); std::swap(count_, tmp.count_); } return *this; } void push(const T val) { top_ new Node(val, top_); count_; } void pop() { if (empty()) { throw std::out_of_range(LinkedStack::pop(): stack is empty); } Node* tmp top_; top_ top_-next; delete tmp; --count_; } T top() { if (empty()) { throw std::out_of_range(LinkedStack::top(): stack is empty); } return top_-data; } const T top() const { if (empty()) { throw std::out_of_range(LinkedStack::top(): stack is empty); } return top_-data; } bool empty() const { return top_ nullptr; } size_t size() const { return count_; } void clear() { while (top_ ! nullptr) { Node* tmp top_; top_ top_-next; delete tmp; } count_ 0; } };如果你看到这里的Node** link和std::swap(top_, tmp.top_)有点发怵别慌下面两个小节专门把这两块骨头拆开嚼碎。3. 关键操作逐行拆解从push到析构成体系地理解3.1 push与pop头插法和头删法的核心逻辑先看入栈操作代码短得惊人void push(const T val) { top_ new Node(val, top_); count_; }这一行top_ new Node(val, top_)干了两件事先new Node(val, top_)申请一个新节点新节点的data是传入的值next指向当前栈顶然后把这个新节点变成栈顶。这是教科书级别的“头插法”。画一下内存图你就懂了。假设当前栈是top_ - [3] - [2] - [1] - nullptr现在push(4)。new出来的节点为[4]它的next指向[3]然后top_改为指向[4]结果就是top_ - [4] - [3] - [2] - [1] - nullptr。新元素永远站在最前面这正是栈“后进先出”的物理实现。出栈操作则是头删法的变形void pop() { if (empty()) { throw std::out_of_range(LinkedStack::pop(): stack is empty); } Node* tmp top_; top_ top_-next; delete tmp; --count_; }第一步把top_暂存到tmp防止待会指针丢了找不到要delete谁第二步top_跳到下一个节点第三步delete掉旧的栈顶节点。这三步顺序一个都不能乱——你要是先delete再移动top_就会访问已释放的内存未定义行为立刻出现段错误还是数据错乱就看运气了。pop这里有个设计选择空栈时到底该干什么你可以选择什么都不干直接return也可以抛出异常。我选择了抛std::out_of_range。原因很简单一个不吭声的pop会让程序在错误的路上越走越远而异常能把问题立刻暴露出来。刷题时你也许可以省掉这个判断但写工程代码时宁可抛异常也不能静默失败。3.2 top、empty与size细节里藏着const正确性这三个函数看着简单但“const正确性”是C新手最容易忽略的地方。T top() { if (empty()) { throw std::out_of_range(LinkedStack::top(): stack is empty); } return top_-data; } const T top() const { if (empty()) { throw std::out_of_range(LinkedStack::top(): stack is empty); } return top_-data; }top()函数有两个重载版本。非const版本返回T允许你修改栈顶元素const版本返回const T保证只读。这是C的标准姿势一个const对象调用的成员函数必须是const成员函数它得能确认自己不修改对象状态。你可能会问为什么要允许修改栈顶这不是破坏栈的封装性吗实际工程里这个需求很常见比如你需要查看当前栈顶的配置项想临时调整它再压回去。标准库的std::stack::top()就是返回引用的我们可以放心照抄标准库的设计。empty()和size()则简单直接bool empty() const { return top_ nullptr; } size_t size() const { return count_; }判断空本质上就是判断头指针是不是空。size()直接返回计数器不用遍历链表这就是我们当初维护count_的原因。两个成员函数都标了const因为它们只是查询状态不修改对象。这是const正确性的习惯能const就const让编译器帮你检查意外修改。3.3 拷贝构造指针的指针C/C链表必修课不写拷贝构造函数编译器会给你一个浅拷贝新栈的top_直接复制原栈的top_地址。结果就是两个栈指向同一串节点任何一个栈析构都会把这串节点delete掉另一个栈再析构就是double free程序直接崩溃。所以必须手写深拷贝。LinkedStack(const LinkedStack other) : top_(nullptr), count_(0) { Node** link top_; for (Node* p other.top_; p ! nullptr; p p-next) { *link new Node(p-data); link ((*link)-next); count_; } }看到Node** link别慌这个“指向指针的指针”是这个拷贝构造的核心技巧也是严蔚敏教材里C语言部分特别经典的一种链表构建方式。我们先把它当成一个普通的Node*指针看link复制了top_的地址即link现在指向“top_这个指针变量本身”。循环第一次执行时*link new Node(p-data)等价于“把新节点地址写到top_里”也就是让top_指向新节点然后link ((*link)-next)把link指向“新节点的next字段”也就是让link指向“下一个要写入指针的位置”。循环继续第二次执行时*link new Node(p-data)就等价于“把第二个新节点地址写到第一个新节点的next字段里”。如此反复一条与原栈顺序完全相同的新链表就被构建出来了。link像一支笔沿着新链表的next字段一个个往后写地址每写一个就把笔尖挪到刚写的next字段处等待写下一条。如果你觉得两个星号实在绕用辅助数组也能实现深拷贝先把原栈从top到底依次读进vector再反向push构建新栈。但指针的指针在C/C链表操作中是绕不过去的核心技能尤其是面试手写链表题时这种写法经常能让代码简洁一个量级我建议还是啃下来。3.4 赋值运算符与析构copy-swap与循环delete赋值运算符用的是“copy-and-swap”这个经典的强异常安全写法LinkedStack operator(const LinkedStack other) { if (this ! other) { LinkedStack tmp(other); std::swap(top_, tmp.top_); std::swap(count_, tmp.count_); } return *this; }思路是先用other拷贝构造一个临时对象tmp然后用swap把tmp的节点和count_跟自己交换。函数结束时tmp析构它手里拿着的刚好是原本属于this的旧节点被顺带释放了。这样即使拷贝过程中抛出异常this对象也能保持原样不会处于“半改半没改”的糟糕状态。这个写法值得你背下来。析构函数调用了clear()void clear() { while (top_ ! nullptr) { Node* tmp top_; top_ top_-next; delete tmp; } count_ 0; }循环里每一步都先把top_暂存再把top_往后挪然后delete暂存的节点。这里最忌讳的一行是delete top_; top_ top_-next;——delete之后top_已经指向已释放内存再去读top_-next就是访问悬垂指针。顺序必须是“先移动再删除”或者“先暂存再删除再移动”绝对不能“先删除再移动”。这套析构逻辑同样适用于clear()方法。clear()和析构的区别仅仅在于clear()执行完对象还活着所以要把count_重置为0析构之后对象就不存在了count_恢复不恢复都无所谓。4. 测试与验证别让代码在“看起来正常”里蒙混过关4.1 功能测试正常路径和异常路径都要覆盖写完之后得有一个能跑起来的测试程序。我建议的测试用例至少覆盖四类场景正常入栈出栈、空栈操作、深拷贝隔离性、大量元素的压力测试。int main() { LinkedStackint s; s.push(10); s.push(20); s.push(30); std::cout size: s.size() , top: s.top() std::endl; // 3, 30 s.pop(); s.pop(); s.pop(); std::cout empty: s.empty() std::endl; // 1 (true) try { s.pop(); } catch (const std::out_of_range e) { std::cout caught: e.what() std::endl; } for (int i 0; i 1000; i) { s.push(i); } std::cout size after push 1000: s.size() std::endl; LinkedStackint copy(s); s.pop(); std::cout original top: s.top() , copy top: copy.top() std::endl; return 0; }注意拷贝测试的核心判据修改原栈之后拷贝出来的栈不受影响。如果拷贝构造写成了浅拷贝这里大概率会double free或者输出乱七八糟的值。压力测试则用来验证大量push、pop之后没有明显的异常行为。4.2 内存检测用ASan和valgrind把内存错误逼出来链表栈的内存管理错误不像逻辑错误那样会立刻报错它可能跑几次正常、突然一次数据错乱。别靠肉眼调试要用工具。最方便的是GCC/Clang自带的AddressSanitizerASan。编译时加上-fsanitizeaddress运行程序时它会帮你检查越界访问、悬垂指针、double free、内存泄漏。g -stdc11 -g -fsanitizeaddress -fno-omit-frame-pointer main.cpp -o main ./main如果内存操作有问题程序会直接报出出错位置和调用栈。另一个工具是valgrind适合在Linux环境下做更全面的内存泄漏检查valgrind --leak-checkfull ./mainvalgrind跑完会给出“definitely lost”“indirectly lost”这些泄漏报告。正常情况应该是“All heap blocks were freed -- no leaks are possible”。我在实际教学中发现很多同学链表栈“看起来能跑”但valgrind一查全是泄漏——几乎都是pop忘记delete、clear循环写错、或者析构函数空着没实现导致的。所以这两个工具强烈建议你写链表代码时养成习惯。4.3 和数组栈对比的实测感受链表栈和数组栈在功能上等价但实际运行表现有明显差异。我用同样的100万次push/pop分别跑过两种实现链表栈占用内存比数组栈多了每一节点的8字节指针开销同时new/delete的调用产生了更多时间消耗。但反过来数组栈为了性能会预留容量比如初始容量16push到17时扩容到32这中间有一次性拷贝开销。如果你的业务场景是“元素总量波动很大、峰值不确定”链表栈的内存使用更贴合实际负载如果你的场景是“元素量稳定、频繁访问栈顶”数组栈的缓存局部性更好运行更快。这也就是为什么C标准库的std::stack默认用std::deque做底层容器而不是链表——deque在缓存局部性和扩容成本之间取了折中。工程选择永远没有银弹只有最合适的取舍。5. 常见问题与排查技巧实录这些坑我替你踩过了5.1 段错误的常见根源链表栈的段错误八成都出在这几个地方构造时忘记初始化top_。成员变量不初始化就是随机值push的时候new出的节点next指向一个野地址一旦访问就崩溃。解决办法是构造函数的初始化列表里必须写top_(nullptr)。pop或top里忘记判空。空栈上执行top_-next等价于从nullptr读取必然段错误。解决办法是操作前调用empty()检查。delete之后继续用指针。在delete之后还企图通过旧指针访问节点的next悬垂指针症状时好时坏。解决办法是delete之前先把next保存下来或者干脆先移动top_再delete。排查这类问题时先用-g编译并用gdb调试看崩溃时程序停在哪一行。一百个段错误里九十九个都能靠“看栈回退的那一行代码”定位。5.2 内存泄漏链表栈最隐蔽的敌人内存泄漏不会让你程序当场崩溃但会让程序内存占用持续上涨跑久了变卡甚至被系统杀掉。常见原因pop只移动top_不delete节点变成孤儿。clear写成了只把top_置空节点链全部泄漏。忘记写析构函数或者析构函数是空的。忘记写拷贝构造函数浅拷贝之后两个栈析构会double free这时候ASan会明确告诉你“attempting double-free”。每new一个节点就得有对应的一个delete兜底。用ASan的-fsanitizeaddress检测它会精确报告是哪一行new的内存没有释放。把这个理念当成习惯你写任何涉及动态内存的代码都会稳很多。5.3 为什么你写push总想用尾插法我见过不少同学用链表写栈时条件反射地写成了尾插法遍历到链表尾部把新节点接上去出栈也去找尾节点。功能上似乎也能实现但push和pop都变成了O(n)。搜链表题时你被训练要“找到尾节点”但栈的需求完全不同——栈操作永远在头部根本不需要遍历。记住一个判断一个数据结构需要频繁在哪个位置操作链表就把哪个位置当作头节点。这个思路推而广之还能解决队列用链表实现时“头删尾插”的设计问题本质上是同一道题。5.4 用一个排查速查表收个尾症状最可能原因排查手段空栈操作就崩溃未判空直接访问top_检查pop、top是否先调empty()数据一多就崩溃忘记初始化top_或next检查构造函数和Node构造函数内存越用越多pop/clear未delete节点valgrind --leak-checkfull析构时double free浅拷贝导致两个栈共享节点补全拷贝构造和拷贝赋值push之后栈内顺序反了push误用尾插法画图确认新节点应指向旧top_程序时好时坏delete后继续使用指针ASan逐行定位最后再分享一个实用习惯代码写完之后我强烈建议你手动画一遍内存图在纸上画出几个节点、把top_指来指去的每一步都画出来。尤其是在push和pop两个操作上把每一步谁指向谁、谁被delete、谁成了新top都标清楚。数据结构这行眼过千遍不如手过一遍。你亲手画过一遍栈的内存变化之后再看队列、二叉树、图的指针操作都会有“原来如此”的通透感。我这个习惯是当年啃严蔚敏教材时养成的直到现在写底层代码遇到指针绕不清楚还是会老老实实画图。栈的链表实现只是一个开始把这里面的指针思维和内存管理基本功练扎实了后面学什么数据结构都顺。
