很多人学数据结构都是从栈和队列开始的也是从它们开始第一次感受到“书上会的题”和“实际用的知识”之间隔着一条鸿沟。老师教你背下“栈是后进先出LIFO队列是先进先出FIFO”你以为自己懂了转头看到程序报错里的 stack overflow、听到架构师讨论 Kafka 和 RabbitMQ 选型、打开线程池源码发现构造函数里躺着好几种 BlockingQueue立刻又懵了。这篇文章我就把这块拼图给你补上。我会从栈和队列对线性表的“操作限制”讲起一路讲到函数调用栈帧形成过程、循环队列为什么要浪费一格、线程池阻塞队列选型、消息队列三巨头差异以及括号匹配、表达式求值、浏览器双栈这些经典应用。不只是让你记住定义而是让你明白“为什么这么设计”以及工程里它们到底是怎么被“包装”成各种高级组件的。1. 先想清楚一个问题栈和队列到底在“限制”什么1.1 都是线性表凭什么它们俩特殊数组和链表是最基础的线性存储结构。数组像把所有东西摊在桌面上你可以随手取任意一件链表像一串珠子你可以从任意位置剪开再缝上。它们的核心能力是“随机访问”或“灵活插入删除”。但实际场景里很多时候你根本不需要这种自由。你只需要两种情况一种是最新的东西先被拿走比如浏览器后退按钮、编辑器撤销、函数调用返回另一种是最早来的先被服务比如食堂打饭排队、打印机任务队列、消息推送顺序。这两种诉求太常用了干脆单独拎出来做成两个抽象结构——栈和队列。栈就是那筒羽毛球你只能从筒口把球一个一个放进去也只能从筒口把最上面那个取出来中间的被死死压住。队列就是食堂窗口前的那条队伍新来的必须站到最后面窗口只服务排在最前面的人谁也别想插队。所以栈和队列的本质是什么是“操作受限的线性表”。线性是说它们装的东西仍然是一串有序元素受限是说插入和删除的位置被锁死了栈只能在同一端栈顶插入和删除。队列只能在队尾插入在队头删除。就这一个限制成就了两个极其重要、又极其好用的结构。1.2 栈和队列不是存储结构是“访问规则”这是我特别想纠正的一个误区。很多人问“栈到底用数组实现还是链表实现”——这个问题问反了。栈和队列不是存储结构它们是接口、规则、抽象约束。底层用什么存完全可以另说。C 标准库里的 std::stack 默认拿 deque 当底层容器但你也可以传入 vector 或 liststd::queue 同样可以换底层容器。这不叫“栈就是 vector”而是“我用某种存储结构去满足了栈的约束”。做一个形象的类比栈像是“只能从最上面拿盘子的消毒柜”这个规则至于盘子是靠墙码的、还是放在转盘上的那是另一回事。只要规则不变外面的用户感受就完全一致。理解这一点很重要。因为在工程里你常常不是在“用一个现成的栈”而是在设计一个组件、一条链路时主动给自己加上这样的访问限制。限制越多出错的可能越小语义越清晰。你写消息队列时规定“队头消费、队尾生产”写线程池时规定“核心线程满了去排队”都是在套用队列规则。1.3 这种限制为什么值钱你可能会觉得又不能用下标随机访问又不能中间插队这不就是个残缺的数组吗恰恰相反。限制换来了两个东西效率确定性和语义清晰度。先说效率。栈和队列的核心操作入栈/出栈、入队/出队都能做到 O(1) 时间并且如果你用数组实现连内存都是连续访问的CPU 缓存极度友好。相比之下链表任意位置的插入虽然也是 O(1)前提是你已经有指针但你要为了“可以随便插”这个用不上的能力付出每个节点多存一个 next 指针的内存代价。再说语义。后端开发里到处是异步任务你如果不规定队头先消费大家都去抢同一个资源那就要加锁、就要竞争、就要乱序。队列天然地表达了一种“先来先服务”的政策让整套系统的行为可预测。调试的时候一个 FIFO 队列里的数据流向是清清楚楚的不需要猜。所以我把栈和队列看作是两套“思维模具”遇到一个需求先不急着选 Redis、上消息队列先想想它的本质到底是 LIFO 还是 FIFO。想清楚了技术选型会容易很多。2. 从数组到调用栈栈的实现与栈帧生成过程2.1 顺序栈的核心实现top 指针的两个边界我用 C 语言写一个最经典的顺序栈顺便把边界问题讲透。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶下标 } SeqStack; // 初始化top -1 表示空栈 void initStack(SeqStack *s) { s-top -1; } int isEmpty(SeqStack *s) { return s-top -1; } int isFull(SeqStack *s) { return s-top MAX_SIZE - 1; } // 入栈 int push(SeqStack *s, int value) { if (isFull(s)) return 0; // 栈满入栈失败 s-data[(s-top)] value; return 1; } // 出栈 int pop(SeqStack *s, int *value) { if (isEmpty(s)) return 0; // 空栈出栈失败 *value s-data[(s-top)--]; return 1; }你注意我把 top 初始化为 -1这样 top 指向的是“栈顶元素的位置”。如果初始化为 0top 指向的则是“下一个空位”。两种写法都有人用但我强烈建议你用 -1 这种因为它让“栈空条件”和“栈满条件”都很好写不容易把下标和数量搞混。还有一个经常被忽略的点栈满判断逻辑。静态数组实现必须预先知道容量满了就把新数据拒之门外。工程里如果预估不好容量就得做动态扩容也就是当 top 到达容量上限时重新分配一个更大的数组把旧数据拷贝过去。很多专业选手会顺手把容量翻倍就像 C vector 扩容策略一样均摊下来插入成本仍然是 O(1)。2.2 函数调用时栈帧是如何形成的如果你学过程序运行一定听过“调用栈”。但栈帧到底怎么来的我用一个简单的例子拆给你看。假设函数 A 调用了函数 B参数是一个整数。程序从 main 一直执行到 A再进入 B操作系统给这个线程分配的那块栈内存会按顺序做这么几件事调用者A先把参数压栈。不同平台规则不同x86 上常见的是从右往左压栈。然后把当前指令的下一条地址也就是“函数返回后该执行哪条指令”压栈。这叫返回地址。进入 B 后B 的第一件事通常是保存调用者 A 的栈底指针旧 ebp再把自己的栈底指针指向当前栈顶形成一个新的栈帧。B 如果还有局部变量就再向下移动栈顶指针给这些局部变量腾出空间。这就是你经常听到的“栈帧形成过程”。一个栈帧里装的就是局部变量、参数、返回地址、旧栈帧指针。B 执行完毕后先恢复旧栈底指针再根据返回地址跳回 A栈顶恢复原样。整个过程像视频倒放一样干干净净。这也就解释了为什么递归能一层套一层地展开每层调用都会压一个新栈帧每层返回都会弹掉一个。一旦递归没有终止条件或者层数过多栈空间被耗尽就会触发我们熟悉的 stack overflow。2.3 栈溢出、backtrace 与“为什么栈内存比堆小”很多初学者不理解为什么局部大数组会栈溢出而同样大小的对象用 malloc/new 就没问题因为操作系统的线程栈默认很小。Linux 下主线程栈常见是 8MBWindows 默认 1MB 左右而堆是进程级的可分配空间动辄几十GB。栈上放 10MB 局部数组基本必崩堆上申请 10MB毫无压力。那“全局静态变量”呢它们在数据段不占栈空间所以也能轻松容纳大块数据。这就是为什么嵌入式开发里常把大缓冲区定义成全局数组或 static 数组的原因之一——栈本来就紧巴巴别去霍霍它。栈还有一个特别实用的特性由于栈帧是连续嵌套的每个栈帧里都保存了调用方的地址所以调试器能实现 backtrace 栈回溯。也就是你看到程序崩溃时的调用链#0 in B at b.c #1 in A at a.c #2 in main at main.c原理就是顺着每个栈帧里的旧帧指针往回链。ARM 平台原理类似只是借助帧指针 FP 和链接寄存器 LR 来恢复现场。中断发生的时候硬件也会自动把程序状态、返回地址压栈形成所谓“中断栈帧”本质还是在用栈的 LIFO 规则保护现场、逐级恢复。所以栈不仅是教材里的数据结构它直接就是你程序运行的基础设施。理解了栈帧你再看崩溃日志里的调用链会有一种“原来如此”的通透感。3. 队列的两种实现与循环队列的“浪费一格”3.1 顺序队列为什么会假溢出队列最直观的实现是用数组front 指向队头rear 指向队尾的后一个位置。入队时 data[rear] x出队时 x data[front]。乍一看没问题但你模拟一下就会发现问题当 rear 走到数组末尾而 front 也往后移动了若干次后数组前半段实际是空的但 rear 已经等于 MAX_SIZE新元素进不来了。明明有空间却报“队满”。这就是顺序队列的假溢出。解决方法就是循环队列把数组想象成一个首尾相接的环rear 和 front 绕圈走计算位置都用取模(rear 1) % MAX_SIZE。只要数组没被真正填满rear 就能从尾部绕回头部继续存。3.2 循环队列判空的两种流派循环队列引入一个新问题怎么区分“空”和“满”如果只靠 front rear这个条件既可能表示空也可能表示满。业内常见三种处理办法牺牲一个存储单元约定 rear 的下一个位置是 front 时判满即(rear 1) % MAX_SIZE front。这个方案简单高效但数组中永远有一个位置不能用最多存 MAX_SIZE - 1 个元素。增加 length 字段用一个变量记录元素个数。判空条件是 length 0判满条件是 length MAX_SIZE。代码稍微多两行但逻辑万分直观。增加 tag 标记用一个标记位记录最后一次操作是入队还是出队用来区分空和满。实际工程中用得少教材中出现更多一些。我个人更推荐第二种尤其是给初学者讲解的时候。它不容易写错少一个元素存储空间换来的逻辑清晰完全值得。热搜里那句“同时以 rear 和 length 分别指示环形队列中的队”说的就是这个方案。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; // 队头下标 int rear; // 队尾下标指向下一个插入位置 int length; // 当前元素个数 } CircularQueue; void initQueue(CircularQueue *q) { q-front q-rear 0; q-length 0; } int isFull(CircularQueue *q) { return q-length MAX_SIZE; } int isEmpty(CircularQueue *q) { return q-length 0; } // 入队 int enqueue(CircularQueue *q, int value) { if (isFull(q)) return 0; q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; q-length; return 1; } // 出队 int dequeue(CircularQueue *q, int *value) { if (isEmpty(q)) return 0; *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; q-length--; return 1; }这里我踩过一个小坑想提醒你循环队列每移动一次下标都要取模千万别把数组长度直接写成 MAX_SIZE 就完事一定要确保rear和front始终落在 [0, MAX_SIZE-1] 区间内否则访问越界是迟早的事。3.3 双端队列与单调队列的工程玩法除了普通队列还有双端队列dequedouble-ended queue它允许在头尾两端都做插入和删除。别小看这个能力滑动窗口类题目里它的价值会充分体现。最著名的应用是单调队列典型问题就是求滑动窗口最大值。思路维护一个双端队列里面存的是数组下标队列中的元素值保持严格单调递减。每当窗口滑动从队尾依次弹出所有比新元素小的元素下标因为它们留着也不可能是最大值把新元素下标压入队尾从队头弹出所有已经滑出窗口的下标。这样队头永远是当前窗口的最大值。每个元素最多入队一次、出队一次整体复杂度 O(n)比暴力法的 O(n*k) 强太多。from collections import deque def maxSlidingWindow(nums, k): q deque() result [] for i, v in enumerate(nums): # 维护单调递减队列 while q and nums[q[-1]] v: q.pop() q.append(i) # 移除滑出窗口的 if q[0] i - k: q.popleft() # 窗口满了才输出 if i k - 1: result.append(nums[q[0]]) return result单调队列不只是刷题工具它还能优化 DP 转移。比如某些区间最值参与的动态规划朴素转移是 O(n^2)用单调队列把“查最值”这一步均摊成 O(1)整体就能降到 O(n)。这就是热搜里“单调队列优化 DP”的真相。它用到的底层结构还是那个你熟悉的双端队列。4. 从教科书到生产阻塞队列、线程池队列与消息队列4.1 阻塞队列并发场景下的缓冲带学完基础队列下一个台阶就是阻塞队列。它在队列的基础上增加了“阻塞”语义队列空时消费者取元素会阻塞等待队列满时生产者放元素会阻塞等待。你写多线程代码最头痛的就是线程安全多个生产者往队列里塞任务多个消费者抢任务如果自己加锁做条件变量容易出错。Java 的 BlockingQueue 把这些封装好了内部用了锁和条件变量你只管 put/take。线程池里的任务队列选型是经典决策点。以 Executors 线程池为例几种常见队列差异巨大ArrayBlockingQueue有界、基于数组FIFO。配合饱和策略能防止任务无限堆积。LinkedBlockingQueue链表实现吞吐量通常更高但默认构造的容量是 Integer.MAX_VALUE等于无界。如果你用 Executors.newFixedThreadPool底层就是无界队列任务一多内存会炸。SynchronousQueue不存储任务每个 put 必须等一个 take适合需要“直接把任务交接给工作线程”的场景。我给个非常实用的建议生产环境线程池务必用有界队列并根据业务量压测设置一个合理容量配合 AbortPolicy 或者 CallerRunsPolicy 的拒绝策略。无界队列不是不能用但当你的上游突发流量上来任务排队几十万条内存直接被打穿到时候想优雅拒绝都来不及。再往外延伸一步如果连锁竞争都嫌重还有 CAS 实现的无锁队列比如 ConcurrentLinkedQueue以及各种针对高并发优化过的“无锁 MPMC 队列”。无锁队列的核心思路不复杂用原子变量维护头尾指针用 CAS 完成入队出队。难点在于处理并发交错时的 ABA 问题和内存回收。普通业务没必要一上来就上无锁但了解它的存在能帮你在压测出现锁竞争瓶颈时多一个思路方向。4.2 消息队列三巨头选型Kafka、RabbitMQ、RocketMQ再往外走消息队列本质上就是“跨进程、跨机器的生产者-消费者队列”。它把队列的 FIFO 思想放到了分布式环境下只是中间多了网络传输、持久化、副本复制这些包装。选型是很多团队头疼的事。我根据实际使用体验给你一张直白的对比表维度KafkaRabbitMQRocketMQ定位分布式日志/流处理管道灵活路由的消息中间件电商/金融场景的可靠消息系统吞吐量极高百万级/秒中等万级/秒高十万级/秒可靠性通过副本和 ISR 机制保证支持持久化、ACK、事务支持事务消息、延迟消息路由灵活性弱按 topic 消费强exchange routing key 灵活匹配中tag 过滤顺序消息分区内严格有序单队列有序多队列需自己控制队列内有序全局有序需设计社区生态非常活跃大数据生态标配老牌插件丰富阿里开源国内金融场景案例多每次有人问我“怎么选”我的答复都是先想清楚你的核心诉求是什么如果你的场景是日志采集、埋点、大数据管道追求的是高吞吐选 Kafka 几乎没错。如果业务系统路由复杂消息要按不同类型分发到不同消费者RabbitMQ 的 exchange 机制会让你舒服很多。如果消息不能丢、不能重复、甚至需要半事务机制比如订单和库存对账RocketMQ 的事务消息很有价值。还有一个绕不开的话题重复消费问题。消息队列大多保证 at least once也就是不丢但不保证不重复。消费者处理完消息后准备提交 offset结果进程崩溃再重启时消息被重新消费一遍——这种事太常见了。解决办法不是让消息队列“保证不重复”而是让消费者做到幂等用业务唯一 ID 去重比如订单号、流水号或处理前查一次 Redis 判断是否已处理或在数据库里建唯一索引。把重复消息变成可接受的比追求“绝对不重复”可靠得多。4.3 队列思想在任务调度与 AGV 调度中的延伸消息队列是显眼的例子还有一批不那么显眼、但同样到处是队列的场景。比如大模型调度平台里的任务队列。请求来了不是立刻执行而是进入待调度队列由调度器按照优先级、资源情况、超时时间统一分配。这里的队列往往不是普通 FIFO而是优先级队列或延迟队列高优先级任务插队到期未执行的任务被唤醒重排。JDK 的 PriorityBlockingQueue、DelayQueue 就是底层实现。AGV 调度系统也一样。一台自动导引车要完成搬运任务任务下发、路径申请、交通管制、状态上报全是一环扣一环的队列。AGV 的任务队列管理不好就会出现两车抢一条路、任务超时、电池耗尽却排不上充电任务的尴尬。技术栈的选择C 实时控制、Java/Go 后台调度、Web 前端监控可以五花八门但数据流的核心永远是对队列规则的把握。哪怕是最老派的集群调度系统管理员用 bqueues 查看作业队列权限本质也是维护一组“排队中的作业”和它们的调度策略。你看队列思想在工业软件里同样无处不在。5. 三个经典应用括号匹配、表达式求值与浏览器双栈5.1 括号匹配怎么写才不容易错栈的教科书级应用就是括号匹配。核心思路很简单遇到左括号([{压栈。遇到右括号弹栈并检查是否匹配。遍历完后栈必须为空。但实际写代码时有两个高频 bug一是遍历到右括号时根本没检查栈是否为空就直接 pop空栈 pop 导致崩溃二是遍历完了忘了检查栈空导致((()))这种合法串也放过。我见过很多人在白板上栽在这两个点上。def is_valid(s): stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) else: if not stack or stack.pop() ! pairs[ch]: return False return not stack为什么括号匹配天然适合栈因为“最近遇到的左括号必须最先被匹配”这个规则和栈的 LIFO 特性完全一致。嵌套结构越深越要靠栈把记忆一层层保存下来。5.2 中缀表达式转后缀一个栈如何完成优先级判断计算器实现是另一个经典的栈应用。人类习惯写中缀3 4 * 2但计算机更喜欢后缀3 4 2 * 因为后缀表达式求值不用处理括号和优先级。中缀转后缀的经典算法是用一个栈存运算符数字直接输出。遇到运算符时把栈顶所有“优先级不低于它”的运算符弹出再把它压栈遇到左括号直接压栈遇到右括号弹到左括号为止。这个过程最值得体会的一点是优先级本质上也是个“后进先出”问题。*先来后来但*必须先在表达式中出现所以*要比晚出栈。这就把“优先级判断”转化成了“出栈顺序判断”非常巧妙。求值同理用两个栈分别存操作数和运算符碰到运算符就弹两个操作数计算再压回去。整个计算器就没有任何魔法了全是栈的基本功。5.3 浏览器的前进后退为什么需要两个栈最后讲一个你每天都在用的场景浏览器后退按钮。想象一下你依次访问了 A、B、C 三个页面。正常情况下这像是一个栈A 在最底C 在最顶。点后退C 出栈到 B再点后退B 出栈到 A。但如果你后退到 B 之后又点击了一个新链接 D会发生什么C 还存在吗不会了。前进按钮会变灰C 被永久丢弃。这是为什么因为浏览器的导航记录是双栈结构后退栈存的是你一路浏览过来的页面。前进栈存的是你后退时弹出的页面。在 B 页点击新链接 D相当于入栈了一个新页面此时前进栈里的 C 被清空。所以后退栈为 [A, B, D]前进栈为空。这个机制保证了你的浏览历史永远是“一条链”不会出现“退回到一个已经不存在的世界”的怪异状态。编辑器的撤销/重做也是同一个套路撤销栈用来存操作记录重做栈在每次新操作时清空。所以你会在很多软件里发现做了新操作之后重做按钮就灰掉了。双栈或者说“历史-未来”模型是栈在交互系统里最优雅的应用之一。我一直建议把栈和队列当成“思维模型”来学而不是当成“容器”来背。遇到后进先出的场景第一反应是栈遇到先进先出的场景第一反应是队列遇到“既要队头淘汰、又要队尾插入”的滑动窗口场景第一反应是双端队列。有了这套反应你再看函数调用、线程池、消息队列、浏览器导航会发现它们全在同一个框架里只是穿了不同的外衣。数据结构学到这份上才算真正长进自己脑子里了。
栈和队列的工程实践：从函数调用栈到消息队列选型
很多人学数据结构都是从栈和队列开始的也是从它们开始第一次感受到“书上会的题”和“实际用的知识”之间隔着一条鸿沟。老师教你背下“栈是后进先出LIFO队列是先进先出FIFO”你以为自己懂了转头看到程序报错里的 stack overflow、听到架构师讨论 Kafka 和 RabbitMQ 选型、打开线程池源码发现构造函数里躺着好几种 BlockingQueue立刻又懵了。这篇文章我就把这块拼图给你补上。我会从栈和队列对线性表的“操作限制”讲起一路讲到函数调用栈帧形成过程、循环队列为什么要浪费一格、线程池阻塞队列选型、消息队列三巨头差异以及括号匹配、表达式求值、浏览器双栈这些经典应用。不只是让你记住定义而是让你明白“为什么这么设计”以及工程里它们到底是怎么被“包装”成各种高级组件的。1. 先想清楚一个问题栈和队列到底在“限制”什么1.1 都是线性表凭什么它们俩特殊数组和链表是最基础的线性存储结构。数组像把所有东西摊在桌面上你可以随手取任意一件链表像一串珠子你可以从任意位置剪开再缝上。它们的核心能力是“随机访问”或“灵活插入删除”。但实际场景里很多时候你根本不需要这种自由。你只需要两种情况一种是最新的东西先被拿走比如浏览器后退按钮、编辑器撤销、函数调用返回另一种是最早来的先被服务比如食堂打饭排队、打印机任务队列、消息推送顺序。这两种诉求太常用了干脆单独拎出来做成两个抽象结构——栈和队列。栈就是那筒羽毛球你只能从筒口把球一个一个放进去也只能从筒口把最上面那个取出来中间的被死死压住。队列就是食堂窗口前的那条队伍新来的必须站到最后面窗口只服务排在最前面的人谁也别想插队。所以栈和队列的本质是什么是“操作受限的线性表”。线性是说它们装的东西仍然是一串有序元素受限是说插入和删除的位置被锁死了栈只能在同一端栈顶插入和删除。队列只能在队尾插入在队头删除。就这一个限制成就了两个极其重要、又极其好用的结构。1.2 栈和队列不是存储结构是“访问规则”这是我特别想纠正的一个误区。很多人问“栈到底用数组实现还是链表实现”——这个问题问反了。栈和队列不是存储结构它们是接口、规则、抽象约束。底层用什么存完全可以另说。C 标准库里的 std::stack 默认拿 deque 当底层容器但你也可以传入 vector 或 liststd::queue 同样可以换底层容器。这不叫“栈就是 vector”而是“我用某种存储结构去满足了栈的约束”。做一个形象的类比栈像是“只能从最上面拿盘子的消毒柜”这个规则至于盘子是靠墙码的、还是放在转盘上的那是另一回事。只要规则不变外面的用户感受就完全一致。理解这一点很重要。因为在工程里你常常不是在“用一个现成的栈”而是在设计一个组件、一条链路时主动给自己加上这样的访问限制。限制越多出错的可能越小语义越清晰。你写消息队列时规定“队头消费、队尾生产”写线程池时规定“核心线程满了去排队”都是在套用队列规则。1.3 这种限制为什么值钱你可能会觉得又不能用下标随机访问又不能中间插队这不就是个残缺的数组吗恰恰相反。限制换来了两个东西效率确定性和语义清晰度。先说效率。栈和队列的核心操作入栈/出栈、入队/出队都能做到 O(1) 时间并且如果你用数组实现连内存都是连续访问的CPU 缓存极度友好。相比之下链表任意位置的插入虽然也是 O(1)前提是你已经有指针但你要为了“可以随便插”这个用不上的能力付出每个节点多存一个 next 指针的内存代价。再说语义。后端开发里到处是异步任务你如果不规定队头先消费大家都去抢同一个资源那就要加锁、就要竞争、就要乱序。队列天然地表达了一种“先来先服务”的政策让整套系统的行为可预测。调试的时候一个 FIFO 队列里的数据流向是清清楚楚的不需要猜。所以我把栈和队列看作是两套“思维模具”遇到一个需求先不急着选 Redis、上消息队列先想想它的本质到底是 LIFO 还是 FIFO。想清楚了技术选型会容易很多。2. 从数组到调用栈栈的实现与栈帧生成过程2.1 顺序栈的核心实现top 指针的两个边界我用 C 语言写一个最经典的顺序栈顺便把边界问题讲透。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶下标 } SeqStack; // 初始化top -1 表示空栈 void initStack(SeqStack *s) { s-top -1; } int isEmpty(SeqStack *s) { return s-top -1; } int isFull(SeqStack *s) { return s-top MAX_SIZE - 1; } // 入栈 int push(SeqStack *s, int value) { if (isFull(s)) return 0; // 栈满入栈失败 s-data[(s-top)] value; return 1; } // 出栈 int pop(SeqStack *s, int *value) { if (isEmpty(s)) return 0; // 空栈出栈失败 *value s-data[(s-top)--]; return 1; }你注意我把 top 初始化为 -1这样 top 指向的是“栈顶元素的位置”。如果初始化为 0top 指向的则是“下一个空位”。两种写法都有人用但我强烈建议你用 -1 这种因为它让“栈空条件”和“栈满条件”都很好写不容易把下标和数量搞混。还有一个经常被忽略的点栈满判断逻辑。静态数组实现必须预先知道容量满了就把新数据拒之门外。工程里如果预估不好容量就得做动态扩容也就是当 top 到达容量上限时重新分配一个更大的数组把旧数据拷贝过去。很多专业选手会顺手把容量翻倍就像 C vector 扩容策略一样均摊下来插入成本仍然是 O(1)。2.2 函数调用时栈帧是如何形成的如果你学过程序运行一定听过“调用栈”。但栈帧到底怎么来的我用一个简单的例子拆给你看。假设函数 A 调用了函数 B参数是一个整数。程序从 main 一直执行到 A再进入 B操作系统给这个线程分配的那块栈内存会按顺序做这么几件事调用者A先把参数压栈。不同平台规则不同x86 上常见的是从右往左压栈。然后把当前指令的下一条地址也就是“函数返回后该执行哪条指令”压栈。这叫返回地址。进入 B 后B 的第一件事通常是保存调用者 A 的栈底指针旧 ebp再把自己的栈底指针指向当前栈顶形成一个新的栈帧。B 如果还有局部变量就再向下移动栈顶指针给这些局部变量腾出空间。这就是你经常听到的“栈帧形成过程”。一个栈帧里装的就是局部变量、参数、返回地址、旧栈帧指针。B 执行完毕后先恢复旧栈底指针再根据返回地址跳回 A栈顶恢复原样。整个过程像视频倒放一样干干净净。这也就解释了为什么递归能一层套一层地展开每层调用都会压一个新栈帧每层返回都会弹掉一个。一旦递归没有终止条件或者层数过多栈空间被耗尽就会触发我们熟悉的 stack overflow。2.3 栈溢出、backtrace 与“为什么栈内存比堆小”很多初学者不理解为什么局部大数组会栈溢出而同样大小的对象用 malloc/new 就没问题因为操作系统的线程栈默认很小。Linux 下主线程栈常见是 8MBWindows 默认 1MB 左右而堆是进程级的可分配空间动辄几十GB。栈上放 10MB 局部数组基本必崩堆上申请 10MB毫无压力。那“全局静态变量”呢它们在数据段不占栈空间所以也能轻松容纳大块数据。这就是为什么嵌入式开发里常把大缓冲区定义成全局数组或 static 数组的原因之一——栈本来就紧巴巴别去霍霍它。栈还有一个特别实用的特性由于栈帧是连续嵌套的每个栈帧里都保存了调用方的地址所以调试器能实现 backtrace 栈回溯。也就是你看到程序崩溃时的调用链#0 in B at b.c #1 in A at a.c #2 in main at main.c原理就是顺着每个栈帧里的旧帧指针往回链。ARM 平台原理类似只是借助帧指针 FP 和链接寄存器 LR 来恢复现场。中断发生的时候硬件也会自动把程序状态、返回地址压栈形成所谓“中断栈帧”本质还是在用栈的 LIFO 规则保护现场、逐级恢复。所以栈不仅是教材里的数据结构它直接就是你程序运行的基础设施。理解了栈帧你再看崩溃日志里的调用链会有一种“原来如此”的通透感。3. 队列的两种实现与循环队列的“浪费一格”3.1 顺序队列为什么会假溢出队列最直观的实现是用数组front 指向队头rear 指向队尾的后一个位置。入队时 data[rear] x出队时 x data[front]。乍一看没问题但你模拟一下就会发现问题当 rear 走到数组末尾而 front 也往后移动了若干次后数组前半段实际是空的但 rear 已经等于 MAX_SIZE新元素进不来了。明明有空间却报“队满”。这就是顺序队列的假溢出。解决方法就是循环队列把数组想象成一个首尾相接的环rear 和 front 绕圈走计算位置都用取模(rear 1) % MAX_SIZE。只要数组没被真正填满rear 就能从尾部绕回头部继续存。3.2 循环队列判空的两种流派循环队列引入一个新问题怎么区分“空”和“满”如果只靠 front rear这个条件既可能表示空也可能表示满。业内常见三种处理办法牺牲一个存储单元约定 rear 的下一个位置是 front 时判满即(rear 1) % MAX_SIZE front。这个方案简单高效但数组中永远有一个位置不能用最多存 MAX_SIZE - 1 个元素。增加 length 字段用一个变量记录元素个数。判空条件是 length 0判满条件是 length MAX_SIZE。代码稍微多两行但逻辑万分直观。增加 tag 标记用一个标记位记录最后一次操作是入队还是出队用来区分空和满。实际工程中用得少教材中出现更多一些。我个人更推荐第二种尤其是给初学者讲解的时候。它不容易写错少一个元素存储空间换来的逻辑清晰完全值得。热搜里那句“同时以 rear 和 length 分别指示环形队列中的队”说的就是这个方案。#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; // 队头下标 int rear; // 队尾下标指向下一个插入位置 int length; // 当前元素个数 } CircularQueue; void initQueue(CircularQueue *q) { q-front q-rear 0; q-length 0; } int isFull(CircularQueue *q) { return q-length MAX_SIZE; } int isEmpty(CircularQueue *q) { return q-length 0; } // 入队 int enqueue(CircularQueue *q, int value) { if (isFull(q)) return 0; q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; q-length; return 1; } // 出队 int dequeue(CircularQueue *q, int *value) { if (isEmpty(q)) return 0; *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; q-length--; return 1; }这里我踩过一个小坑想提醒你循环队列每移动一次下标都要取模千万别把数组长度直接写成 MAX_SIZE 就完事一定要确保rear和front始终落在 [0, MAX_SIZE-1] 区间内否则访问越界是迟早的事。3.3 双端队列与单调队列的工程玩法除了普通队列还有双端队列dequedouble-ended queue它允许在头尾两端都做插入和删除。别小看这个能力滑动窗口类题目里它的价值会充分体现。最著名的应用是单调队列典型问题就是求滑动窗口最大值。思路维护一个双端队列里面存的是数组下标队列中的元素值保持严格单调递减。每当窗口滑动从队尾依次弹出所有比新元素小的元素下标因为它们留着也不可能是最大值把新元素下标压入队尾从队头弹出所有已经滑出窗口的下标。这样队头永远是当前窗口的最大值。每个元素最多入队一次、出队一次整体复杂度 O(n)比暴力法的 O(n*k) 强太多。from collections import deque def maxSlidingWindow(nums, k): q deque() result [] for i, v in enumerate(nums): # 维护单调递减队列 while q and nums[q[-1]] v: q.pop() q.append(i) # 移除滑出窗口的 if q[0] i - k: q.popleft() # 窗口满了才输出 if i k - 1: result.append(nums[q[0]]) return result单调队列不只是刷题工具它还能优化 DP 转移。比如某些区间最值参与的动态规划朴素转移是 O(n^2)用单调队列把“查最值”这一步均摊成 O(1)整体就能降到 O(n)。这就是热搜里“单调队列优化 DP”的真相。它用到的底层结构还是那个你熟悉的双端队列。4. 从教科书到生产阻塞队列、线程池队列与消息队列4.1 阻塞队列并发场景下的缓冲带学完基础队列下一个台阶就是阻塞队列。它在队列的基础上增加了“阻塞”语义队列空时消费者取元素会阻塞等待队列满时生产者放元素会阻塞等待。你写多线程代码最头痛的就是线程安全多个生产者往队列里塞任务多个消费者抢任务如果自己加锁做条件变量容易出错。Java 的 BlockingQueue 把这些封装好了内部用了锁和条件变量你只管 put/take。线程池里的任务队列选型是经典决策点。以 Executors 线程池为例几种常见队列差异巨大ArrayBlockingQueue有界、基于数组FIFO。配合饱和策略能防止任务无限堆积。LinkedBlockingQueue链表实现吞吐量通常更高但默认构造的容量是 Integer.MAX_VALUE等于无界。如果你用 Executors.newFixedThreadPool底层就是无界队列任务一多内存会炸。SynchronousQueue不存储任务每个 put 必须等一个 take适合需要“直接把任务交接给工作线程”的场景。我给个非常实用的建议生产环境线程池务必用有界队列并根据业务量压测设置一个合理容量配合 AbortPolicy 或者 CallerRunsPolicy 的拒绝策略。无界队列不是不能用但当你的上游突发流量上来任务排队几十万条内存直接被打穿到时候想优雅拒绝都来不及。再往外延伸一步如果连锁竞争都嫌重还有 CAS 实现的无锁队列比如 ConcurrentLinkedQueue以及各种针对高并发优化过的“无锁 MPMC 队列”。无锁队列的核心思路不复杂用原子变量维护头尾指针用 CAS 完成入队出队。难点在于处理并发交错时的 ABA 问题和内存回收。普通业务没必要一上来就上无锁但了解它的存在能帮你在压测出现锁竞争瓶颈时多一个思路方向。4.2 消息队列三巨头选型Kafka、RabbitMQ、RocketMQ再往外走消息队列本质上就是“跨进程、跨机器的生产者-消费者队列”。它把队列的 FIFO 思想放到了分布式环境下只是中间多了网络传输、持久化、副本复制这些包装。选型是很多团队头疼的事。我根据实际使用体验给你一张直白的对比表维度KafkaRabbitMQRocketMQ定位分布式日志/流处理管道灵活路由的消息中间件电商/金融场景的可靠消息系统吞吐量极高百万级/秒中等万级/秒高十万级/秒可靠性通过副本和 ISR 机制保证支持持久化、ACK、事务支持事务消息、延迟消息路由灵活性弱按 topic 消费强exchange routing key 灵活匹配中tag 过滤顺序消息分区内严格有序单队列有序多队列需自己控制队列内有序全局有序需设计社区生态非常活跃大数据生态标配老牌插件丰富阿里开源国内金融场景案例多每次有人问我“怎么选”我的答复都是先想清楚你的核心诉求是什么如果你的场景是日志采集、埋点、大数据管道追求的是高吞吐选 Kafka 几乎没错。如果业务系统路由复杂消息要按不同类型分发到不同消费者RabbitMQ 的 exchange 机制会让你舒服很多。如果消息不能丢、不能重复、甚至需要半事务机制比如订单和库存对账RocketMQ 的事务消息很有价值。还有一个绕不开的话题重复消费问题。消息队列大多保证 at least once也就是不丢但不保证不重复。消费者处理完消息后准备提交 offset结果进程崩溃再重启时消息被重新消费一遍——这种事太常见了。解决办法不是让消息队列“保证不重复”而是让消费者做到幂等用业务唯一 ID 去重比如订单号、流水号或处理前查一次 Redis 判断是否已处理或在数据库里建唯一索引。把重复消息变成可接受的比追求“绝对不重复”可靠得多。4.3 队列思想在任务调度与 AGV 调度中的延伸消息队列是显眼的例子还有一批不那么显眼、但同样到处是队列的场景。比如大模型调度平台里的任务队列。请求来了不是立刻执行而是进入待调度队列由调度器按照优先级、资源情况、超时时间统一分配。这里的队列往往不是普通 FIFO而是优先级队列或延迟队列高优先级任务插队到期未执行的任务被唤醒重排。JDK 的 PriorityBlockingQueue、DelayQueue 就是底层实现。AGV 调度系统也一样。一台自动导引车要完成搬运任务任务下发、路径申请、交通管制、状态上报全是一环扣一环的队列。AGV 的任务队列管理不好就会出现两车抢一条路、任务超时、电池耗尽却排不上充电任务的尴尬。技术栈的选择C 实时控制、Java/Go 后台调度、Web 前端监控可以五花八门但数据流的核心永远是对队列规则的把握。哪怕是最老派的集群调度系统管理员用 bqueues 查看作业队列权限本质也是维护一组“排队中的作业”和它们的调度策略。你看队列思想在工业软件里同样无处不在。5. 三个经典应用括号匹配、表达式求值与浏览器双栈5.1 括号匹配怎么写才不容易错栈的教科书级应用就是括号匹配。核心思路很简单遇到左括号([{压栈。遇到右括号弹栈并检查是否匹配。遍历完后栈必须为空。但实际写代码时有两个高频 bug一是遍历到右括号时根本没检查栈是否为空就直接 pop空栈 pop 导致崩溃二是遍历完了忘了检查栈空导致((()))这种合法串也放过。我见过很多人在白板上栽在这两个点上。def is_valid(s): stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) else: if not stack or stack.pop() ! pairs[ch]: return False return not stack为什么括号匹配天然适合栈因为“最近遇到的左括号必须最先被匹配”这个规则和栈的 LIFO 特性完全一致。嵌套结构越深越要靠栈把记忆一层层保存下来。5.2 中缀表达式转后缀一个栈如何完成优先级判断计算器实现是另一个经典的栈应用。人类习惯写中缀3 4 * 2但计算机更喜欢后缀3 4 2 * 因为后缀表达式求值不用处理括号和优先级。中缀转后缀的经典算法是用一个栈存运算符数字直接输出。遇到运算符时把栈顶所有“优先级不低于它”的运算符弹出再把它压栈遇到左括号直接压栈遇到右括号弹到左括号为止。这个过程最值得体会的一点是优先级本质上也是个“后进先出”问题。*先来后来但*必须先在表达式中出现所以*要比晚出栈。这就把“优先级判断”转化成了“出栈顺序判断”非常巧妙。求值同理用两个栈分别存操作数和运算符碰到运算符就弹两个操作数计算再压回去。整个计算器就没有任何魔法了全是栈的基本功。5.3 浏览器的前进后退为什么需要两个栈最后讲一个你每天都在用的场景浏览器后退按钮。想象一下你依次访问了 A、B、C 三个页面。正常情况下这像是一个栈A 在最底C 在最顶。点后退C 出栈到 B再点后退B 出栈到 A。但如果你后退到 B 之后又点击了一个新链接 D会发生什么C 还存在吗不会了。前进按钮会变灰C 被永久丢弃。这是为什么因为浏览器的导航记录是双栈结构后退栈存的是你一路浏览过来的页面。前进栈存的是你后退时弹出的页面。在 B 页点击新链接 D相当于入栈了一个新页面此时前进栈里的 C 被清空。所以后退栈为 [A, B, D]前进栈为空。这个机制保证了你的浏览历史永远是“一条链”不会出现“退回到一个已经不存在的世界”的怪异状态。编辑器的撤销/重做也是同一个套路撤销栈用来存操作记录重做栈在每次新操作时清空。所以你会在很多软件里发现做了新操作之后重做按钮就灰掉了。双栈或者说“历史-未来”模型是栈在交互系统里最优雅的应用之一。我一直建议把栈和队列当成“思维模型”来学而不是当成“容器”来背。遇到后进先出的场景第一反应是栈遇到先进先出的场景第一反应是队列遇到“既要队头淘汰、又要队尾插入”的滑动窗口场景第一反应是双端队列。有了这套反应你再看函数调用、线程池、消息队列、浏览器导航会发现它们全在同一个框架里只是穿了不同的外衣。数据结构学到这份上才算真正长进自己脑子里了。
