栈和队列：从线性表到经典应用，一篇理清考点与边界

学完线性表的顺序存储和链式存储之后再看栈和队列会有一种“这俩不就是被焊死在固定位置的线性表吗”的感觉。这个直觉是对的但千万别因此小看它们。栈和队列是数据结构里少有的、几乎每个系统底层都会用到的结构程序函数调用、浏览器撤销、打字机回退靠栈打印任务、消息推送、线程池靠队列。这一篇系列笔记里我把它们放一块儿整理从逻辑定义讲到代码实现再讲到括号匹配、后缀表达式、单调栈这些初阶阶段最常遇到的场景顺便把408和期末考试里反复出题的那些边界条件统一过一遍。适合正在学数据结构、准备期末或者考研复习的朋友参考目标是看完之后能自己画图、手写代码、准确说出每个指针的移动方向。1. 先把栈和队列放进线性表的谱系里看1.1 为什么说它们是“受限的线性表”线性表的定义是n个数据元素的有限序列前面的顺序表和链表支持在任意位置插入、删除、查找。栈和队列本质上还是线性表只是操作被限制在了端点。栈只允许在一端插入和删除这一端叫栈顶另一端叫栈底特性是后进先出LIFO。打个比方食堂里一摞盘子后放上去的盘子在最上面拿的时候也先从最上面拿。队列则限制在两端操作队尾入队、队头出队特性是先进先出FIFO跟地铁闸机口排队一样先到的人先刷闸进站。这个“限制”听起来像是退化实际上是一种刻意设计。因为很多现实流程本身就是后进先出或先进先出的用这两种结构表达代码会变得非常直观。撤销操作就是一串栈每做一步就压入栈撤销时弹栈任务调度就是队列请求来了排到队尾处理完一个从队头走。数据结构的好坏不在于功能多不多而在于跟你表达的场景匹不匹配。408里栈和队列是选择题常客而且考得很细判空判满、指针移动方向、循环队列长度公式、共享栈判满条件。这些知识没有难度但不能靠死记硬背要把每一步的指针变化画出来画一遍就记住了。1.2 学完这一篇你应该带走什么给这篇笔记定三个下限目标。第一能画图推演。给你一个入栈序列1、2、3你能分析出哪些出栈序列合法哪些不合法给你一串字符你能模拟括号匹配过程。第二能手写公式。循环队列的长度公式、判满条件、共享栈的栈满条件提笔就能写不是背的是推导出来的。第三能写代码。顺序栈、链栈、循环队列、链式队列不查资料十分钟之内写出来并且能应对扩容和边界的情况。后面的内容就按“逻辑结构—物理实现—经典应用—避坑清单”的顺序展开一层一层把这两个结构吃透。2. 栈后进先出的“一柱擎天”2.1 顺序栈与链栈两种物理落地方式顺序栈有一个固定数组和一个栈顶指针。最主流的写法是top指向当前栈顶元素初始top-1表示栈空入栈执行arr[top] x出栈执行x arr[top--]。也有一种写法是top初始为0top先指向下一个可写入的位置入栈执行arr[top] x出栈执行x arr[--top]。两种写法没有谁对谁错但必须从一开始就定死一种否则写着写着就把指针搞混了。链栈相对好理解本质就是用单链表每次插入和删除都发生在头部链表头就是栈顶不需要考虑扩容的问题理论上容量只要内存允许就能不断增长。缺点是每个节点要额外存一个指针空间开销比顺序栈大。实际开发里顺序栈更常用因为连续内存访问更快链表节点散落容易产生缓存未命中。但写实验报告和应对面试时两种都要会。我给个实用建议初学阶段一定要自己手写一遍顺序栈不要直接调库一分钟能写出来才算过关。手写的内容很简单——结构体定义、初始化、判空、判满、入栈、出栈、取栈顶总共不超过40行。提到栈的空间很多人会联想到热词里的一个问题C语言局部变量越少所占栈空间越小吗这个问题可以放到操作系统函数调用栈的语境里讨论。局部变量确实在函数栈帧上分配变量越多通常栈帧越大但现代编译器会做优化变量可能被优化到寄存器里或者复用栈上已经死亡变量的空间。所以结论是局部变量越少通常能减小栈帧但不绝对写代码时优先保证清晰节省栈空间的事让编译器去操心。2.2 共享栈考研面试都爱出的冷门考点共享栈在工程里不算常用但408和期末考经常出因为它是“用有限空间做资源调配”的一个典型思维。思路很简单用一个数组实现两个栈栈0从数组开头向右增长栈1从数组末尾向左增长。定义两个栈顶指针top1-1top2MaxSize。入栈0执行arr[top1] x入栈1执行arr[--top2] x两者相向而行。判满的条件是top1 1 top2也就是两个栈顶指针碰头了。共享栈的好处是空间利用率高。如果用两个独立顺序栈每个栈都要预留空间如果一个栈满了另一个栈还空着多出来的空间无法借用。共享栈则允许两个栈动态“借用”彼此空出来的区域只要它俩的总数据量不超过数组容量就不怕。我当年复习的时候觉得这个点小而不起眼结果好几套考研模拟题都拿它当选择题压轴。核心就三个条件top1怎么动、top2怎么动、栈满怎么判。画一条数轴左边一个箭头右移右边一个箭头左移箭头相遇就栈满这个画面记住了就永远不会忘。2.3 栈帧、backtrace与递归栈在操作系统里长什么样初学栈的时候很多人觉得它就是一个纯理论结构离我们很远。实际上你的电脑每一微秒都在用栈——函数调用的底层机制就是栈。当函数A调用函数B时系统会为B开辟一段栈帧里面存放返回地址、参数、局部变量等。B执行完栈帧弹出回到A继续执行。这个过程不断嵌套就形成了调用栈。程序崩溃时打印出来的那一长串调用链就是各个栈帧按顺序展开的记录这就是backtrace栈回溯的原理。换句话说backtrace做的事情就是骂你代码里的栈信息翻了个底朝天。把“栈帧形成过程”和递归联系在一起很多概念就通了。递归的每一层都是一次函数调用都会压栈所以递归深度过大时会爆栈。这也是为什么某些应试指南里反复强调递归可以改成循环因为循环不消耗栈空间。学会栈之后再看你平时用的调试器、编程语言的异常堆栈、性能分析工具会发现它们其实都靠这一套机制吃饭。数据结构不是躺在纸上的概念它就是运行时真实发生的事情。把“抽象的栈”和“底层调用栈”在脑子里融合是理解栈的一个重要转折点。2.4 栈溢出与局部变量问题的辨析栈溢出是个高频问题来源主要有两种。第一种是递归深度过大或者递归写错了导致死循环。比如斐波那契数列用朴素递归实现n到了40左右性能就明显下降n到几十万就爆栈。解决的思路是改成循环、尾递归优化或者使用迭代显式栈模拟。第二种是函数内部定义了过大的局部数组比如int a[1000000]这会让当前栈帧直接撞上栈上限。大数组应该放到堆里动态分配或者用静态区。关于栈空间大小很多人不知道的是Linux上默认用户栈空间一般就8MB左右可以用ulimit -s查看。嵌入式环境里栈更小比如单片机、树莓派Pico这种资源受限平台栈可能只有几十KB热词里提到的rp2040 pico-sdk增大栈空间就是通过修改链接脚本或启动文件中的栈大小定义来扩大可用栈区这种问题在桌面开发里几乎不会遇到但一上嵌入式就得小心。给新手一个栈溢出的排查思路先看是不是递归爆栈再看函数内是否有超大数组最后看有没有死循环导致无限递归。不要一上来就怀疑编译器九成九是自己代码的问题。3. 队列先进先出的“水管”3.1 顺序队列的假溢出困境栈有一个栈顶指针就够了队列却需要两个指针front指向队头rear指向队尾的下一个位置。入队时rear后移出队时front后移。如果直接用普通数组就会遇到一个很尴尬的情况。假设数组长度是5你连续入队5个元素然后出队3个元素这时front3rear5虽然数组下标0、1、2已经空出来了但因为rear已经到了数组末尾新元素无法入队。这就是假溢出——明明有空间却说队列满了。这个坑对很多人来说是第一道坎因为我们习惯把数组想象成一条固定长度的直线元素从前往后排排满就结束。但队列的操作方向是单向的front和rear都只往后走头部空间被释放后就被浪费了。解法有两个一是把数组想象成首尾相接的环这就是循环队列二是不用数组改用链表动态分配节点需要几个就挂几个这就是链式队列。大多数人第一步都应该好好理解循环队列因为它牵扯到取模运算是408里非常稳定的出题点。画图解假溢出是最直观的方法画一条有5个格子的数组用两个下标分别标出front和rear的位置然后在空格子里试着填一个元素你会发现rear已经到边界了填不进去但front前面明明还有空位。这一步理解透了后面循环队列的取模公式就顺理成章。3.2 循环队列牺牲一格还是记个数循环队列就是把数组在逻辑上首尾相接rear到末尾后通过取模绕回开头入队变成rear (rear 1) % MaxSize出队变成front (front 1) % MaxSize。判空条件没有争议front rear。麻烦的是判满。因为如果让rear也指向一个实际元素队满时front和rear也会相等跟判空条件撞车。解决这个问题有几种常见方案。方案一牺牲一个存储单元不用让rear始终指向一个空位置。判满条件是(rear 1) % MaxSize front这是最主流的写法严蔚敏教材和王道408辅导书都用这套。方案二增加一个数据计数器size入队加一出队减一判空判满看size不牺牲空间但需要维护计数器。方案三增加一个tag标记最近一次是入队还是出队出队将tag置0入队置1判满条件是front rear 且 tag 1。这三种方案408选择题都出现过一定要都认识。循环队列的长度公式也常考(rear - front MaxSize) % MaxSize。加MaxSize再取模是为了防止负数。比如front在rear后面时直接相减得到的是负数加上MaxSize再取模才是真实元素个数。对初学者的建议是先把“牺牲一格”的方案写熟它最省事面试时也最容易说清楚。写代码时要注意取模符号别漏很多人写着写着就忘记给rear和front加% MaxSize导致数组越界。3.3 链式队列与入队出队图解链式队列用单链表实现需要两个指针front指向链表头节点哨兵节点rear指向链表尾节点。头节点可以看成哨兵不带数据这样队列为空的判断就是front rear。入队过程新建一个数据节点把它的next置空然后让rear-next newNode再把rear newNode。这个顺序不能反如果先把rear移过去就找不到原来尾节点在哪了。出队过程稍微麻烦一点先取p front-next然后把front-next p-next如果p恰好是最后一个节点也就是p rear那么还要把rear front最后free(p)。很多初学者会漏掉“最后一个节点出队时更新rear”这一步导致队列空了但rear还指着已释放的节点这是典型的悬空指针问题。链表队列不需要判满因为节点可以动态申请理论上只有内存耗尽才没法入队。这是它相比循环队列的最大优势。实际应用里如果你明确知道队列的峰值长度循环队列更紧凑高效如果长度波动大链式队列更灵活。热词里有“队列入队出队图解”我在这里用文字给你画一遍过程初始时front和rear都指向头节点入队节点AA挂到头节点后面rear指向A入队节点BB挂到A后面rear指向B出队一次front的next从A改为BA被释放再出队一次front的next指向NULLfront和rear重新相等队列空。你拿笔在纸上画一遍这个流程胜过看十遍别人的图。3.4 双端队列、阻塞队列与消息队列的延伸搞清楚基础的顺序队列和链式队列之后有必要顺着热词往外看一眼那些带前缀的“队列家族”。双端队列deque两头都可以插入和删除。C里的std::deque、Java里的ArrayDeque都是典型实现。它没有破坏队列的线性特征只是放宽了入队和出队的限制可以用在滑动窗口、回文判断、撤销重做这种需要两端操作的场景里。阻塞队列这是队列在生产环境里最重要的变体。队列为空时消费者来取数据会被阻塞队列为满时生产者来放数据会被阻塞。线程池的核心就是个阻塞队列热词里提到的“线程池的阻塞队列选择”就是这个结构在并发场景下的应用。Java里常见的ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue各有各的适用场景和坑但底层的数据结构逻辑都源自初阶数据结构里学的那个队列。消息队列比如Kafka、RabbitMQ、RocketMQ本质上把队列思想扩展到了跨进程、分布式的场景。消息先从生产者进入队列消费者按顺序拉取实现解耦、异步和削峰。但要注意消息队列远不止数据结构里的那个“先进先出缓冲区”它还包括持久化、分区分片、副本、顺序一致性、重复消费处理等一大堆工程问题。初学者只要在脑子里记住“消息队列是队列思想的分布式延伸”就够了具体的选型对比、死信队列、重复消费去重属于后续专门课程的范畴。4. 经典应用场景把抽象结构落到具体问题上4.1 括号匹配最朴素的栈应用学完栈之后第一个应该看的应用就是括号匹配因为它几乎用一个最简单的例子说明了“栈为什么需要存在”。思路是扫描字符串里的每一个字符遇到左括号(、[、{就入栈遇到右括号)、]、}就弹栈并检查弹出的左括号跟当前右括号是否匹配。最后扫描结束如果栈是空的说明所有括号都成功匹配否则就是有多余的左括号或者括号顺序有问题。这个算法的关键点在于括号的左半部分入栈后只有遇到对应的右半部分才会被弹出天然形成了一个嵌套顺序。字符串([)]虽然左右括号数量一样但左括号(入栈后遇到]弹出的是(不匹配判定非法。这就是栈的嵌套表达能力。给一个C语言的框架代码实验报告可以直接参考int isMatching(char *s) { char stack[100]; int top -1; for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { stack[top] s[i]; } else { if (top -1) return 0; // 右括号先出现 char ch stack[top--]; if (!(ch ( s[i] )) !(ch [ s[i] ]) !(ch { s[i] })) { return 0; } } } return top -1; }注意两个容易错的地方一是右括号出现时先检查栈是否为null否则对空栈取栈顶会越界二是最后不能直接返回1必须确认栈已空否则像((这种缺右括号的输入会被误判成合法。4.2 后缀表达式与计算器中缀转后缀表达式求值是栈应用的另一个经典场景。人习惯用的中缀表达式是ab*c运算符在两个操作数中间但这对于计算机来说不直观因为要考虑优先级。后缀表达式把运算符放在操作数后面变成abc*计算时只需要一个栈遇到数字压栈遇到运算符弹出两个数字做运算结果压回去不需要再考虑优先级。计算后缀表达式比较容易初学者真正的难点是中缀转后缀的规则步骤拆开是这样的扫描中缀表达式的每个字符。如果是操作数直接输出到后缀表达式中。如果是运算符分几种情况栈为空或栈顶是左括号时直接入栈否则如果当前运算符优先级高于栈顶运算符直接入栈如果当前运算符优先级低于或等于栈顶运算符把栈顶运算符弹出并输出然后继续与新的栈顶比较直到满足入栈条件。左括号直接入栈遇到右括号时不断弹出栈顶运算符并输出直到弹出的那个是左括号为止左括号只弹出不输出。这里最大的坑是很多人把左括号当成普通运算符去比较优先级。记住左括号入栈后它就像一个屏障只有右括号才能把它赶出来。左括号下方哪怕有加减乘除遇到左括号时也不该弹出。加减的优先级是1乘除的优先级是2。一句话总结就是高优先级先出栈同优先级也先出栈保证从左到右结合。你可以在纸上自己演练一遍ab*c-d看结果是不是abc*d-。4.3 单调栈与单调队列从初阶跨到算法进阶的桥热词里有“单调队列优化dp”这里必须提一下单调栈和单调队列它们是栈和队列在算法竞赛、面试算法题里最常见的进阶形态。单调栈就是栈内元素始终保持单调递增或递减。典型题目是“下一个更大元素”给定一个数组对于每个元素找它右边第一个比它大的元素。做法是维护一个栈遍历数组时先把栈中所有小于当前元素的元素弹出这些被弹出的元素的下一个更大元素就是当前元素然后把当前元素入栈。这样每个元素最多入栈一次、出栈一次时间复杂度只有O(n)而暴力做法是O(n^2)。单调队列最经典的题目是“滑动窗口最大值”。窗口大小为k求每个窗口中最大的数字。用双端队列维护可能成为最大值的元素下标队头始终放当前窗口的最大值。新元素入队时从队尾把小于等于它的元素都弹掉因为这些“小个子”在它进窗口之后永远不会再有机会当最大值了窗口滑动时如果队头下标已经滑出窗口把它从队头弹出。初学的时候千万别觉得单调栈和单调队列很玄。它们的本质只是“利用元素的出栈/出队时机排除不必要的比较”把冗余计算压缩掉。写通滑动窗口最大值你就掌握了单调队列的核心手感再去看优化DP的题目会顺畅很多。5. 期末复习与408应试的避坑清单5.1 判空判满的边界条件对照表栈和队列的各种实现方式判空判满是最容易记混的考点。我把常见形态整理成一张表复习时可以直接对照记忆。结构判空条件判满条件备注顺序栈top-1top -1top MaxSize-1栈顶指针指向当前元素顺序栈top0top 0top MaxSize栈顶指针指向空位链栈top NULL一般不判满动态分配节点共享栈top1 -1 top2 MaxSizetop1 1 top2两个栈顶相向循环队列front rear(rear 1) % MaxSize front牺牲一个元素空间链式队列带头节点front rear一般不判满注意尾指针悬空问题这张表背后有一条逻辑主线判空判满本质上是在问“两个指针在什么情况下相遇/撞车”。理解了这个就算遇到某个不熟悉的变形也能现场推出来。5.2 常见知识陷阱与选择题套路408和期末考里栈和队列的坑来来回回就那几个。第一个是循环队列判满误用front rear那是判空条件但解法没变[轮]这里可以加一段描述第一个是说循环队列你要时刻记着“要不要浪费一个位置”。第二个坑是链式队列最后一个节点出队后忘了把rear更新为front导致队列虽然空了rear却指着已经释放的内存后面再入队就错乱。第三个坑是中缀转后缀时把左括号当成普通运算符处理。第四个坑是入栈序列1、2、3问你出栈序列能不能是3、1、2答案是“不能”。分析方式也很朴素3先出栈说明1和2都已经在栈里2压在1上面所以2必须比1先出不可能1先出。这类题目判断方法是看某个元素出栈前它前面的元素有没有被压在栈底且被后到的元素挡住。还有一个容易错的操作是“入栈出栈交替进行”。比如只有两个栈空间入栈1、入栈2、出栈、入栈3问此时栈中顺序很多人会想当然写1、3。正确画法是1进2进出栈时2出再入栈3栈底到栈顶是1、3。这类题必须一步步推指针变化不能凭直觉。5.3 实验报告与代码实现的注意点学习栈和队列时实验报告和上机题是绕不开的。我见过太多人的报告就是把代码贴上去然后抄一段结论完事这其实浪费了练习机会。一份有含金量的实验报告至少应该包含三样东西状态图、测试用例、时空复杂度分析。状态图就是手动画出入栈出栈过程中的指针变化、数组元素排布这是让老师相信你“真的理解了”的关键。测试用例不能只测正常情况还要测边界空栈出栈、空队出队、队列满时入队、链队列最后一个节点出队。这些边界情况才是真正的考察点也是写代码时最容易藏bug的地方。代码实现上还有几个实践建议。第一用数组实现顺序栈时扩容前记得先检查旧元素数量重新分配内存后用memcpy或循环拷贝。第二循环队列的所有指针移动都要取模并且每次移动前先想清楚“现在front和rear谁在前谁在后”。第三写链式队列时出队函数一定要处理“最后一个元素”的特殊情况否则链表断了队列也就废了。做OJ题时最常见的三个报错是数组越界通常是循环队列取模写错、栈溢出递归或超大局部数组、空指针链式队列入队前没判空。遇到报错不要慌按这三个方向排查命中率极高。6. 说点我自己的实操体会这篇笔记写到最后分享一点真实经验。我当年学栈和队列时最大的感觉是“看得懂写不对”看教材上的入栈出栈图一看就明白合上书自己写代码就各种越界。后来的心得是别信自己的脑子信自己的手。每学一个新结构就在纸上把一个4元素的操作序列完整画一遍front、rear、top全部标出来再跟着图把代码写一遍。这个过程很笨但效果出奇地好。另一个实用技巧是把栈和队列跟后面的知识提前挂上钩。树的先序、中序、后序遍历本质上就是递归调用栈的进出过程树的层序遍历本质是队列图的深度优先搜索用栈思想广度优先搜索用队列思想。你在初阶把这些底层结构和后面的大块头联系起来学树和图的时候会很轻松。再补充一个很多人不知道的小技巧。如果你在一个工程里需要临时逆序一组数据最省事的方式就是用栈把数据依次push进去再依次pop出来顺序就反了。同理需要按顺序处理一批带优先级的任务自然想到队列遇到“最新的最优先”那多半该用栈或者优先队列的变体。能想清楚“这个场景为什么用栈而不是队列”你对这两兄弟的理解就真的到位了。