如果不是为了应付考试或者面试题你可能会觉得栈和队列这两兄弟实在太简单了一个先进后出一个先进先出几行代码就能写完。但我在实际写代码的过程中越来越发现真正会用栈和队列的人和只会背概念的人差距不在代码量而在能不能把“约束”这两个字想透。栈是一种后进先出LIFO的线性结构队列是一种先进先出FIFO的线性结构这几乎是每个学过数据结构的人都能脱口而出的定义。可定义归定义真到用的时候很多人要么不知道该在什么场景选它们要么一写循环队列的判空判满就翻车。这篇内容我会把栈和队列从理论一层层剥到代码再把它们放到典型场景里看怎么用。无论你是刚开始学数据结构的初学者还是准备笔试面试的求职者都能从中拿到一套可以直接落地的东西而不只是一堆名词。1. 为什么栈和队列总是一起出现1.1 一个关键词受限线性表很多初学者会把栈和队列当成两个独立的数据结构来背其实它们本质上是同一个东西——线性表。所谓线性表就是元素排成一条线每个元素都有唯一的前驱和后继数组、链表都是线性表的具体存储形式。栈和队列也不例外它们同样是一串有序的元素存储方式也逃不开数组或链表区别只在于你只能在特定位置操作元素。这个“限制”并不是缺点反而是一种保护。以栈为例你只能在栈顶插入或删除栈底永远不动以队列为例你只能从队尾入、从队头出。这种约束带来了两个很大的好处第一操作边界清晰不容易出错第二行为是可以预测的调用方永远知道下一个被处理的是谁。工程上很多系统设计追求的就是这种“可预期”。浏览器历史记录为什么用栈因为它必须保证你点击后退时回到的是最近一次访问的页面而不是任意一个旧页面。打印机任务为什么用队列因为它必须保证先提交的文档先被打印大家按顺序来才显得公平。所以想理解栈和队列第一把钥匙就是它们不是独立的“新东西”而是“被约束了操作位置的线性表”。明白了这一点后面的原理和你自己动手实现都会顺畅很多。1.2 一条学习主线约束、实现、应用这篇文章的内容安排也是按这条主线走的先讲清楚栈和队列的约束规则再对比不同的底层实现方式然后给完整代码最后放入真实场景。如果你已经有一些基础可以直接跳到第 3 章看代码或者跳到第 4 章看应用如果你是纯新手建议按顺序读因为后面代码里的很多细节比如为什么循环队列要留一个空格、为什么出栈要把值通过指针带出来都依赖前面的原理解释。我特意用 C 语言写代码实现不是因为其他语言不行而是 C 最贴近内存和底层存储能清楚看到 top、front、rear 这些游标是怎么在数组上移动的。你用 Java、Python、Go 做同样的事逻辑完全一致只是语法不同。手写一遍这些结构比单纯调用语言内置的 Stack、Queue 接口理解深度完全不一样。2. 把底层机制看透LIFO 与 FIFO 是怎么运作的2.1 栈叠盘子模型理解栈最轻松的方式是想象厨房里叠盘子。你洗完一个盘子就往最上面放要用的时候也是从最上面拿后放上去的盘子一定最先被拿走。这就是“后进先出”。在代码里栈需要记录“最上面在哪里”这个位置称为栈顶top。栈底是固定不动的指针 top 会随着入栈、出栈不断变化。入栈时先把 top 加 1再把元素写进新位置出栈时先把 top 位置的元素取出来再把 top 减 1。这个顺序非常关键很多人写成先写再减或先加再读最后数组越界都找不到原因。栈顶初始值一般设为 -1表示空栈。为什么是 -1 而不是 0 因为如果是 0表示栈里已经有一个元素了和“空栈”矛盾。设成 -1 之后入栈先做 top第一个元素会落到下标 0既简洁又不会产生歧义。栈最典型的真实对应物是函数调用栈。程序每次调用一个函数都会把返回地址、局部变量等现场信息压入系统栈函数返回时再从栈顶弹出。递归为什么容易栈溢出因为每一层递归都对应一次压栈层数太多系统栈装不下。你平时写代码不会直接看到这个过程但它每时每刻都在发生这就是栈的价值——用来保存“现场”恢复“来时路”。2.2 队列排队模型队列对应的生活场景更简单食堂打饭。先来的人先打到饭后来的人排在队尾这就是“先进先出”。队列有两个口队头是出队方向队尾是入队方向。代码实现里front 指向队头元素的位置rear 指向队尾元素的下一个位置。入队时把元素写到 rear 指向的位置然后 rear 向后移一位出队时把 front 指向的元素取出来然后 front 向后移一位。这里有一个经典误区既然 rear 指向下一个空位那么初始时 front 和 rear 都应该是 0表示空队列。判断空队列用 front rear。队列解决的是“顺序公平”和“异步解耦”问题。操作系统里的进程调度、网络数据包缓冲、业务系统中的消息队列核心思想都是先进先出。它和栈恰好互补栈处理需要“后悔”和“回退”的场景队列处理需要“排队”和“按序消费”的场景。2.3 顺序存储和链式存储怎么选栈和队列既可以用数组实现顺序存储也可以用链表实现链式存储。很多初学者以为这是二选一的喜好问题实际上两者各有明确的适用条件对比项顺序存储数组链式存储链表空间来源创建时一次性分配固定大小每入栈/入队一个节点就动态申请空间上限有最大容量满了就不能再入理论上只受内存总量限制访问速度下标直接定位速度快每次操作都要移动指针稍慢内存利用率固定大小可能浪费按需分配但有额外的指针开销扩容方式需手动扩容或预先定大天然动态扩展具体到栈顺序栈用得多因为栈的操作只在栈顶数组实现的效率极高且栈的深度在很多场景可以预估。具体到队列事情就复杂一点如果用顺序数组但不做循环处理出队后前面留下的空位没法再利用产生“假溢出”。所以顺序队列几乎都会做成循环队列这也是后文代码的重点。链式队列适合长度动态变化大、无法预估上限的场景比如消息缓冲。2.4 循环队列“浪费一个空间”的设计逻辑循环队列是很多人第一次接触“取模运算”的地方。普通顺序队列的问题是这样的数组 MaxSize5入队 a、b、c 后front0rear3出队 a 后front1rear3继续入队 d、erear 很快到达 5数组末尾到了但下标 0、1 前面明明还有位置却无法再入队。这就是假溢出。解决办法是把数组想象成一个首尾相接的圆环rear 到达末尾后自动绕回开头也就是rear (rear 1) % MaxSize。取模让下标在 0 到 MaxSize-1 之间循环队列的容量就被完整复用起来了。但循环队列立刻带来一个新问题空队列时 front rear如果所有格子都装满rear 绕一圈追上 front也会出现 front rear。那怎么区分空和满经典做法是故意浪费一个存储空间当(rear 1) % MaxSize front时认为队列已满。也就是说数组中始终留一个空位让 rear 永远不直接追上 front。这样“空”和“满”的条件就分开了front rear 是空(rear 1) % MaxSize front是满。我也知道有的教材用 size 计数器区分空满这样空间利用率是 100%但需要额外维护一个变量每次入队出队都更新。核心思路没有区别你选择一种能理解透的即可。手写代码时我推荐先掌握留空法因为它能逼你把取模和环形移动练熟这也是很多面试官最想看到的。3. 完整代码实现从结构定义到运行测试3.1 动手写代码前的三个约定正式写代码之前先把三个约定说清楚后面所有代码都遵循它们。第一语言和容量。代码用 C 语言实现栈和队列的元素类型统一用 int最大容量用宏#define MaxSize 10定义。你如果想把元素类型换成结构体或字符串思路完全一样只是类型不同。第二接口风格。入栈/出栈、入队/出队的函数统一返回 bool成功返回 true失败返回 false。要带出的数据比如出栈的元素值通过指针参数传出。为什么这样做C 语言没有引用传递如果不通过指针带出数据你只能在函数内部打印外面拿不到结果如果不返回 bool栈空、栈满这类错误就没法被调用方感知。这个习惯真实生产代码都用得上。第三代码结构。栈和队列是两个独立的小程序每段代码都包含头文件、宏定义、结构体、所有函数和 main 测试直接复制就能编译运行。3.2 顺序栈完整代码下面的代码实现了一个容量为 10 的顺序栈包含初始化、判空、判满、入栈、出栈、取栈顶六个操作#include stdio.h #include stdlib.h #include stdbool.h #define MaxSize 10 typedef struct { int data[MaxSize]; int top; } SeqStack; // 初始化top 置为 -1表示空栈 void InitStack(SeqStack *s) { s-top -1; } bool StackEmpty(SeqStack *s) { return s-top -1; } bool StackFull(SeqStack *s) { return s-top MaxSize - 1; } // 入栈先 top再写入 bool Push(SeqStack *s, int value) { if (StackFull(s)) { printf(栈满无法入栈 %d\n, value); return false; } s-data[(s-top)] value; return true; } // 出栈先取出再 --topvalue 通过指针带出 bool Pop(SeqStack *s, int *value) { if (StackEmpty(s)) { printf(栈空无法出栈\n); return false; } *value s-data[(s-top)--]; return true; } // 只取栈顶元素不出栈 bool GetTop(SeqStack *s, int *value) { if (StackEmpty(s)) { printf(栈空无栈顶元素\n); return false; } *value s-data[s-top]; return true; } int main() { SeqStack s; InitStack(s); int val; Push(s, 1); Push(s, 2); Push(s, 3); if (GetTop(s, val)) { printf(当前栈顶元素: %d\n, val); } if (Pop(s, val)) { printf(出栈元素: %d\n, val); } if (Pop(s, val)) { printf(出栈元素: %d\n, val); } if (Pop(s, val)) { printf(出栈元素: %d\n, val); } if (Pop(s, val)) { printf(出栈元素: %d\n, val); } return 0; }注意Push和Pop都接收SeqStack *s指针而不是SeqStack s本身。这是 C 语言最容易踩的坑如果传值函数内部修改的只是副本外部的栈根本不会变化。后面我会专门讲这个问题。3.3 循环队列完整代码下面实现一个容量为 10 的循环队列。这里要特别留意数组虽然开了 MaxSize10但实际最多只能存 9 个元素因为要留一个空格来区分空和满。#include stdio.h #include stdlib.h #include stdbool.h #define MaxSize 10 typedef struct { int data[MaxSize]; int front; int rear; } SeqQueue; // 初始化front 和 rear 都指向 0 void InitQueue(SeqQueue *q) { q-front q-rear 0; } bool QueueEmpty(SeqQueue *q) { return q-front q-rear; } bool QueueFull(SeqQueue *q) { return (q-rear 1) % MaxSize q-front; } // 入队写入 rear 位置再让 rear 前进一格 bool EnQueue(SeqQueue *q, int value) { if (QueueFull(q)) { printf(队列已满无法入队 %d\n, value); return false; } q-data[q-rear] value; q-rear (q-rear 1) % MaxSize; return true; } // 出队读取 front 位置再让 front 前进一格 bool DeQueue(SeqQueue *q, int *value) { if (QueueEmpty(q)) { printf(队列为空无法出队\n); return false; } *value q-data[q-front]; q-front (q-front 1) % MaxSize; return true; } // 取队头元素不出队 bool GetHead(SeqQueue *q, int *value) { if (QueueEmpty(q)) { printf(队列为空无队头元素\n); return false; } *value q-data[q-front]; return true; } int main() { SeqQueue q; InitQueue(q); int val; EnQueue(q, 10); EnQueue(q, 20); EnQueue(q, 30); if (GetHead(q, val)) { printf(当前队头元素: %d\n, val); } if (DeQueue(q, val)) { printf(出队元素: %d\n, val); } if (DeQueue(q, val)) { printf(出队元素: %d\n, val); } if (DeQueue(q, val)) { printf(出队元素: %d\n, val); } if (DeQueue(q, val)) { printf(出队元素: %d\n, val); } return 0; }这段代码里最核心的就是QueueFull里那行(q-rear 1) % MaxSize q-front。每次入队后 rear 都指向下一个空位如果下一个空位正好是 front说明前面没有剩余空间了队列已经满。这就是循环队列的灵魂理解它比背代码重要得多。3.4 测试结果分析把上面两个程序分别编译运行预期输出是栈测试输出 当前栈顶元素: 3 出栈元素: 3 出栈元素: 2 出栈元素: 1 栈空无法出栈 队列测试输出 当前队头元素: 10 出队元素: 10 出队元素: 20 出队元素: 30 队列为空无法出队从输出可以直观看到两者行为完全不同栈按“后进先出”弹出3 最后进入却最先出来队列按“先进先出”消费10 最早进入也最早出来。代码最后都故意触发了一次失败操作分别打印“栈空”和“队列为空”这说明接口返回 bool 的正确用法——调用方可以根据返回值决定下一步逻辑而不是让程序崩溃。3.5 链式版本实现差异与选择建议我在这里不贴完整的链式代码了但把关键差异讲透你就能随时写出来。链栈本质是单链表只做头插和头删top 指针就是链表的头指针。入栈时malloc一个新节点把 next 指向当前 top再更新 top出栈时保存 top 的值top 后移再释放原头节点。链栈不需要判满因为内存是动态分配的只在malloc失败时无法入栈。链队需要维护两个指针front 指向头节点rear 指向尾节点。入队用尾插法出队删除头节点。这里有一个很容易漏掉的操作如果出队后队列变空rear 也要置为 NULL否则 rear 变成野指针下一次入队会直接崩溃。我在实际调试中见过不少初学者在这里翻车。选型建议很简单如果数据量可预估、追求速度、代码逻辑越简单越好用顺序版本如果数据量波动很大、无法提前确定上限或者需要频繁创建多个队列实例用链式版本。4. 从课堂例题到真实业务典型应用实战4.1 括号匹配栈的“消除配对”思想括号匹配是栈最经典的入门应用。思路非常直观遍历字符串遇到左括号(、[、{就入栈遇到右括号)、]、}就从栈顶弹出一个括号检查是否配对。如果栈在错误时机为空或者弹出的左括号与当前右括号不匹配直接返回 false最终遍历完栈还必须为空。道理说起来简单但它的本质是“用栈保存最近出现的待匹配符号”。为什么必须用栈因为最近出现的左括号必须和最靠近它的右括号配对这正是 LIFO 的语义。我用前面的顺序栈写了一个可运行版本bool IsBalanced(const char *str) { SeqStack s; InitStack(s); for (int i 0; str[i] ! \0; i) { if (str[i] ( || str[i] [ || str[i] {) { Push(s, str[i]); } else if (str[i] ) || str[i] ] || str[i] }) { if (StackEmpty(s)) { return false; } int top; Pop(s, top); if ((str[i] ) top ! () || (str[i] ] top ! [) || (str[i] } top ! {)) { return false; } } } return StackEmpty(s); }比如测试字符串({[]})整个过程栈的变化是入(入{入[遇到]弹出[匹配遇到}弹出{匹配遇到)弹出(匹配最后栈空返回 true。你可以看到这个“最近匹配”的过程和栈的后进先出天然一致。4.2 表达式求值两个栈搞定中缀转后缀计算机计算3 4 * 2时并不像人脑那样天然知道先算乘法。中缀表达式对人类友好但对计算机不友好更常用的是把它转成后缀表达式逆波兰式比如3 4 2 * 再用一个栈求值。中缀转后缀的规则用栈来维护运算符数字直接输出遇到运算符时如果栈为空或当前运算符优先级高于栈顶则入栈否则弹出栈顶运算符并输出直到当前运算符优先级更高。遇到左括号入栈遇到右括号则将栈内运算符弹出直到左括号。整个过程中栈起到了“暂存还不能处理的运算符”的作用。后缀表达式求值更简单遍历后缀式是数字就入栈是运算符就弹出两个操作数先弹出的是右操作数后弹出的是左操作数计算后把结果压回栈。遍历结束栈中唯一的数字就是答案。这里栈承担了“保存中间结果”的任务每一步计算的结果都要落回栈里等着和后续结果继续运算。这两个阶段是栈在计算领域最深刻的应用。你在很多编译原理、计算器实现里看到的东西本质上就是这两个流程。4.3 约瑟夫环用队列模拟循环游戏约瑟夫环的问题背景是n 个人围成一圈从第一个人开始报数报到 k 的人出局剩下的人继续从 1 开始报数直到只剩一人。用队列模拟这个“圆圈”非常自然所有人按编号依次入队循环里从队头取一个人如果没报到 k就立刻出队再从队尾入队相当于这个人还没出局只是走到了队伍末尾如果报到 k就只出队不入队相当于他出局了直到队列只剩一个人。我用 n7、k3 推一遍过程初始 1 2 3 4 5 6 7数到 33 出局接着 4 5 66 出局然后 7 1 22 出局接着 4 5 77 出局然后 1 4 55 出局接着 1 4 11 出局最终剩下 4。这个过程中队列每一次“出队再入队”就是一次顺时针移动和真实围圈报数完全对应。这个例子特别能说明一个点队列不只是“先来先服务”的通道它还能模拟循环和轮转。操作系统里的时间片轮转调度和这个思路一脉相承。4.4 工程中的扩展形态单调栈、双端队列与消息缓冲学完基础版本你会发现实际工程里有几种“变体”特别常见面试和工作中都绕不开。单调栈是指栈内元素保持单调递增或递减常用于找数组中每个元素“左边/右边第一个比它大/小的位置”。它利用的是栈的 LIFO 回退特性新元素入栈时不断弹出破坏单调性的旧元素弹出的那一刻正好能确定旧元素的结果。经典问题如柱状图最大矩形、每日温度思路都是这样。双端队列deque允许两端入队和出队C 的 std::deque、Java 的 ArrayDeque 都是现成实现。最经典的场景是滑动窗口最大值维护一个双端队列队头始终是当前窗口的最大值新元素从队尾入队前先把队尾所有比它小的元素弹出。这个“从尾部淘汰”的操作普通队列做不到。消息队列中间件则把队列的异步缓冲能力放大到了系统层面生产者把任务投递到队列消费者按顺序拉取处理生产者不需要等待消费者。很多底层缓冲区的实现核心就是一个环形队列和你手写的循环队列几乎同构写指针追读指针满了就阻塞或者覆盖判满判空逻辑完全一致。可以说小到一块内存缓冲大到分布式消息系统队列都是基础设施。5. 高频问题与排错技巧实录5.1 判空判满条件永远只有一行但要理解为什么我把栈和队列的判空判满条件整理成一张表对照着记会非常清晰结构判空判满顺序栈top -1top MaxSize - 1循环队列front rear(rear 1) % MaxSize front链栈top NULL不需要链队front NULL 或 front rear不需要死记这些条件没有意义关键要理解它们怎么来的。栈很简单top 指向栈顶元素下标空栈没有元素所以 top 是 -1数组最后一个下标是 MaxSize-1top 到了那里说明装满。队列麻烦一点但因为留了一个空位所以满的条件是“rear 再走一步就到 front”。理解了这个逻辑即使你忘了公式也能现场推出来。5.2 假溢出顺序队列最经典的陷阱假溢出是普通顺序队列特有的问题。假设 MaxSize5依次入队 a、b、c此时 front0rear3出队 afront 变成 1继续入队 d、erear 一路走到 5到达数组末尾。此时队列实际还有下标 0 是空的但因为 rear 已经到了数组边界按固定顺序写不进去了这就是“假溢出”——有空间却用不上。初学者第一反应可能是“把整个数组往前搬”也就是出队后把所有元素左移一位。这样做功能上可以但出队时间复杂度从 O(1) 变成 O(n)队越长越慢。正确解法只有两个一是用循环队列让 rear 绕回开头二是一开始就选择链式队列。理解了假溢出的成因你就明白为什么教材一讲顺序队列就必讲循环队列。5.3 指针传参C 语言实现时的第一大坑我在指导别人写栈和队列代码时遇到最多的问题不是逻辑问题而是“函数运行了但我打印栈还是空的”。十有八九是把Push(SeqStack *s, int value)写成了Push(SeqStack s, int value)。C 语言函数参数是按值传递的。SeqStack s会在函数内部生成一个副本你对副本做的任何修改都不会影响 main 函数里的原变量。只有传入地址s函数内部通过s-top操作才能真正改到结构体。出栈函数Pop(SeqStack *s, int *value)里int *value也是一样的道理栈顶值要通过指针带出否则你在函数里取出来的数据外面接收不到。还有一个容易被忽略的习惯出栈、出队函数的返回值不要设计成 void。虽然测试代码里可能只想打印一个值但生产环境里调用方必须知道操作是成功还是失败。返回 bool把数据用指针带出是更安全、更工程化的接口设计。5.4 面试笔试易错点速查表最后整理一份面试和笔试中高频出现的易错点都来自我实际看到过的错误写法易错场景错误写法正确写法原因栈初始化top 0top -1top0 意味着已有元素空栈语义错误入栈顺序data[top] xdata[top] x第一个元素必须先移动到下标 0出栈顺序x data[--top]x data[top--]top 指向的是当前元素不是下一格循环队列判满rear 1 front(rear 1) % MaxSize frontrear 绕回开头后是 0不取模会漏判队列长度rear - front(rear - front MaxSize) % MaxSize环形场景中 rear 可能小于 front修改结构体传值传参传地址传参C 语言值传递修改不了外层变量链队删除只更新 front若队列变空还需置空 rear否则 rear 变野指针这里的“队列长度”公式我简单解释一下因为 rear 绕回去之后可能数值上比 front 小直接相减会得到负数加上 MaxSize 再取模就能得到实际元素个数。比如 MaxSize10front8rear2实际长度应该是 48、9、0、1 四个位置有数据(2 - 8 10) % 10 4正好对上。就我个人而言每次带新人或者做技术分享我都喜欢让大家先把这段代码亲手敲一遍、把 top 和 rear 的变化过程画在纸上。因为这几行朴素的代码背后是“约束操作位置以达到可预期行为”的工程思想。栈和队列教给你的不是两个 API而是一种思维习惯遇到需要回退、撤销、逆序处理的场景栈往往是对的答案遇到需要排队、缓冲、轮转、按序消费的场景队列往往就在眼前。把这两兄弟理解透了再看二叉树遍历、图的深度优先和广度优先搜索你会觉得似曾相识因为它们不过是栈和队列在不同的数据结构上的又一次应用。下次写代码之前不妨先想一想这个流程是不是一个栈或者一个队列