栈与队列完全指南：原理、代码实现与典型应用场景

如果不是为了应付考试或者面试题，你可能会觉得栈和队列这两兄弟实在太简单了：一个先进后出，一个先进先出，几行代码就能写完。但我在实际写代码的过程中越来越发现，真正会用栈和队列的人，和只会背概念的人，差距不在代码量，而在能不能把“约束”这两个字想透。

栈是一种后进先出（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 循环队列“浪费一个空间”的设计逻辑

循环队列是很多人第一次接触“取模运算”的地方。普通顺序队列的问题是这样的：数组 MaxSize=5，入队 a、b、c 后，front=0，rear=3；出队 a 后，front=1，rear=3；继续入队 d、e，rear 很快到达 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; } // 出栈：先取出，再 --top，value 通过指针带出 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 的循环队列。这里要特别留意：数组虽然开了 MaxSize=10，但实际最多只能存 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，就只出队不入队，相当于他出局了；直到队列只剩一个人。

我用 n=7、k=3 推一遍过程：初始 1 2 3 4 5 6 7；数到 3，3 出局；接着 4 5 6，6 出局；然后 7 1 2，2 出局；接着 4 5 7，7 出局；然后 1 4 5，5 出局；接着 1 4 1，1 出局；最终剩下 4。这个过程中，队列每一次“出队再入队”就是一次顺时针移动，和真实围圈报数完全对应。

这个例子特别能说明一个点：队列不只是“先来先服务”的通道，它还能模拟循环和轮转。操作系统里的时间片轮转调度，和这个思路一脉相承。

4.4 工程中的扩展形态：单调栈、双端队列与消息缓冲

学完基础版本，你会发现实际工程里有几种“变体”特别常见，面试和工作中都绕不开。

单调栈是指栈内元素保持单调递增或递减，常用于找数组中每个元素“左边/右边第一个比它大/小的位置”。它利用的是栈的 LIFO 回退特性：新元素入栈时不断弹出破坏单调性的旧元素，弹出的那一刻正好能确定旧元素的结果。经典问题如柱状图最大矩形、每日温度，思路都是这样。

双端队列（deque）允许两端入队和出队，C++ 的 std::deque、Java 的 ArrayDeque 都是现成实现。最经典的场景是滑动窗口最大值：维护一个双端队列，队头始终是当前窗口的最大值，新元素从队尾入队前先把队尾所有比它小的元素弹出。这个“从尾部淘汰”的操作普通队列做不到。

消息队列中间件则把队列的异步缓冲能力放大到了系统层面：生产者把任务投递到队列，消费者按顺序拉取处理，生产者不需要等待消费者。很多底层缓冲区的实现，核心就是一个环形队列，和你手写的循环队列几乎同构：写指针追读指针，满了就阻塞或者覆盖，判满判空逻辑完全一致。可以说，小到一块内存缓冲，大到分布式消息系统，队列都是基础设施。

5. 高频问题与排错技巧实录

5.1 判空判满：条件永远只有一行，但要理解为什么

我把栈和队列的判空判满条件整理成一张表，对照着记会非常清晰：

死记这些条件没有意义，关键要理解它们怎么来的。栈很简单：top 指向栈顶元素下标，空栈没有元素，所以 top 是 -1；数组最后一个下标是 MaxSize-1，top 到了那里说明装满。队列麻烦一点，但因为留了一个空位，所以满的条件是“rear 再走一步就到 front”。理解了这个逻辑，即使你忘了公式，也能现场推出来。

5.2 假溢出：顺序队列最经典的陷阱

假溢出是普通顺序队列特有的问题。假设 MaxSize=5，依次入队 a、b、c，此时 front=0，rear=3；出队 a，front 变成 1；继续入队 d、e，rear 一路走到 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 面试笔试易错点速查表

最后整理一份面试和笔试中高频出现的易错点，都来自我实际看到过的错误写法：

这里的“队列长度”公式我简单解释一下：因为 rear 绕回去之后可能数值上比 front 小，直接相减会得到负数，加上 MaxSize 再取模，就能得到实际元素个数。比如 MaxSize=10，front=8，rear=2，实际长度应该是 4（8、9、0、1 四个位置有数据），(2 - 8 + 10) % 10 = 4，正好对上。

就我个人而言，每次带新人或者做技术分享，我都喜欢让大家先把这段代码亲手敲一遍、把 top 和 rear 的变化过程画在纸上。因为这几行朴素的代码背后，是“约束操作位置以达到可预期行为”的工程思想。栈和队列教给你的不是两个 API，而是一种思维习惯：遇到需要回退、撤销、逆序处理的场景，栈往往是对的答案；遇到需要排队、缓冲、轮转、按序消费的场景，队列往往就在眼前。把这两兄弟理解透了，再看二叉树遍历、图的深度优先和广度优先搜索，你会觉得似曾相识，因为它们不过是栈和队列在不同的数据结构上的又一次应用。下次写代码之前，不妨先想一想：这个流程，是不是一个栈，或者一个队列？