数据结构这门课有个很典型的感受前面学顺序表、链表的时候你觉得是在学“怎么把数据存起来”存得整齐、找得快就行。但一学到栈和队列画风突然变了——同样是线性表它开始教你不允许随便存、不允许随便取。我第一次学到这里是有点懵的后来才想明白正是这种“受限”才让栈和队列成了后续所有复杂系统的地基。这篇笔记把栈和队列Stack Queue的核心内容整理一遍包括定义、顺序与链式实现、循环队列的判空判满、双结构互相转换以及它们在系统栈、表达式求值、线程池阻塞队列、消息队列里的真实形态。适合正在期末复习、备战考研408数据结构、或者想把初阶地基打牢的读者。1. 从线性表到“受限操作表”栈和队列的定位与直觉1.1 先回顾栈和队列仍然是线性表不管是考试还是写代码第一件事要清楚栈和队列都是线性表只是插入和删除的位置被严格限制了。线性表意味着元素之间有一对一的线性关系每个元素最多只有一个前驱和一个后继。我们前面学的顺序表、链表都是这种线性关系下的存储方式。而栈和队列的存储方式其实还是那两套——要么连续数组要么链表结点。真正新引入的是“规则”栈只允许在一端插入和删除这一端叫栈顶。队列只允许在一端插入队尾在另一端删除队头。教材把栈和队列放在线性表后面讲就是这个逻辑存储结构你已经见过了现在要给存储加上约束看加了约束之后能解决什么问题。1.2 栈的直觉叠盘子栈最经典的形象是叠盘子。一摞盘子你想拿只能拿最上面那个想放也只能放在最上面。于是先放进去的盘子被压在底下最后才能被拿到。栈的英文是Stack本身就是“一摞、一堆”的意思。后进先出也就是LIFOLast In First Out是栈最核心的语义。注意不是“后进后出”而是“后进先出”。这个顺序感很多人一开始会绕你就记住盘子的例子就够了最后放的盘子在最顶上所以最先拿走。1.3 队列的直觉奶茶店排队队列的直觉更简单就是排队。先到的人先买到奶茶后来的人只能排到队尾。先进先出FIFOFirst In First Out。队列的英文Queue本义就是“排队”。数据结构里说“入队”是Enqueue“出队”是Dequeue。这里我有一个记忆习惯看到Queue第一反应不是“队列”而是“排队”语义就不会错。1.4 为什么操作受限反而更有价值很多人第一次学这两个结构会反问线性表不是随便插随便删挺爽的吗为什么非要规定一头进一头出答案是现实中大量场景需要的就是“确定性”的规则。系统函数调用不可能从中间恢复现场只能沿调用顺序一层层弹回任务排队必须先进先出才能保证公平和顺序递归必须一层层返回后调用的先结束。自由插入删除虽然灵活但会让行为不可预测。“受限”不是限制你而是让数据流动变得可控。理解了这层后面学树的深搜广搜、图的遍历、操作系统里的系统栈、消息队列都会顺很多。2. 栈的代码细节顺序栈和链栈逐行拆解容易错的三个点2.1 顺序栈的结构定义与初始化初阶阶段栈最常用的实现是顺序栈。结构体里两个核心字段一个数组存数据一个top整型变量当栈顶指针。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针约定指向栈顶元素 } SqStack; // 初始化 void InitStack(SqStack *s) { s-top -1; }top初始化为-1还是0是一个经典的约定问题。如果top指向栈顶元素初始化为-1如果top指向栈顶元素的下一个空位初始化就是0。两种写法都能跑但所有操作必须保持一致。我个人推荐约定top指向栈顶元素初始化为-1。原因很简单空栈时找不到“栈顶元素”用-1表示“当前没有栈顶元素”非常直观。后面入栈出栈的代码写起来也对称。2.2 入栈出栈的边界细节核心操作就四个入栈、出栈、取栈顶、判空。bool StackEmpty(SqStack *s) { return s-top -1; } bool Push(SqStack *s, int x) { if (s-top MAXSIZE - 1) return false; // 栈满 s-data[(s-top)] x; return true; } bool Pop(SqStack *s, int *x) { if (s-top -1) return false; // 栈空 *x s-data[(s-top)--]; return true; } bool GetTop(SqStack *s, int *x) { if (s-top -1) return false; *x s-data[s-top]; return true; }注意入栈的写法是s-data[(s-top)] x先移动指针再放元素出栈是*x s-data[(s-top)--]先取元素再移动指针。这两个顺序如果写反就会出现“指针移到了没写过值的位置”或者“元素取到最后又白算一次”的问题。栈满的判断条件top MAXSIZE - 1也很容易写错。MAXSIZE是数组总长度合法下标是0到MAXSIZE-1当top走到MAXSIZE-1时最后一个位置已经存了数据不能再入了所以是满。2.3 链栈为什么头插头删就是栈链栈的本质是“用单项链表的头插和头删来实现栈”因为头插法和头删法操作的都是第一个结点天然就是栈顶。typedef struct StackNode { int data; struct StackNode *next; } StackNode, *LinkStack; void Push(LinkStack *s, int x) { StackNode *p (StackNode*)malloc(sizeof(StackNode)); p-data x; p-next *s; // 新结点指向原来的栈顶 *s p; // 新结点成为新栈顶 } bool Pop(LinkStack *s, int *x) { if (*s NULL) return false; *x (*s)-data; StackNode *p *s; *s (*s)-next; free(p); return true; }链栈不需要判满因为只要内存够就可以一直malloc新结点。这也是链栈和顺序栈最大的取舍点顺序栈操作快、缓存友好但容量固定链栈容量动态但要为每个结点附带一个next指针内存利用率略低。2.4 两个我见别人写过BUG的经典场景第一个BUG是链栈出栈时不保存待删除结点的指针// 错误示范 bool Pop(LinkStack *s, int *x) { *x (*s)-data; *s (*s)-next; // 原来的栈顶结点已经无指针指向了 // 但没有free内存泄漏 }初学C的人经常忘记free代码能跑但越跑内存越大。养成习惯出栈前先存下要释放的结点指针再移动栈顶指针最后free。第二个BUG是顺序栈扩容逻辑混乱。有人先判断栈满然后realloc扩大数组但扩容后又用原来的MAXSIZE去判断边界导致逻辑对不上。扩容后必须同步更新MAXSIZE否则下一次Push照样认为栈满。3. 队列的代码细节假溢出、循环队列与三种判空判满写法3.1 顺序队列的假溢出问题顺序队列最简单直观的实现是两个指针front指向队头元素rear指向队尾元素的下一个位置。初始frontrear0。入队就是q-data[q-rear] x出队就是x q-data[q-front]。问题来了front和rear都只增不减。入队出队几次之后rear可能已经到达数组末尾而数组前面还有大量空位。此时按“rear到了末尾”去判断队列满了但实际空间远没占满。这个现象叫“假溢出”。假溢出的本质是数组物理位置被单向使用了前面的空位无法复用。3.2 循环队列的模运算实现解法是用循环队列也就是在逻辑上把数组的头尾相接。rear到末尾后再入队就绕回下标0。核心操作是一个取模运算rear (rear 1) % MAXSIZE; front (front 1) % MAXSIZE;判断队列长度的公式也变化了length (rear - front MAXSIZE) % MAXSIZE;为什么要加MAXSIZE再取模因为rear可能已经绕到了front前面直接减出来是负数。加一圈再取模保证长度一定落在0到MAXSIZE-1之间。理解了这一个公式循环队列的大部分逻辑就通了。3.3 判空判满的三种方案对比循环队列里最大的坑是队空和队满时front都等于rear。因为空队列里两个指针指在一起满队列因为绕了一圈又指在一起。必须区分。第三种方案把“满”和“空”的定义分得很清楚但入队出队后要记得置tag工程上很少用面试里常拿来考概念。日常写代码我建议用第二种size计数因为最好读、最不容易错。考试写题优先第一种牺牲一个单元因为考得最多。3.4 链队列与循环队列的选择链队列用两个指针front指向队头结点rear指向队尾结点。入队是尾插出队是头删。typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; void EnQueue(LinkQueue *q, int x) { QNode *p (QNode*)malloc(sizeof(QNode)); p-data x; p-next NULL; if (q-rear NULL) { q-front q-rear p; // 第一个结点的特殊情况 } else { q-rear-next p; q-rear p; } }这里最容易被忽略的是“队列为空时入队要同时更新front和rear”以及“队列变空时要把rear也置为NULL”。否则会留下一个悬空指针下次入队时访问空指针崩溃。工程里能用循环队列就用循环队列因为在预分配好的数组上操作内存连续、缓存命中率高。链队列的优势是容量完全动态适合无法预知队列长度的场景。4. 用栈实现队列、用队列实现栈一题双解打通两个结构4.1 双栈模拟队列把“倒水”过程写清楚LeetCode 232是一道非常经典的题用两个栈实现队列。思路是两个栈分工inStack只负责入队outStack只负责出队。核心操作在出队如果outStack为空就把inStack里的元素全部倒进outStack。一次倒栈把LIFO反转成了FIFO。为什么两次LIFO等于FIFO你可以想象一个例子依次入栈1、2、3栈顶是3。把3、2、1依次弹出再压进另一个栈第二个栈栈顶变成1。此时从第二个栈弹出得到的就是1、2、3正好是入队顺序。这就是“正反两次”抵消了逆序。均摊复杂度是O(1)。每个元素最多被操作两次一次压入inStack一次从inStack倒到outStack。4.2 双队列模拟栈重点在出栈的搬移用两个队列模拟栈LeetCode 225。这次思路反过来了队列只允许队头出而栈要弹出的恰恰是最后进去的元素。做法是维护两个队列保留一个主队列存数据。出栈时把主队列里前n-1个元素转移到另一个队列剩下最后那个元素出队。下一次操作时两个队列的身份互换。这个操作的复杂度是O(n)因为每次出栈都要搬移几乎全部元素。和双栈模拟队列不同双队列模拟栈没法做到有效的均摊O(1)这也是这个题比232难理解的痛点。4.3 双解带给我们的启示这两个题写完能隐约感觉到一件事栈和队列虽然一个LIFO一个FIFO但底层都是线性结构只是操作规则不同。只要能控制好出入顺序就能互相模拟。这个思路在后面很有用。比如树的层序遍历用队列深搜可以用栈递归本质也是栈图的拓扑排序又用队列。它们不是孤立的两个知识点而是同一套线性思维在不同规则下的变体。5. 栈在系统里干活的细节栈帧形成、backtrace与表达式求值5.1 函数调用栈帧形成过程学到这里很多人才第一次意识到数据结构里的栈不只在教科书里编译器在真实运行时就给你用上了。每次函数调用都会在调用栈上分配一块区域叫栈帧Stack Frame里面存放参数、返回地址、局部变量、上一步的栈帧指针。一次函数调用的完整过程大致是调用者把实参压栈。压入返回地址也就是函数调用指令之后那条指令的地址。跳转到被调函数的入口。被调函数保存上一个栈帧的指针。移动栈顶指针为局部变量分配空间。执行函数体。将返回值写到指定位置。释放当前栈帧恢复上一个栈帧指针。取出返回地址跳回调用者。这个过程完美体现了栈的LIFO特性后调用的函数先返回。这也是为什么递归不能无限进行下去——每一层递归都会新增一个栈帧栈空间是有限的最终栈溢出错。5.2 backtrace栈回溯与局部变量、栈空间系统崩溃时打印出的调用栈就是backtrace栈回溯。它做的事情很简单但很有用沿着当前栈帧保存的“上一个栈帧指针”一条条往回走把整条调用链打出来。做崩溃分析时我们靠它定位是哪一层的哪个函数把问题踢过来的。热词里那句“C语言局部变量越少所占栈空间越小”也来自栈帧概念。每个局部变量都要占用当前栈帧里的空间数组变量尤其占地方。局部变量越多、越大当前栈帧就越宽栈消耗越快。但栈帧宽度不会无限增长操作系统给每个线程的栈是有限的默认几MB级别。这里有个面试高频题递归死循环为什么会栈溢出普通while死循环为什么是CPU跑满答案就是递归每层都新建栈帧栈空间有限普通循环不新增栈帧只是CPU原地打转。5.3 中缀转后缀与栈式求值表达式求值是栈的经典教材应用。我们平时写的3 4 * 2是中缀表达式但计算机不方便直接算因为要判断优先级和括号。更自然的处理形式是后缀表达式逆波兰式3 4 2 * 。中缀转后缀的规则操作数数字直接输出。遇到操作符与栈顶操作符比较优先级。如果栈顶优先级不低于当前操作符就把栈顶弹出输出直到栈顶优先级更低然后当前操作符入栈。左括号直接入栈遇到右括号弹出直到左括号左括号自己不入输出。后缀表达式求值则简单得多遇到数字压栈遇到操作符弹出两个数字做计算结果压栈。最后栈里剩下的就是表达式的值。这两个算法在手写代码题里出现频率非常高。初阶学习时不需要把算法背得多熟但要在纸上多走几遍把“栈顶永远是最紧急待处理的操作符”这个直觉建立起来。6. 队列在工程里扛事的细节线程池阻塞队列与消息队列选型避坑6.1 线程池的阻塞队列选择队列在工程里最典型的形态之一是线程池的任务队列。以Java的ThreadPoolExecutor为例它接收一个BlockingQueue来存放待执行任务。常见的选择有四种ArrayBlockingQueue有界数组队列容量固定队列满了就触发拒绝策略。LinkedBlockingQueue默认无界任务可以无限堆积但无界意味着内存可能被撑爆。SynchronousQueue不真正缓存任务生产者直接把任务交给线程适合任务量小但要求快速交接的场景。PriorityBlockingQueue支持按优先级出队。选型里最容易踩的坑是“无界队列看起来很安全”。因为线程池永远不会因队列满而拒绝任务表面上任务都收下了但如果生产速度长期大于消费速度任务会越来越多内存一点点耗尽。等到你发现内存告警已经很难收拾。工程上更推荐有界队列配合明确的拒绝策略让问题在早期暴露。6.2 消息队列重复消费问题与幂等设计消息队列听起来高级本质就是队列的分布式形态生产者把消息放到队尾多个消费者从队头拉取。Kafka、RabbitMQ、RocketMQ都是这个思路的变体。工程里最经典的坑是重复消费。为什么会重复因为很多消息队列提供“至少一次投递”的语义消费者处理完消息后还没来得及提交消费进度offset消费者就宕机了。消息会被重新投递于是同一业务被处理了两遍。解决重复消费的核心思路不是“让队列保证不重复”而是让消费者做到幂等——重复执行和一次执行结果相同。常见手段包括数据库唯一键约束、Redis的SETNX做去重标记、业务状态机判断等。这个道理和数据结构里的队列本身无关但当你真正理解FIFO和“消费进度”在队尾还是队头推进时看消息队列的文档不会发懵。6.3 消息队列选型Kafka、RabbitMQ、RocketMQ对比热词里有“kafka、rabbitmq、rocketmq消息队列选型实战对比与避坑指南”这个话题展开能写几万字。这里只从数据结构视角做一个粗对比帮初阶读者建立一个决策框架。项目KafkaRabbitMQRocketMQ核心特点高吞吐、分布式日志路由灵活、延迟低高吞吐事务消息典型场景日志收集、大数据流处理业务解耦、异步任务电商交易、订单状态流转消费顺序性一个分区内有序跨分区不能保证默认轮询消费需要额外设计支持顺序消息但吞吐会下降可靠性机制副本机制但重复消费需要幂等兜底消息确认机制完善事务消息重试机制选型最大的避坑点不要只盯吞吐量。Kafka吞吐虽高但跨节点动态扩缩容、消费进度管理都比较复杂RabbitMQ对路由和延迟控制更精细适合业务消息RocketMQ在事务消息和可靠性上更有优势适合对数据一致性要求高的业务。初阶读者不必纠结到底选谁只需要理解这些分布式消息系统最终解决的还是“生产者—队列—消费者”的结构问题FIFO、顺序性、重复消费这些概念都是队列语义在分布式环境下的扩展。6.4 单调队列滑动窗口最大值与优化DP的引子单调队列是队列的一个重要进阶用法也是最让我“开窍”的一个例子。它做的事情是在一个滑动窗口里快速求最值给定数组和窗口大小k求每个窗口的最大值。暴力法对每个窗口扫描k个元素复杂度O(nk)。单调队列能把复杂度降到O(n)。核心维护方法队头永远是当前窗口最大值的下标。新元素入队前从队尾弹出所有比它小的元素——因为它们既比新元素小又比新元素旧未来不可能再成为最大值。队头如果滑出窗口范围就弹出。队头对应的元素就是当前窗口最大值。这个例子的价值在于它证明了队列不仅能“存”数据还能通过加一点单调性规则来做优化。后面学动态规划时“单调队列优化DP”就是基于这个思路把某类DP的转移复杂度从O(n)降到O(1)。7. 把笔记真正变成自己的复习、实验报告与配套练习7.1 数据结构实验报告里的队列图解怎么做热词里有“链式队列入队与出队”“队列入队出队图解”“数据结构实验报告”。我批过不少初学者的实验报告发现扣分最多的不是代码而是没画状态图。写链队列的实验报告至少画三张图第一张初始空队列状态front和rear都为NULL队列头尾是两条独立的指针线。第二张入队三个结点后的状态画出三个结点方框结点的next箭头依次相连front指向第一个结点rear指向最后一个结点。第三张出队一个结点后的状态front移动到第二个结点被删结点用虚线或删除线标出说明内存被释放。画图的关键是让指针的“移动”有迹可循。不要只在文字里写“front指向下一个结点”要让图里清清楚楚看出前后变化。评卷老师看到这样的图基本不会扣分。7.2 期末复习与面试常见的栈队列考点期末和408最常考的栈队列考点我整理过一张表这里精简一下考点关键结论栈的LIFO特性递归、括号匹配、表达式求值都是栈队列的FIFO特性层序遍历、任务调度、消息队列循环队列判空判满三种方案必须会一种优先牺牲一个单元链队列边界处理空队入队要同时改front和rear用栈实现队列inStack/outStack双栈倒换用队列实现栈出栈时搬移前n-1个元素面试手写题的热门题目则包括括号匹配LeetCode 20、最小栈LeetCode 155、用栈实现队列LeetCode 232、用队列实现栈LeetCode 225、滑动窗口最大值LeetCode 239。7.3 配套练习建议刷题顺序建议按照“熟悉基本操作—掌握模拟转换—学会用栈队列解决实际问题”的节奏来。先做基础题把栈和队列的API用熟比如用数组手写一个栈、手写一个循环队列。然后做双栈模拟队列和双队列模拟栈这两题能把两个结构的语义差异理解得很透。最后再做括号匹配、最小栈、滑动窗口最大值这类应用题。平时上机时最好把每个操作的指针变化在纸上面画一遍尤其是循环队列里front和rear绕圈的过程。画完再看代码你会发现所有边界条件都变好懂了。学栈和队列最大的体会是它是少有的“学起来轻松但面试永远躲不掉”的内容。函数调用、表达式计算、线程池、消息队列全都在用它。复习到后期我养成一个习惯就是准备一页纸考点表把循环队列三种判满方式、链队列入队出队边界、双栈模拟队列的流程浓缩成半页考前扫一遍就能把整个章节的骨架恢复。别忘了这些结构真正的威力是到了后续树、图、操作系统里才会爆发出来的。
