LeetCode 第 20 题“有效的括号”是我带新手刷栈时几乎必讲的一道题。题面短、规则直白大部分第一次做的人都能秒懂“用栈就能解”可一旦把条件改成“不使用 STL 库自己写一个自定义 stack”很多同学的代码就开始出各种稀奇古怪的问题。这篇文章就用 C 完整走一遍这条手写栈路线从数据结构怎么设计到括号匹配的每一行代码为什么要这么写再到边界用例和调试经验。这篇文章不只适合准备笔试面试的读者也适合那些刚学完 C 基本语法、想开始刷题但还没搞懂“栈顶指针到底是怎么动的人”。我打算彻底抛开std::stack自己从零实现一个能用的栈然后把这道经典题解掉。这样你以后再看 STL 里的栈容器脑子里浮现的就不仅仅是接口而是data[topIndex]、data[topIndex]这些真实动作。1. 为什么这道题被当成“栈的入门教科书”这道题的难度不高但它把“栈到底解决什么问题”展示得非常干净。1.1 三句话理解题目规则题目要求其实可以压缩成三条每个左括号都必须有一个同类型的右括号来接它(只能配)[只能配]{只能配}。右括号必须按“最近的未闭合左括号”出现顺序来匹配()没问题(]有问题。最终所有括号都必须闭合不能有孤零零的左括号也不能有多出来的右括号。注意“按正确顺序闭合”这句是整道题的核心。对([])处理完(和[之后看到的第一个右括号是]它要去闭合最近出现的[而不是最开头的(。这种“后出现的先被匹配”的顺序学名叫后进先出也就是 LIFO。栈的天然属性和这个需求完全吻合。很多人第一眼看到题目就能猜到用栈但只有当你亲手验证过([)]这种反例之后才会真正理解为什么非栈不可。1.2 为什么计数器和数组都搞不定这个问题经常有人问我能不能分别数三种括号的数量比如([)]左括号有两个右括号也有两个数量刚好对上。如果只数数量这道题会错误地把它判成有效。问题在于数量无法表达“谁与谁配对”的顺序信息。数组行不行也不行。数组或者队列通常是按先进先出的顺序去匹配会让最外层的(先被考虑而在([)]中真正应该先处理的是内层的[。你需要的永远只是“最近那个还没闭合的左括号”这个信息如果在数组里你得自己记住“最近”的位置本质上就是模拟栈顶指针。既然绕不开指针不如直接用栈。用一句话说这里需要的数据结构必须支持“只操作尾部、后进先出”栈是这个需求最直接的实现。这也是为什么题目本身就是“为什么需要栈”的最佳案例。实际写代码时你还会发现一个有趣的细节栈不仅能判断括号类型是否匹配还能顺带记录括号出现的顺序这两个信息加在一起就是把这道题做对的全部条件。1.3 解法的大框架遇到左括号入栈遇到右括号弹栈标准思路一句话就能讲完从左往右扫描字符串见到左括号就压入栈见到右括号就从栈顶弹出一个左括号检查这两个括号是否属于同一类型。如果类型不匹配或者该弹的时候栈已经是空的直接判定无效。扫描结束后如果栈不为空说明还有没闭合的左括号也无效。这个框架会根据实现细节分成两个流派。一个是“压入左括号弹出后再比对”另一个是“遇到左括号就把对应的右括号压进去遇到右括号直接和栈顶比”。这两种写法我后面都会给代码目前先记住大方向。我自己在实际教学里发现很多人卡住不是因为不知道用栈而是不清楚“弹出来的东西到底和谁比”这反而是次要问题真正的重点在于栈要一直保存“还没闭合的左括号集合”并且只允许从最近的位置取出来。2. 自己写一个栈三个变量、两个约定、一堆细节手写一个栈并不是什么高深的事但有几个约定如果在动笔前不定清楚写出来的代码会非常别扭。2.1 为什么要专门强调“不使用 STL 库”有人会觉得std::stack一行就能声明何必要自找麻烦真实场景里至少有三种理由。第一个是面试。面试官让你做算法题用stackchar虽然不算错但如果你能在很短时间内写一个基于数组的栈这通常会被视为对数据结构有更扎实的理解。第二个是底层开发。在嵌入式环境里标准库可能被裁剪或者内存管理策略要求你严格控制分配时机这时容器类不一定可用。第三个是学习本身。手写一遍栈之后push、pop、top、empty这些接口背后的指针移动你会记得非常牢。以后再碰到任何用到栈的题目你的直觉会比只会调用容器的人准得多。LeetCode 这类题目的字符串长度通常不会特别夸张自写一个栈来解完全不会拖慢提交速度。代码量也就是二十到三十行成本并不高。2.2 用原生数组模拟栈最核心的三个变量一个最简单的栈只需要三个变量char* data存实际元素的数组首地址。int capacity当前数组能存多少个元素。int topIndex栈顶元素的下标。栈为空时怎么表示我习惯把topIndex初始化为-1。这个约定非常自然-1表示“没有任何元素”第一个元素入栈后下标变成 0。如果从 0 初始化就得约定“topIndex 指向下一个空位”那push和pop的逻辑会相反写起来容易混。push的操作是data[topIndex] cpop只需要--topIndextop()返回data[topIndex]empty()判断topIndex -1。就这四件事没有别的魔法。至于为什么用数组而不是链表这里只访问末尾元素数组连续内存、缓存友好扩容只是偶尔发生整体性能更好。链表得为每个节点维护 next 指针除了显得复杂刷题场景下没有任何优势。2.3 完整的手写栈类代码下面这段代码是我在实际练习中用的栈类基于动态数组容量不够时翻倍扩容class MyStack { private: char* data; int capacity; int topIndex; void resize() { int newCapacity capacity * 2; char* newData new char[newCapacity]; for (int i 0; i topIndex; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCapacity; } public: MyStack() : capacity(8), topIndex(-1) { data new char[capacity]; } ~MyStack() { delete[] data; } MyStack(const MyStack) delete; MyStack operator(const MyStack) delete; void push(char c) { if (topIndex 1 capacity) { resize(); } data[topIndex] c; } void pop() { if (topIndex 0) { --topIndex; } } char top() const { return data[topIndex]; } bool empty() const { return topIndex -1; } };有几个 C 细节需要单独说清楚。第一new[]必须配delete[]不能写delete data。这道题里如果忘了释放内存提交可能也能过因为评测程序不会一直盯着你的进程看但真放到长期运行的程序里这就是内存泄漏。第二我显式禁用了拷贝构造和拷贝赋值。这个类持有裸指针data如果允许浅拷贝两个对象会指向同一块内存析构时可能出现双重释放。在 Solution 里我们只在局部创建栈对象不会拷贝它但作为完整类定义加上这两行删除声明是负责任的做法。第三top()在空栈时访问data[-1]是未定义行为。所以使用这个类的人必须保证先判空再取栈顶。这个保证我会在题解算法里反复体现。如果你想把这个类用到更复杂的场景可以在top()内部加个断言或者抛异常不过竞赛和刷题场景一般没必要增加这个负担。2.4 刷题版的轻量写法直接在函数里维护一个数组栈如果你觉得封装一个类太隆重只想快速提交可以直接在isValid函数内部用一个原生数组当栈。字符串长度为 n 时最坏情况所有字符都是左括号栈内最多 n 个元素所以开长度为n 1的数组就够class Solution { public: bool isValid(string s) { if (s.size() % 2 1) { return false; } char* st new char[s.size() 1]; int top -1; bool ok true; for (char ch : s) { if (ch ( || ch [ || ch {) { st[top] ch; } else { if (top 0) { ok false; break; } char topChar st[top--]; if ((ch ) topChar ! () || (ch ] topChar ! [) || (ch } topChar ! {)) { ok false; break; } } } if (ok top ! -1) { ok false; } delete[] st; return ok; } };这个版本里我特意把所有提前退出都改成“先置 false 再 break最后统一释放内存”避免函数中途直接 return 导致忘记delete[]。这种写法虽然看着有点啰嗦但手动管理内存时是非常好的习惯。new char[s.size() 1]里的 1不是为了多存一个字符而是为了处理空串时s.size() 0的情况。虽然标准允许new char[0]但这类边角行为最好不要依赖。栈从 -1 开始push 时先top所以闭区间[0, top]里的元素都是有效的。3. 正式题解完整代码与每一行背后的原因现在把自定义的MyStack和算法结合起来给出完整的解题代码。3.1 首选写法压入对应的右括号匹配时直接比较我推荐的主版本是这个。它配合前面手写的MyStack使用class Solution { public: bool isValid(string s) { if (s.size() % 2 1) { return false; } MyStack st; for (char ch : s) { if (ch () { st.push()); } else if (ch [) { st.push(]); } else if (ch {) { st.push(}); } else { if (st.empty() || st.top() ! ch) { return false; } st.pop(); } } return st.empty(); } };逻辑非常直白遇到左括号就把“将来必须出现的右括号”压入栈遇到右括号只要栈顶的字符和它相同就说明匹配成功弹出即可。如果栈空或者栈顶不是这个右括号直接失败。为什么推荐这种写法因为“期望值”被提前压进了栈里后面每一轮匹配就只是一个字符等值比较不需要再写三组if去判断(对)、[对]、{对}。代码更短逻辑也更不容易漏配对。处理到右括号时st.empty() || st.top() ! ch这个条件用了 C 的短路求值先检查栈是否为空如果为空就直接返回 false后面的st.top()根本不会执行所以不存在空栈取 top 的未定义行为。这是写这类逻辑非常舒服的一个点。扫描完成后return st.empty()决定最终结果。如果所有括号都正确配对栈应该是空的只要栈里还有残留就说明有左括号一直没等来它的右括号。3.2 另一种写法栈里存左括号弹出后再比对如果你更习惯“栈里存左括号”的直觉代码长这样class Solution { public: bool isValid(string s) { if (s.size() % 2 1) { return false; } MyStack st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else { if (st.empty()) { return false; } char topChar st.top(); if ((ch ) topChar ! () || (ch ] topChar ! [) || (ch } topChar ! {)) { return false; } st.pop(); } } return st.empty(); } };两版代码都能通过这道题区别只在风格。第二版的优点是“栈里存的就是原字符串中的左括号”符合直觉缺点是要写三组条件判断。第一版的优点是省掉了条件判断缺点是初学者会疑惑“为什么压进去的是右括号”。我个人的建议是两个版本都写一遍然后想想它们为什么等价。无论栈里存的是左括号还是对应的右括号栈的核心作用都相同保存“还没有闭合的括号的匹配顺序”。理解到这个层面这道题才算真正掌握。3.3 几个容易悄悄丢掉分数的细节这些细节看起来很小但在实际写代码时非常容易踩。第一匹配成功后忘记pop()。很多人写完st.top()和ch的比较后就直接进入下一轮循环栈越堆越高最后返回 false或者在某些巧合下错误地返回 true。弹栈不是可选项它是“该括号已闭合”的标志。你可以把弹栈想象成把一叠盘子最上面那个拿走不拿走的话下一个盘子永远无法被访问到。第二不判空直接top()。空栈调top()会读到非法内存在本地可能返回一个垃圾字符如果你恰好拿它和一个右括号比较结果不可预期。所以每次取栈顶前都要保证栈非空或者用短路写法保证访问顺序。第三奇数长度剪枝。有效括号串一定是偶数长度所以s.size() % 2 1时直接返回 false 是安全的。这个剪枝不改变正确性但可以在无效输入上少走一圈循环。第四自定义栈的扩容条件。我用的是topIndex 1 capacity判断栈满因为topIndex从 -1 开始当topIndex capacity - 1时说明下一个 push 会越界。如果你从 0 初始化判断条件就会变成topIndex capacity。写代码前先把约定定死能少踩很多坑。4. 边界用例与复杂度把这道题彻底测明白算法题不看边界用例等于没做。我每次讲这道题都会把用例分成几组来跑。4.1 一组覆盖所有无效姿势的测试清单官方示例是必测的()、()[]{}应返回 true(]、([)]应返回 false{[]}应返回 true。其中([)]就是典型的数量平衡但顺序错误[还没等来]就遇到了)栈在这里直接抓住问题。第二组是边界长度空串应该是 true因为没有括号需要匹配单个字符(和)都应该是 false。奇数长度剪枝会让(和)在第一拍就直接返回 false完全正确。第三组是嵌套和残缺((()))是 true((())是 false因为多了一个左括号))((是 false因为一开始就出现多余右括号。((()))可以验证深层嵌套时栈的压入和弹出顺序是对的。第四组是压力测试生成一个长度为 10000 的全左括号串也就是((((...(((。如果手写栈扩容逻辑有 bug这里会崩溃或者误判全右括号串可以验证“空栈弹栈”的路径是否安全。4.2 复杂度的标准答案时间上每个字符最多入栈一次、出栈一次其余操作都是 O(1)所以整体复杂度是 O(n)。空间上栈里最多同时存在 n 个左括号比如输入全是左括号的情况因此额外空间是 O(n)。有些面试官会追问能不能做到 O(1) 空间如果字符串里只有一种括号当然可以用一个计数器就行。但这道题有三种括号并且要求顺序闭合你需要保存的是“待闭合括号的完整顺序”这个信息本质上就是一个栈所以最坏情况下的 O(n) 空间是跑不掉的。这样回答可以让面试官知道你不只是在背题而是真的理解了下界。4.3 一个很隐蔽的“假通过”场景结合“忘记弹栈”这个错误我见过一个很有意思的失误。假设你写的是“栈里存左括号”版本匹配成功后忘了pop()。输入()时处理完()后栈里还留着一个(最后st.empty()为 false整体还是会判错说明这个 bug 未必能靠一两个简单用例发现。真正危险的场景是多个不同括号类型混在起。如果代码逻辑出错导致拿栈里残留的{去匹配}虽然{}本身是有效配对但这种匹配顺序已经被破坏了。所以你要理解弹栈操作存在的意义它保证每次匹配的都是最近那个未闭合左括号而不是任意一个可以配对的左括号。这也是栈与其他结构最本质的区别。5. 调试手写栈时我常用的几个土办法手写栈之后调试方式和直接使用std::stack不太一样。这里分享一些我实际用过的办法。5.1 一个故意写错的版本我在教学时经常拿一个带 bug 的版本让学员找问题。比如下面这段有一个非常隐蔽的错误class Solution { public: bool isValid(string s) { MyStack st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); } else { if (st.top() ! ( ch )) return false; if (st.top() ! [ ch ]) return false; if (st.top() ! { ch }) return false; st.pop(); } } return st.empty(); } };问题在哪里st.top()在空栈时是未定义行为。如果输入是}代码会先调用st.top()然后访问越界。而且这里的比较顺序也有问题用st.top() ! ( ch )这种形式逻辑上只能硬凑一旦st.top()越界后续判断全部建立在垃圾数据之上。正确写法永远是右括号出现时先确认栈非空再取栈顶比较然后弹出。顺序不能反。这也是我在前面代码里反复强调st.empty() || st.top() ! ch的原因。5.2 打印内部状态的调试技巧手写栈没有现成的迭代器想打印栈内容得自己来。我的土办法是临时在push和pop之后把topIndex和栈内元素打出来。比如处理([)]时你会在调试输出里看到遇到(压入(栈内元素为(。遇到[压入[栈内元素为(、[。遇到)取栈顶是[和期望的(不匹配返回 false。这个过程只靠眼睛盯代码可能看不出来但一旦把状态打印出来问题非常直观。如果你在本地 IDE 里调试也可以直接设断点查看data[0]到data[topIndex]的内容。这类“笨办法”在复杂逻辑里反而比花里胡哨的调试工具更高效。5.3 一个反复出现的误解为什么匹配顺序必须是“反”的不少读者会问为什么处理([])时第一个右括号匹配的是内层的[而不是外层的(这恰恰是栈存在的理由。你可以把括号理解成一层层半开的门先开的门要等里面所有门都关上之后才能关。匹配顺序和出现顺序相反但闭合顺序和栈的弹出顺序完全一致。如果用数组来解决你需要手动维护一个“最近未闭合位置”的指针这本质上就是自己实现栈顶指针。与其绕一大圈不如直接用栈。理解这一点之后再看题目里“左括号必须以正确的顺序闭合”这句话你会觉得它其实就是在描述 LIFO。6. 自定义栈这件事的工程价值与下一步练习6.1 什么时候应该手写栈什么时候直接用 STL默认情况下工程代码里直接用std::stack是合理的。STL 实现经过严格测试可读性高也没有手动管理内存的隐患。手写栈的真正理由有三类一是学习数据结构原理二是面试中展示基本功三是嵌入式等标准库不全或内存受限的场景。做过这道题以后你再看到std::stack的push、pop、top脑子里应该自然浮现出data[topIndex]和data[topIndex]这些底层操作。这种“看到接口能想到实现”的能力比背下十道题更有价值。6.2 顺手可以做的小扩展如果你想巩固这个思路我建议按顺序做两件事。第一把“压入右括号”和“压入左括号”两个版本各手写一遍感受它们在代码量和可读性上的差异。第二去试一下 LeetCode 232 “用栈实现队列”你会真正体会到两个栈如何配合实现先进先出。最后说一句我的个人习惯刷这类基础题我会故意把 STL 容器全部换成手写版本不是为了标新立异而是想让自己对数据结构保持直觉。栈顶指针从 -1 还是 0 开始、扩容时要不要拷贝、析构时怎么释放这些问题一旦自己动手写过就不再是八股而是身体记忆的一部分。等你熟练了自然会知道什么时候该手写、什么时候直接std::stack一行搞定更合适。