1. 先从一个面试场景说起你要的到底是栈还是数组有次组里招人候选人简历写得很漂亮我照惯例问了句请实现一个栈。对方唰唰唰写了二十行代码用数组模拟了push、pop、top然后抬头看我眼神里带着就这的意味。我追问了一句那你觉得你实现的是栈还是一个用栈接口包装起来的数组他愣了一下。这个场景几乎每年都会重演。很多写了好几年C的人能把栈的代码背得滚瓜烂熟但被问栈作为抽象数据类型ADT到底是什么的时候反而说不清楚。这不是什么咬文嚼字的学院派问题——你理解了ADT才会明白为什么接口和实现要分离为什么换一种底层存储方式不影响调用方代码为什么标准库里std::stack只是一个容器适配器而不是一个容器。这些认知直接决定你写出来的东西是能跑的代码还是能维护的代码。这篇文章我想把ADT的概念和栈这个经典例子彻底揉碎了讲清楚同时给出一份可以直接抄走的C实现。无论你是刚学数据结构的学生还是写了好几年业务代码想补补基本功都应该能从里面找到点东西。2. 从数学定义到代码契约ADT到底抽象了什么2.1 ADT的三层结构数据、操作、约束抽象数据类型这个词很多人把它理解成一个类或者一个接口其实都不够准确。一个ADT由三部分组成数据对象一组值的集合比如整数集合或者元素序列。操作集合对这个数据对象能施加的合法操作比如栈的push、pop、top、isEmpty。公理与约束操作之间必须满足的逻辑关系比如先push再pop得到的还是原来那个元素。第三部分最容易被忽略但它才是ADT的灵魂。举个生活中的例子自动售货机是一个ADT你投币、按键、取货这是操作但如果你投了五块钱按了三块钱的饮料机器吐出一罐五块钱的可乐还找你两块钱零钱这就违反了约束。约束保证了操作的组合有意义。放在代码里约束就是不变式invariant。一个栈实现无论底层用什么存储都必须保证后进先出这个次序语义。任何破坏这个语义的优化都是错的。2.2 接口即契约为什么调用方不该关心底层ADT的核心价值在于信息隐藏。调用方只需要知道栈支持push、pop、top、isEmpty这几种操作且遵守后进先出规则完全不需要知道内部是数组还是链表也不需要知道内存是怎么分配的。这个抽象带来的直接好处是你可以自由地更换底层实现而不影响调用方。测试环境里想用一个能快速清空的栈换成vector版本。生产环境里栈的最大深度不确定怕数组扩容有开销换成链式版本。调用方的代码一行都不用改因为你只依赖契约不依赖实现。我之前维护过一个旧的C风格代码库里面到处是int stack[1024]这种裸数组配合一个int sp指针管理栈顶。一旦要改栈的容量得把所有相关文件翻一遍因为每处都直接操作了栈的内部结构。后来我重构出一个Stack接口底层的数组也好、链表也好全部封装进去调用方统一走接口容量问题变成了一个内部实现问题。这就是ADT工程价值的真实体现。2.3 栈的ADT定义先写契约再写代码写栈之前先把契约定清楚。一个最小可用栈应该包含push(x)将x压入栈顶。如果栈已满限容实现下抛异常。pop()移除栈顶元素。如果栈为空行为未定义实现上应该抛异常。top()返回栈顶元素但不移除。如果栈为空抛异常。isEmpty()返回栈是否为空。size()返回栈内元素个数方便调用方做容量判断。这里有一个设计细节值得多说一句pop应该返回值还是void很多教科书喜欢写int pop()直接把栈顶元素弹出来并返回。但工程上更推荐void pop()配T top()分离的形式。原因有二一是如果返回值和移除动作绑在一起万一返回值的拷贝过程抛异常元素已经被移除了数据就丢了二是top和pop分离后语义更清晰也更容易做到强异常安全。下面实现里我会按这个风格来写。3. 栈的两种经典实现数组版与链式版3.1 数组版实现教科书里最常见的样子先看最简单的数组版本。核心思路是拿一个固定长度数组存元素用一个整数记录栈顶下标。#include stdexcept template typename T, std::size_t Capacity class FixedStack { public: void push(const T value) { if (topIndex_ Capacity) { throw std::overflow_error(stack overflow); } data_[topIndex_] value; } void pop() { if (topIndex_ 0) { throw std::underflow_error(stack underflow); } --topIndex_; } T top() { if (topIndex_ 0) { throw std::logic_error(stack is empty, no top element); } return data_[topIndex_ - 1]; } const T top() const { return const_castFixedStackT, Capacity(*this).top(); } bool isEmpty() const { return topIndex_ 0; } std::size_t size() const { return topIndex_; } private: T data_[Capacity]; std::size_t topIndex_ 0; };几个容易写错的地方我逐一说明。第一top()返回的是data_[topIndex_ - 1]不是data_[topIndex_]。原因在于我的topIndex_语义是下一个可写入的位置而不是当前栈顶的位置。把下标语义定清楚整个代码的思路就顺了。如果你反过来定义topIndex_指向栈顶元素那push得先topIndex_再赋值而pop得直接--topIndex_。没有谁对谁错但要前后一致。第二这个版本用了模板参数Capacity作为编译期容量好处是不涉及堆分配性能最好坏处是容量写死在类型里FixedStackint, 1024和FixedStackint, 1025是两个完全不同的类型无法互相赋值。这也就是为什么标准库里的std::stack是基于std::deque动态扩容的。第三top() const版本我用了const_cast复用非const版本的实现。这个小技巧可以避免两份几乎相同的代码。不过要注意你的非const版本必须确实不修改内部状态这个const_cast才是安全的。3.2 链式版实现动态生长的更灵活方案数组版的硬伤是容量固定。如果事先不知道数据量链式版就更有优势。每个节点单独分配内存不需要预留空间。#include stdexcept #include utility template typename T class LinkedStack { struct Node { T value; Node* next; explicit Node(T v, Node* n nullptr) : value(std::move(v)), next(n) {} }; public: LinkedStack() default; ~LinkedStack() { clear(); } LinkedStack(const LinkedStack other) { copyFrom(other); } LinkedStack operator(const LinkedStack other) { if (this ! other) { clear(); copyFrom(other); } return *this; } LinkedStack(LinkedStack other) noexcept : head_(other.head_), size_(other.size_) { other.head_ nullptr; other.size_ 0; } LinkedStack operator(LinkedStack other) noexcept { if (this ! other) { clear(); head_ other.head_; size_ other.size_; other.head_ nullptr; other.size_ 0; } return *this; } void push(const T value) { head_ new Node(value, head_); size_; } void pop() { if (empty()) { throw std::underflow_error(pop on empty stack); } Node* victim head_; head_ head_-next; delete victim; --size_; } T top() { if (empty()) { throw std::logic_error(top on empty stack); } return head_-value; } void clear() { while (head_) { Node* victim head_; head_ head_-next; delete victim; } size_ 0; } bool empty() const { return size_ 0; } std::size_t size() const { return size_; } private: Node* head_ nullptr; std::size_t size_ 0; void copyFrom(const LinkedStack other) { head_ nullptr; size_ 0; Node** tailPtr head_; Node* cur other.head_; while (cur) { *tailPtr new Node(cur-value); tailPtr ((*tailPtr)-next); cur cur-next; } size_ other.size_; } };这个版本比数组版复杂得多主要多出来的复杂度来自资源管理和拷贝语义。链表每个节点都是new出来的必须自己负责释放于是就得写析构函数而一旦写了析构函数编译器就会拒绝给你生成拷贝构造和拷贝赋值你得自己补齐。copyFrom函数里那个二级指针Node** tailPtr是链表复制的经典写法一开始指向head_之后不断指向最后一个节点的next这样从头到尾一遍遍历就能建立整条链不需要额外记一个tail指针还得考虑空链表的特殊情况。3.3 两种方案的取舍没有银弹只有语境数组版和链式版的对比网上已经写烂了但很多对比都停留在数组访问快、链表插入灵活这种教科书层面。我说点实战层面的体会。数组版真正的优势不在快而在缓存局部性。栈顶附近的元素在内存中是连续分布的CPU从缓存里就能取出这对高频push/pop的场景影响非常明显。链式版的每个节点分散在堆上访问下一个节点大概率要重新去内存里捞cache miss的成本在这种小而短的操作里会被放大。链式版的真正优势也不在插入灵活——栈只在栈顶操作数组版尾插本来就不慢——而在于容量动态且无需整体搬移。链表天然按需分配每个节点独立存在不需要扩容后整体拷贝这个动作。所以我的建议很简单如果你知道数据量的上界或者能接受一个合理的预留大小选数组版。工程上90%以上的栈场景其实是限容的。如果数据量没有上界且你不想操心扩容策略选链式版。付出的代价是单次操作多一次堆分配以及更差的缓存行为。如果你用的是标准库std::stack默认基于std::deque它两边都能拿一点好处是最省心的选择。4. C特有的坑模板、RAII与异常安全4.1 什么时候应该写模板先等一等再动手很多教程一上来就写templatetypename T以至于新手以为栈必须写成模板。实际上是否需要模板取决于你的使用场景。如果你只是给某种具体类型做一个栈写非模板类完全没问题代码更简短理解成本更低。如果你需要栈容纳多种类型或者想在项目里复用模板才是正确选择。不过用模板意味着你写的每一行代码都要经受住所有可能类型的考验。比如上面的FixedStack里T data_[Capacity]这句对于不可默认构造的类型这种写法直接编译失败。你的栈得支持哪些类型的元素这决定了你的实现边界。我建议初学者先写一个int版本的栈把逻辑跑通再升级成模板。不要一开始就模板加链表加智能指针一起上那样出了问题你根本分不清是哪个环节的bug。4.2 为什么不用裸指针RAII让你少写一半代码链式版里我用了裸指针加手动new/delete这一方面是为了把底层原理讲清楚另一方面古典数据结构教材都是这么写的。但实际工程里我强烈建议用std::unique_ptr管理节点RAII会让代码安全性和可读性都上一个台阶。template typename T class LinkedStackRAII { struct Node { T value; std::unique_ptrNode next; }; std::unique_ptrNode head_; std::size_t size_ 0; public: void push(const T value) { auto newHead std::make_uniqueNode(); newHead-value value; newHead-next std::move(head_); head_ std::move(newHead); size_; } void pop() { if (empty()) { throw std::underflow_error(pop on empty stack); } head_ std::move(head_-next); --size_; } // 析构函数、拷贝构造等由默认规则生成 // 但注意因为unique_ptr不可拷贝拷贝构造需要手动实现 };对比之下pop从手动delete节点变成了一行head_ std::move(head_-next)。unique_ptr的析构会自动释放被移动走的旧头节点内存泄漏的窗口直接被语言机制堵死了。项目里能用RAII的地方我不会用裸指针因为裸指针带来的不是更底层而是更容易漏。4.3 异常安全三级别你的栈是弱安全还是强安全写栈这类容器异常安全是个绕不开的话题。业界把异常安全分成三个级别基本保证操作抛出异常后对象处于合法但不确定的状态不过没有资源泄漏所有不变式仍然成立。强保证操作抛出异常后对象保持原来的状态就像操作根本没发生过。不抛异常操作保证不抛出异常通常用于析构和移动操作。对栈来说最关键的是pop和push的配合。前面我提过为什么pop不返回值就是出于强保证的考虑如果pop既移除元素又返回它返回值的拷贝构造抛异常时元素已经被移除了栈处于一个元素丢了但状态合法的中间态这连基本保证都有点勉强。我写的void pop()加T top()这种分离式设计天然容易做到强保证top()只查不改不抛异常前提是元素类型不会因访问而抛异常pop()只是释放节点或减少下标也不涉及元素拷贝。真正可能在push里抛异常的是元素的拷贝构造和栈扩容时的内存分配这可以通过先构造新状态成功后再替换旧状态来做成强保证。4.4 移动语义让栈的拷贝成本降下来写模板栈时移动语义是必须考虑的。假如你写了一个FixedStackstd::string往里面push一个局部std::string变量如果只有push(const T)这一版那么每一次入栈都是一次深拷贝。加上push(T)右值引用版本并配合std::move就能把临时字符串的堆缓冲区直接移交出去省掉一次拷贝。void push(const T value) { data_[topIndex_] value; } void push(T value) { data_[topIndex_] std::move(value); }这里有一个细节std::move(value)之后value处于被移动状态理论上不应该再访问它。好在入栈操作本来就是最后使用它的一次移动完正好不再需要所以这个用法是安全的。如果你在push之后还用了value那就要小心了被移动后的对象只保证可析构、可重新赋值。5. 测试边界条件为什么卡壳的永远是简单问题5.1 一个看似很稳的栈真的经得起这七问吗我曾经拿下面这组问题去考实习生笔试全对上机一跑就露馅。你拿到任何一个栈实现先问它七个问题对空的栈调用top()会发生什么对空的栈调用pop()会发生什么连续pop到空后再push还能正常工作吗栈满的时候push是静默失败、覆盖旧数据、还是明确报错栈里只有一个元素push再pop一次top()返回的是什么拷贝一个栈之后修改原栈副本会不会受影响元素类型是std::string时重复push/pop一万次会不会飘内存第一问和第二问是检查你是否处理了underflow。很多初版代码直接访问data_[topIndex_ - 1]栈为空时topIndex_为0访问data_[-1]行为未定义。这属于不崩溃是因为运气好的代码。第三问和第四问是检查下标语义能否在极限状态下自洽。栈满时push我选择抛std::overflow_error。有人可能觉得满了就覆盖最老的元素更实用比如做环形缓冲时确实有这种需求但那就不叫栈了那是另一个ADT。ADT的约束不允许你换个场景就改语义。第五问看起来简单其实最考基本功。出问题的往往不是一个元素时push/pop的逻辑而是你在pop里把topIndex_减成了负数。我见过不止一个同学在pop时写--topIndex_但栈空时topIndex_已经是0一减变成SIZE_MAX这种巨量无符号数之后push直接崩溃。所以pop里的空栈检查绝不能省。5.2 写个临时测试用例集比调试器好使我写栈这种基础结构时不会直接跑到项目里调试而是先写一个临时测试文件把上面七个问题逐个验证。#include cassert #include string using TestStack LinkedStackRAIIint; void testBasics() { TestStack s; assert(s.empty()); assert(s.size() 0); s.push(10); s.push(20); s.push(30); assert(s.size() 3); assert(s.top() 30); s.pop(); assert(s.top() 20); s.pop(); assert(s.top() 10); s.pop(); assert(s.empty()); } void testUnderflowThrows() { TestStack s; bool caught false; try { s.pop(); } catch (const std::underflow_error) { caught true; } assert(caught); caught false; try { s.top(); } catch (const std::logic_error) { caught true; } assert(caught); } void testAfterEmptyStillWorks() { TestStack s; s.push(1); s.pop(); s.push(2); assert(s.top() 2); } void testStringPush() { LinkedStackRAIIstd::string s; s.push(std::string(hello)); s.push(world); s.pop(); assert(s.top() hello); } int main() { testBasics(); testUnderflowThrows(); testAfterEmptyStillWorks(); testStringPush(); return 0; }assert在Release模式下会被编译器优化掉所以这只是一个开发阶段的自测脚本。真要严谨应该上测试框架或者写独立测试程序。但对一个教学级别的栈实现来说这个临时测试已经能挡住绝大多数低级错误。5.3 一个真实踩坑记录拷贝构造里的深拷贝没有做有次重构链式栈我给LinkedStack加拷贝构造时偷懒写成了浅拷贝版本新栈的head_直接指向旧栈的head_。当时想着反正这个栈只在单线程里用没人会拷贝结果隔了一周线上业务报了一个极其诡异的bug——某个模块的栈数据在没有任何push/pop操作的前提下自己变了。排查了一下午最后定位到是某个中间层把栈作为参数传给了另一个函数函数内部拷贝了一份两个栈共享了同一组节点。函数里对副本的push/pop操作全部作用到了原栈上。这就是浅拷贝的威力它不是写错了它是在你最没防备的地方炸了。那之后我的规矩是涉及动态资源的类要么明确禁用拷贝 delete要么老老实实写深拷贝。用shared_ptr做伪深拷贝也不是不行但一定要想清楚节点共享的后果。很多真实bug追溯到底都是以为自己在操作副本其实在操作同一份数据。6. 从课堂到生产栈能解决哪些实际问题6.1 括号匹配最简单的栈应用也是最好的教学案例给定一个只包含(,),{,},[,]的字符串判断括号是否配平。这个问题的标准解法就是扫描一遍遇到左括号压栈遇到右括号看栈顶是否匹配。#include string #include unordered_map bool isBalanced(const std::string expr) { std::stackchar st; for (char c : expr) { if (c ( || c { || c [) { st.push(c); } else { if (st.empty()) return false; char open st.top(); if ((open ( c )) || (open { c }) || (open [ c ])) { st.pop(); } else { return false; } } } return st.empty(); }这个例子把栈的后进先出语义映射得非常直观后出现的左括号必须被先匹配掉这恰好对应了嵌套结构的关闭顺序。千万别小看这个例子编译器做语法分析、IDE自动补全括号、代码格式化工具判断缩进底层都有类似逻辑。6.2 逆波兰表达式求值不用括号也能表达优先级后缀表达式逆波兰表达式求值是栈的另一个经典应用。3 4 5 *表示(3 4) * 5。求值逻辑是遇到数字压栈遇到运算符弹出两个操作数计算结果压回栈。int evalRPN(const std::vectorstd::string tokens) { std::stackint st; for (const auto tok : tokens) { if (tok || tok - || tok * || tok /) { int rhs st.top(); st.pop(); int lhs st.top(); st.pop(); if (tok ) st.push(lhs rhs); if (tok -) st.push(lhs - rhs); if (tok *) st.push(lhs * rhs); if (tok /) st.push(lhs / rhs); } else { st.push(std::stoi(tok)); } } return st.top(); }注意这里弹出顺序的坑栈顶是右操作数所以先弹出来的是rhs后弹出来的是lhs。减法和除法对顺序敏感写成st.top()直接拿到的就是右操作数最容易出错的点就在这里。为什么后缀表达式不用括号因为运算符和操作数的顺序已经隐含了优先级信息而这正是靠栈这个结构天然支持的。6.3 函数调用的物理本质你的程序本身就是一座栈严格说函数调用栈call stack和数据结构教材里的栈并不完全是一回事——前者是运行时环境管理的执行上下文后者是程序员显式操作的数据结构。但它们共享后进先出这个核心思想而且理解前者会加深对后者的理解。每次函数调用系统会把返回地址、参数、局部变量压进调用栈函数返回时这些信息被弹出。递归函数之所以需要用栈就是因为嵌套调用必须后来的先结束这和后进先出完全一致。有时候我会用显式栈代替递归目的不是炫技而是规避递归深度限制。在篇幅受限的递归场景里比如深度可能达到数万层的树的遍历系统调用栈会溢出而用堆上的std::stack自己模拟深度只受内存限制。这种递归转迭代的手段本质上是把隐式的调用栈换成了显式的数据结构。6.4 编辑器撤销功能为什么撤销总是最近一次优先CtrlZ这个功能背后就是一个栈。每次修改文档把反操作压栈每次撤销弹出一个反操作并执行。因为用户最想撤销的是最近的一次操作而这个恰好是栈顶元素。这个模式在业务系统里也能用。之前我做一个审核流程系统审核状态的变更就需要撤销回上一个有效状态我当时用的就是这个思路每次状态变更把如何回滚这次变更的闭包压栈。用户点了撤销从栈里取出最近一次的回滚闭包执行。这个设计的妙处在于回滚栈的push和pop逻辑完全对称而且天然按时间倒序执行不需要额外排序。从这个角度看栈不是数据结构课上的古董它是后做的事要先回滚这类需求的天然模型。6.5 推荐练习路径手写一遍胜过看十篇如果你想把今天这篇的内容消化掉我建议按这个顺序练习手写一个int版本的数组栈写下下标语义画出push/pop过程中数据和下标的每一步变化。把它升级成模板版本加入const版本和非const版本的top()。手写一个链式栈先不管拷贝构造跑通基本功能。给链式栈补上析构函数和深拷贝用上面的七个测试问题验证。最后把链式栈换成unique_ptr节点版本对比两步之间代码量的变化。用你的栈去解决括号匹配和RPN求值两个问题感受基于契约的组件如何被自由组合。每一步都不长关键是自己动手把思路走一遍。数据结构这东西看得懂和写得出来之间隔着一整条调试的路。7. 写在最后抽象能力才是真正值钱的这篇从ADT的概念一路聊到栈的两种实现、C的资源管理和异常安全再到实际应用场景信息量不小。但如果你只记住一件事我希望是写栈的时候脑子里先有契约再谈实现。调用方只依赖push、pop、top这些操作和后进先出这个规则至于底层是数组还是链表是裸指针还是智能指针都不该影响调用方。这套接口与实现分离的思路适用范围远不止栈这一种数据结构。队列、树、图、哈希表乃至你业务代码里那些什么模块对外暴露什么能力的设计底层逻辑都是同一个定义清楚契约隐藏实现细节。C里那么多特性——抽象类、模板、RAII、移动语义——归根结底都是在帮你把这个抽象做得更干净、更安全。最后分享一个我个人的小习惯每当我要写一个新的数据结构或者设计一个新的模块接口我会先在注释里写清楚这个类承诺什么、不承诺什么——比如本栈保证后进先出pop空栈抛异常不保证线程安全。这份承诺就是ADT里的公理和约束。写清楚之后实现过程中遇到的每个选择都会变得异常清晰。这算是写代码这么多年最值钱的一个习惯。