我正在学习栈和队列。这篇先记录已经写出来的顺序栈、test.c中的练习以及用这个栈做的 LeetCode 20「有效的括号」。本文保留我当时的原代码包括注释掉的练习和函数命名不一致的地方后面单独说明问题与最小修正便于复习时看到真实的思考过程。这里没有队列的实现代码所以不把栈误写成队列。一、先认清这个栈a、top、capacityST用动态数组保存数据。a指向数组起始位置capacity表示已经申请到的元素个数top表示目前已有的有效元素个数同时也是下一个元素应该写入的下标。这样空栈是top 0栈顶下标是top - 1有效范围是a[0]到a[top - 1]。状态topcapacity下一次入栈位置刚初始化00先申请空间再写a[0]压入 1、2、334a[3]四个位置都用完44必须先扩容这里选的是“top指向下一个空位”的写法。有的教材让top指向当前栈顶初始值便可能是-1两种约定都能用但入栈、出栈、判空、取栈顶必须贯彻同一种约定。Stack.h完整原代码#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintSLDataType;typedefstructStack{SLDataType*a;inttop;intcapacity;}ST;//初始化和销毁voidSLInit(ST*pst);voidSTDestroy(ST*pst);//入栈和出栈voidSLPush(ST*pst,SLDataType x);voidSLPop(ST*pst);//取栈顶数据SLDataTypeSTTop(ST*pst);//判空boolSTEmpty(ST*pst);//获取数据个数intSTsize(ST*size);typedef int SLDataType;把栈的数据类型暂定为int所以a是int数组。typedef struct Stack { ... } ST;让后续函数可以用ST*表示栈地址。#pragma once防止头文件在一次编译中重复展开四个标准头文件分别提供printf/perror、malloc/realloc/free、assert和bool。头文件负责声明Stack.c负责定义test.c负责调用。三处的函数名和参数类型必须一致参数变量叫size还是pst不影响链接但STsize(ST * size)中的size实际上也是一个栈指针叫pst更不容易误解。二、逐个看Stack.c的功能和用法Stack.c完整原代码#includeStack.hvoidSLInit(ST*pst){assert(pst);pst-aNULL;pst-top0;pst-capacity0;}voidSLDestroy(ST*pst){assert(pst);free(pst-a);pst-toppst-capacity0;}voidSLPush(ST*pst,SLDataType x){assert(pst);//扩容if(pst-toppst-capacity){intnewcapacitypst-capacity0?4:pst-capacity*2;SLDataType*tmp(SLDataType*)realloc(pst-a,sizeof(SLDataType)*newcapacity);if(tmpNULL){perror(realloc fail);return;}pst-atmp;pst-capacitynewcapacity;}pst-a[pst-top]x;pst-top;}voidSTPop(ST*pst){assert(pst);assert(pst-top0);pst-top--;}SLDataTypeSTTop(ST*pst){assert(pst);assert(pst-top0);returnpst-a[pst-top-1];}boolSTEmpty(ST*pst){assert(pst);returnpst-top0;}intSTsize(ST*pst){assert(pst);returnpst-top;}SLInit初始化调用SLInit(s)时s是局部变量s的地址函数通过pst修改同一个栈。assert(pst)要求这个地址不为NULL。随后把数组指针设为NULL把元素数和容量都设为 0。初始化后还没有申请数组内存第一次SLPush才会申请。先初始化再使用才不会拿未初始化的野指针去realloc或free。SLPush最需要搞懂的动态扩容入栈的顺序是检查栈指针 → 判断空间是否已满 → 必要时申请更大的数组 → 在a[top]写入数据 →top。绝不能先写入再判断是否扩容。初始a NULLtop 0capacity 0 压入 100 0扩到 4写 a[0] 10top 变 1 再压 20、30、40依次写 a[1]、a[2]、a[3]top 变 4 压入 504 4扩到 8写 a[4] 50top 变 5if (pst-top pst-capacity)的意思是“有效元素数等于可存元素数”即没有空位。pst-capacity 0 ? 4 : pst-capacity * 2在第一次分配时取 4以后每次翻倍。增长策略让多数入栈只需一次写入偶尔扩容会复制旧元素单次最坏O(n)连续入栈的均摊时间是O(1)。realloc(pst-a, sizeof(SLDataType) * newcapacity)的第二个参数是字节数所以必须乘sizeof(SLDataType)。这里的newcapacity是“多少个元素”并非“多少字节”。realloc(NULL, n)相当于首次申请内存。已有内存时它可能在原地址扩也可能搬到新地址旧数据会保留到新申请的空间中但成功后只应使用返回的新指针。为什么先接到tmp再写pst-a tmp因为realloc失败会返回NULL而原内存仍归原指针所有。如果直接写pst-a realloc(...)失败时就丢了原地址内存泄漏。当前写法失败后调用perror并returntop和capacity没变旧栈仍可使用但SLPush返回void调用者无法从返回值判断这次入栈是否成功。后面的 LeetCode 解法依赖压栈成功内存不足时可能错误地判断括号。若要把这套栈用于需要可靠错误处理的程序应让入栈函数返回成功/失败或采用明确的退出策略。还有一点capacity * 2和sizeof(...) * newcapacity在极大输入下应检查整数溢出本练习代码没有做这个防护。扩容成功后先更新a和capacity再执行pst-a[pst-top] x; pst-top;。写入时top仍是下一个空位的下标自增后它又恢复为有效元素个数。这里不能先top再用a[top]否则第一次入栈就会跳过a[0]。SLDestroy销毁free(pst-a)归还动态数组free(NULL)也是安全的。之后把top、capacity清零。当前代码没有把pst-a设回NULL因此留下悬空指针销毁后若再次调用SLDestroy或者不重新初始化就入栈都可能出错。最小修正是在free后补pst-a NULL;。不过本文原代码保持不动提醒自己按现状只能销毁一次、销毁后不再使用。STPop、STTop、STEmpty、STsizeSTPop(s)只让top--逻辑上删掉栈顶不必清空数组里的旧值下一次入栈会覆盖它。assert(pst-top 0)表示空栈不能出栈。函数定义是STPop头文件却声明成SLPop必须统一。STTop(s)返回a[top - 1]但不删除元素所以通常先读栈顶再调用STPop。空栈时不能读取函数用断言阻止这种调用。STEmpty(s)在top 0时返回true。遍历出栈时可以写while (!STEmpty(s))。STsize(s)返回有效元素个数top并非容量。头文件中参数名size没有改变函数类型但建议改成pst便于阅读。assert只适合检查“调用者本不该犯的错误”。开启NDEBUG时断言可能被编译掉所以不能把它当成正式的空栈错误处理。调用STTop/STPop前仍要确保非空。三、test.c完整原代码与实际执行顺序#includestdio.h#includestdlib.h////int main()//{// // 原地扩容// // 异地扩容// int* p1 (int*)malloc(8);// printf(%p\n, p1);//// int* p2 (int*)realloc(p1, 80);// printf(%p\n, p2);//// free(p2);////// int i 0;// int ret1 i;//// int ret2 i;//////// return 0;//}#includeStack.h//int main()//{// ST s;// STInit(s);// STPush(s, 1);// STPush(s, 2);// STPush(s, 3);// STPush(s, 4);//// printf(%d\n, STTop(s));// STPop(s);// printf(%d\n, STTop(s));// STPop(s);// STPop(s);// STPop(s);// STPop(s);//// //printf(%d\n, STTop(s));//// STDestroy(s);//// return 0;//}intmain(){// 入栈1 2 3 4// 出栈4 3 2 1 / 2 4 3 1ST s;STInit(s);STPush(s,1);STPush(s,2);printf(%d ,STTop(s));STPop(s);STPush(s,3);STPush(s,4);while(!STEmpty(s)){printf(%d ,STTop(s));STPop(s);}STDestroy(s);}这份文件有三段练习。第一段已注释的malloc/realloc用来观察原地扩容和异地扩容两个地址是否相同都可能发生不能预设一定原地扩。它没有检查分配失败也没有展示失败时原指针仍有效的处理方式所以更适合作概念练习。i是先自增再作为表达式的值i是先取旧值再自增从i 0开始ret1 1随后ret2 1、i 2。第二段已注释的main演示连续入栈、读栈顶、出栈。其中入了 4 个元素却调用了5 次STPop若解除注释并按一致的函数名编译最后一次会对空栈出栈触发断言。它还提醒我们STTop不等于出栈读完若想删除仍须STPop。当前实际的main先入栈1、2输出并弹出2再入栈3、4循环输出并弹出4、3、1。所以按预期顺序输出是2 4 3 1这是一种合法的栈出栈序列。4 3 2 1对应四个元素都先入栈再连续出栈是另一种操作顺序。循环判空避免了对空栈调用STTop最后STDestroy负责释放数组。这份原代码为什么目前编译不过我用 C11 的编译检查核对了磁盘上的原文件test.c的STInit、STPush、STPop找不到相应声明。名字对应关系如下调用处头文件声明Stack.c定义最小统一方式STInitSLInitSLInit调用处改成SLInitSTPushSLPushSLPush调用处改成SLPushSTPopSLPopSTPop头文件改声明为STPopSTDestroySTDestroySLDestroy定义改名为STDestroy或声明/调用统一为SLDestroy还要注意注释掉的第二段main也使用STInit/STPush将来解除注释时同样需要统一程序只能保留一个有效的main。上表只是说明如何对齐名称没有修改下面保存的原文件。即使先解决当前的“未声明函数”链接阶段仍会因STDestroy的定义名不一致而失败。四、LeetCode 20「有效的括号」题目截图与要求题目给一个只包含()、[]、{}的字符串判断每个左括号能否按类型相同、顺序正确的规则闭合。空字符串也符合“没有不匹配括号”的条件结果为true。截图中的()和()[]{}都返回true。题目保证只有这六种字符因此下面代码中的else可把非左括号视为右括号若用于普通文本就必须另外判断字符是否真是)、]、}。我的 LeetCode 代码保留原写法下面是我最初发来的实现整理了换行与缩进函数名和判断逻辑照原样保留。它同时包含栈结构、栈操作和isValid便于单独复盘题解。若和上面的本地三个文件一起编译会重复定义栈函数它是另一份题解代码展示不是要直接拼进同一个 C 工程。这份题解原文没有写标准库头文件若单独编译需要补上assert.h、stdbool.h、stdio.h、stdlib.h这里的SLDataType是int可以容纳这些 ASCII 括号字符STTop返回后再赋给char用于比较。typedefintSLDataType;typedefstructStack{SLDataType*a;inttop;intcapacity;}ST;voidSLInit(ST*pst){assert(pst);pst-aNULL;pst-top0;pst-capacity0;}voidSLDestroy(ST*pst){assert(pst);free(pst-a);pst-toppst-capacity0;}voidSLPush(ST*pst,SLDataType x){assert(pst);//扩容if(pst-toppst-capacity){intnewcapacitypst-capacity0?4:pst-capacity*2;SLDataType*tmp(SLDataType*)realloc(pst-a,sizeof(SLDataType)*newcapacity);if(tmpNULL){perror(realloc fail);return;}pst-atmp;pst-capacitynewcapacity;}pst-a[pst-top]x;pst-top;}voidSTPop(ST*pst){assert(pst);assert(pst-top0);pst-top--;}SLDataTypeSTTop(ST*pst){assert(pst);assert(pst-top0);returnpst-a[pst-top-1];}boolSTEmpty(ST*pst){assert(pst);returnpst-top0;}intSTsize(ST*pst){assert(pst);returnpst-top;}boolisValid(char*s){ST st;SLInit(st);while(*s){if(*s(||*s[||*s{){SLPush(st,*s);}else{if(STEmpty(st)){SLDestroy(st);returnfalse;}chartopSTTop(st);STPop(st);if((top(*s!))||(top[*s!])||(top{*s!})){SLDestroy(st);returnfalse;}}s;}bool retSTEmpty(st);SLDestroy(st);returnret;}为什么必须用栈遇到左括号就先记住遇到右括号时必须匹配最近一个还未闭合的左括号。这正是栈“后进先出”最后入栈的左括号最先接受检查。比如([{}])依次压入(、[、{随后}配{]配[)配(。如果只统计每类括号数量([)]虽然数量相等也会被误判为合法用栈会发现读到)时栈顶是[当场返回false。isValid的执行过程ST st; SLInit(st);创建并初始化一个空栈用它只保存尚未配对的左括号。while (*s)逐字符扫描直到遇到字符串结尾的\0。s让指针移到下一个字符本题的s是 LeetCode 传入的字符串首地址。如果是(、[、{SLPush(st, *s)入栈等待未来的右括号。否则遇到右括号时先用STEmpty判断是否已有可匹配的左括号。没有就先SLDestroy再返回false例如输入)(在第一个字符就失败。非空时取出top STTop(st)然后STPop(st)。三个条件分别检查(对)、[对]、{对}任一对不匹配就销毁栈并返回false。字符全部扫描完后还要检查STEmpty(st)。例如((没出现错误右括号但仍有未闭合左括号应返回false。先把判断结果存进ret销毁栈后再返回它。输入关键一步结果()[]{}每个右括号都配当前栈顶最后为空true([{}])闭合顺序{、[、(true([)]读到)时栈顶是[false(](与]类型不一致false(()扫描完还有(留在栈里false)(第一个右括号到来时栈为空false题解的易错点错误写法只比较左右括号的数量。为什么错数量相同不保证顺序([)]就是反例。正确写法右括号只与当前栈顶的左括号比较。以后判断题目出现“最近一个未匹配项”时先想栈。错误写法读到右括号先调用STTop。为什么错输入从右括号开始时会在空栈取栈顶触发断言。正确写法先STEmpty再取栈顶。以后判断任何需要栈顶的操作先证明栈非空。错误写法扫描结束直接返回true。为什么错((没遇到错误右括号但左括号没闭合。正确写法结果取决于最终STEmpty(st)。错误写法匹配失败直接返回。为什么错st.a可能已申请内存会泄漏。正确写法每条提前返回路径先销毁栈正常路径也要销毁。当前实现的额外限制SLPush分配失败只是打印错误并返回voidisValid不知道压栈失败可能给出错误结果SLDestroy释放后未清空a。这两点是栈接口本身的问题不是配对思路的问题。扫描一次字符串设长度为n时间O(n)最坏情况下所有字符都是左括号辅助空间O(n)。这里的栈按 4、8、16……扩容均摊入栈仍是常数时间。若空间分配失败当前实现并不保证正确返回值复杂度分析默认分配成功。五、复习时记住栈的关键约定是top表示“下一个空位”因此入栈写a[top]后top出栈只需top--取栈顶用a[top - 1]。SLPush的关键是先判断是否满、用临时指针接realloc、成功后更新地址和容量、最后写入并自增。括号题的关键是右括号只配最近的左括号而且必须处理空栈、类型不符、扫描完仍有剩余三类情况。多文件练习还提醒我头文件声明、实现定义、调用名称要逐个对齐不能只看算法思路就以为程序已经能编译。