“队列和栈”这几个字在很多人的记忆里是大学《数据结构》课第二章的内容考试背一背概念、画一画出入队流程图就过去了。但真到了实际写代码的时候你会发现这两个“最简单的结构”反而是最容易出问题的地方循环队列的边界算错、std::queue 取 front 之前没判空、单调栈的思路半天绕不出来、线程池里的阻塞队列不知道选有界还是无界……我之前带过的不少同学一说队列栈就觉得“这有什么好学的”一动手就翻车。这篇文章我想把 C 环境下队列和栈的关键知识点一次性捋清楚从手写实现到 STL 容器适配器从单调栈算法到生产环境里的阻塞队列。既照顾刚开始学数据结构的新手也适合准备算法面试或者想夯实基础的开发者。读完你至少能收获三样东西闭着眼睛能写对循环队列、能独立推导单调栈解决“下一个更大元素”类问题、能说清楚工程里各种“队列”变体背后的取舍逻辑。里面所有代码你都可以直接拿去做实验、写数据结构的课设或者塞进自己的工具库里。1. 队列和栈到底在解决什么问题1.1 先给“顺序”下定义FIFO 与 LIFO队列queue和栈stack都属于线性表它们的区别不在存储形态而在元素的访问顺序。队列是先进先出FIFO, First In First Out像食堂排队打饭先到的人先打到饭后到的人排在队尾。栈是后进先出LIFO, Last In First Out像一摞盘子你总是先拿最上面那个后放上去的盘子。这个顺序规则看起来简单但它直接决定了这两类结构在系统设计里的分工。函数调用为什么用栈不用队列因为函数嵌套调用时最后被调用的函数最先返回这种天然的“后进先出”恰好和栈吻合。操作系统的打印任务为什么用队列因为打印任务应该按照提交的顺序排队执行先提交的先打印这就是“先进先出”。可以说队列强调的是“公平与先后”栈强调的是“现场与回溯”一个面向流水线一个面向嵌套过程。1.2 两类结构的操作集合不管是手写还是用 STL队列和栈暴露给外界的核心操作就那么几个。我把它们列成一张表方便和后面的代码对照操作队列栈插入push队尾入队push压栈删除pop队首出队pop弹栈读取下一元素front()队首top()栈顶判空empty()empty()元素个数size()size()注意一个细节栈读的是 top队列读的是 front而出队/弹栈操作往往不返回被移除的元素要先取值、再删除。这个“两步操作”的设计习惯很多新手刚用 std::queue 时不适应后面我会专门讲。1.3 衡量一个数据结构好不好看三件事我评价队列栈实现的好坏一般看三个维度单次操作的时间复杂度、空间占用、以及代码的边界处理是否稳健。时间复杂度数组实现的队列和栈push/pop 都是 O(1)数组扩容逻辑均摊也是 O(1)链表实现同样 O(1)。空间占用数组是一整块连续内存缓存友好链表每个节点多一个 next 指针还会产生内存碎片。边界处理是否处理了空结构访问、容量满、扩容失败这些情况。笔试和面试里数组实现队列的边界条件恰恰是重灾区。搞清楚了这三点你会发现“数据结构与算法”不是背代码而是做取舍。下面从手写实现开始讲因为只有亲手写过一遍你才能真正理解 STL 里那些容器适配器为什么要那样设计。2. 手写队列和栈数组和链表两条路都走一遍2.1 数组实现栈最简单的版本栈用数组实现是所有数据结构里最直白的一个。维护一个 topIndex初始为 -1push 时先 topIndex 再赋值pop 时直接 --topIndex逻辑上把元素“丢弃”。templatetypename T class Stack { private: T* data; int capacity; int topIndex; public: explicit Stack(int cap) : capacity(cap), topIndex(-1) { data new T[capacity]; } ~Stack() { delete[] data; } bool push(const T value) { if (topIndex capacity - 1) return false; // 栈满 data[topIndex] value; return true; } bool pop() { if (empty()) return false; // 栈空 --topIndex; return true; } T top() { return data[topIndex]; } bool empty() const { return topIndex -1; } int size() const { return topIndex 1; } };有几个细节值得说top() 返回引用方便直接修改栈顶元素push 和 pop 用 bool 返回值表示成功与否而不是抛异常是为了在某些高性能场景避免异常开销。实际开发里我更推荐用 std::vector 代替裸数组里边的 top() 直接对应 back()push 对应 push_back()扩容问题 vector 帮你解决裸 new[] 还得自己写扩容逻辑很容易写出内存泄漏。2.2 数组实现队列循环队列才是正确的打开方式如果用普通数组实现队列队首出队后 frontIndex 不断后移数组前面空出来的位置永远用不上空间利用率越来越低。所以用数组实现队列的标准做法是循环队列ring buffer把数组看成一个首尾相接的环通过取模运算让 frontIndex 和 rearIndex 在数组范围内循环。templatetypename T class CircularQueue { private: T* data; int capacity; int frontIndex; int rearIndex; int count; public: explicit CircularQueue(int cap) : capacity(cap), frontIndex(0), rearIndex(0), count(0) { data new T[capacity]; } ~CircularQueue() { delete[] data; } bool enqueue(const T value) { if (count capacity) return false; // 队满 data[rearIndex] value; rearIndex (rearIndex 1) % capacity; count; return true; } bool dequeue() { if (count 0) return false; // 队空 frontIndex (frontIndex 1) % capacity; --count; return true; } T front() { return data[frontIndex]; } bool empty() const { return count 0; } bool full() const { return count capacity; } int size() const { return count; } };这里我特意用 count 记录元素个数而不是靠 rearIndex frontIndex 判空、靠 (rearIndex 1) % capacity frontIndex 判满。原因是用“牺牲一个存储单元”的方式区分队空和队满代码更绕还会让实际可用容量变成 capacity - 1很多《数据结构实验报告》里写的版本就是这么实现的看着精妙实战里反而容易把自己绕晕。维护一个 count判断逻辑直接读着就是人话。关键的点入队时先赋值再移动 rearIndex出队时先取数据再移动 frontIndex取模用的是 capacity 而不是 capacity 1别搞混。如果你想加深印象可以玩一个经典题设计一个支持 front、rear、enQueue、deQueue、isEmpty、isFull 的循环队列题目通常会要求用“牺牲一个槽位”的写法这正好能让你对比出两种写法的差异。2.3 链表实现什么时候选它链表实现的队列和栈核心思路是用头节点和尾节点维护链。以队列为例struct Node { int val; Node* next; explicit Node(int v) : val(v), next(nullptr) {} }; class LinkedQueue { private: Node* head; Node* tail; public: LinkedQueue() : head(nullptr), tail(nullptr) {} ~LinkedQueue() { while (head) { Node* tmp head; head head-next; delete tmp; } } bool empty() const { return head nullptr; } void push(int value) { Node* node new Node(value); if (tail) { tail-next node; tail node; } else { head tail node; } } bool pop() { if (!head) return false; Node* tmp head; head head-next; if (!head) tail nullptr; // 删的是最后一个节点 delete tmp; return true; } int front() const { return head-val; } };链表的优势是不需要预先分配容量也不存在扩容时的数据搬运劣势是每个节点都要 new/delete时间复杂度虽然仍是 O(1)但常数很大而且节点在内存里分散缓存不友好。我在实际项目里的经验是明确知道数据规模上限、对性能敏感的场景优先用数组或 vector数据量不确定、频繁增删但又不想考虑扩容的场景才用链表。这里有一个很容易被忽略的 bugpop 删除最后一个节点时一定要把 tail 置空。如果忘了下一次 push 时 tail 还指向已释放的内存写起来就是悬垂指针崩溃。我见过不止一个同学在这翻车排查半天发现是析构或者删除逻辑的问题。2.4 一个共通的实现技巧不管数组还是链表我建议把所有容器类的“判空”“判满”“求 size”都写成 const 成员函数并且在 push/pop 之前统一做合法性检查。这种防御式写法的好处是调用方即使忘了判空顶多遇到固定返回 false 的 pop而不是对空容器取 front/top 导致未定义行为。如果你想在自己电脑上跑这些代码VS Code 里配好 C/C 环境新建一个 cpp 文件用 g 编译时记得加 -stdc17。上面这些类不依赖任何第三方库直接编译就能跑拿来做数据结构的实验报告核心代码再合适不过。3. std::queue 和 std::stack先说清楚它俩的底层设计逻辑3.1 容器适配器到底是什么C STL 里的 std::queue 和 std::stack准确叫法是“容器适配器container adapter”。它们本身不管理内存而是在一个底层容器之上把接口裁剪成队列/栈的语义。默认底层容器是 std::deque你也可以显式指定 std::list 或 std::vectorstd::queueint, std::dequeint q; // 默认底层容器 std::queueint, std::listint ql; // 用链表作为底层 std::stackint, std::vectorint st; // 栈用 vector 很常见为什么要设计成适配器而不是让 queue 直接继承 vector因为队列要限制“只能队尾进、队首出”如果直接暴露 vector 的迭代器、随机访问接口使用者就能任意操作内部元素破坏队列的封装语义。适配器把接口收窄安全性就上来了。这是接口隔离的思想学数据结构的时候顺便理解这一层再看源码就不会觉得奇怪了。3.2 常用操作和复杂度操作std::queuestd::stack复杂度入队/压栈pushpushO(1) 均摊出队/弹栈poppopO(1)读首元素fronttopO(1)读尾元素back无O(1)判空emptyemptyO(1)长度sizesizeO(1)用起来代码很短#include queue #include stack std::queueint q; q.push(1); q.push(2); int x q.front(); // x 1 q.pop(); std::stackint st; st.push(10); st.push(20); int y st.top(); // y 20 st.pop();这里有个很多新手会犯的错std::queue 的 pop 不返回被弹出的元素。你要先 front() 取值再 pop() 删除。刚用 C 写队列时我老是习惯性地想写 int x q.pop()编译不过才反应过来。这个设计是为了避免返回引用后元素被立刻销毁产生悬垂引用属于 C 里“宁可多写一步也要保证安全”的理念。3.3 容易被忽略的三个使用细节第一swap 交换两个队列是 O(1) 的直接 q1.swap(q2) 就行等价于交换底层容器指针后面“两个队列实现栈”就会用到。第二std::queue 的 back() 可以读队尾元素这个接口不是所有人都知道。某些“用队列维护滑动窗口”的场景需要同时看队首和队尾back() 很方便。第三存自定义类型时要小心对象切割。适配器只负责把对象当作 T 存如果你用继承体系记得存基类指针而不是值否则派生类部分会被切掉。这是 C 所有容器通用的坑队列栈也不例外。4. 单调栈把 O(n²) 暴力优化成 O(n)4.1 一句话理解单调栈单调栈就是栈中元素从栈底到栈顶保持单调递增或单调递减。它解决的问题有一个共同模式找每个元素左边/右边第一个比它大/小的元素。这类问题最直观的暴力做法是双重循环 O(n²)单调栈可以压到 O(n)。为什么单调栈能做到 O(n)关键在于每个元素最多入栈一次、出栈一次所以虽然看起来有 while 循环但总操作次数是 O(n)。这一条几乎所有的题解都会算但我要补充一个更重要的理解角度单调栈的 while 弹出操作本质上是在“结算”。每次弹栈都是给被弹出的元素找到了答案所以它只弹一次后续再也不用回头扫描。4.2 下一个更大元素从暴力到单调栈看一下经典的“下一个更大元素”问题给一个数组 nums返回等长数组 result其中 result[i] 表示 nums[i] 右边第一个比它大的元素不存在则填 -1。暴力解法很直白对每个 i从 i1 往后扫找到第一个更大的复杂度 O(n²)。单调栈的思路反过来从左到右遍历数组时把“还没找到答案的下标”压进栈当新元素比栈顶元素大时说明新元素就是栈顶元素要找的“下一个更大元素”于是弹出栈顶记录答案继续比较新的栈顶。因为栈里从底到顶是单调不增的所以每个元素一旦被弹出答案就确定了。vectorint nextGreaterElement(const vectorint nums) { int n nums.size(); vectorint result(n, -1); stackint st; // 存下标栈内元素对应值从栈底到栈顶单调递减 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { result[st.top()] nums[i]; // nums[i] 是栈顶的下一个更大元素 st.pop(); } st.push(i); } return result; }手动跑一遍就通了。数组 [2, 1, 4, 3]i0栈空压入 0i1nums[1]1 不大于 nums[0]2压入 1栈内为 0,1对应值 2,1单调递减i2nums[2]4 大于 nums[1]1弹出 1result[1]44 还大于 nums[0]2弹出 0result[0]4然后压入 2i3nums[3]3 不大于 nums[2]4压入 3遍历结束栈里剩 2,3对应答案都是 -1。最终 result [4, 4, -1, -1]。整个过程里每个下标只压栈一次、弹栈一次总复杂度 O(n)。4.3 单调栈的四个方向变体和经典变形单调栈不只是“右边第一个更大”一共有四个方向左边/右边 × 更大/更小。写的时候只要调整遍历方向和比较符号即可但有几类更隐蔽的变形环形数组题目里说数组首尾相连要找的“下一个”可以绕回开头。常见处理是遍历 2n 个位置用 i % n 映射下标栈里仍然存下标。这样每个元素最多多被比较一轮复杂度仍然是 O(n)。求“到更大元素的距离”比如找每个元素到右边第一个更大元素的距离其实上一个问题解出 result 数组后距离就是下标差所以栈里存下标而不是值这一步就顺理成章。接雨水、柱状图中最大的矩形这两个是单调栈的经典应用题核心都是维护单调性在弹栈时根据栈内相邻柱子的信息计算面积或容量。其中柱状图最大矩形需要在数组末尾补一个 0 做“哨兵”逼出所有剩余柱子的结算。这类题我建议单独刷 5~10 道吃透比盲目刷一百道有效得多。关于单调栈我最想分享的心得是不要死记模板。拿到题先问自己两个问题——“我在找左边还是右边的更大/更小元素”“比较结果是严格大于还是大于等于”这两个答案定了while 里的比较符号和压栈时机就定了。这句话帮我解决了 90% 的单调栈题目。5. 从教材到生产阻塞队列、线程池和消息队列里的取舍5.1 阻塞队列把“取不到数据”变成“等待数据”教材里的队列出队时如果为空返回失败。但生产环境里生产者消费者模型要求消费者在队列为空时“等一会儿”而不是立即失败或忙轮询。阻塞队列就是在队列上加了等待/唤醒语义。C 里可以用 std::mutex 配合 std::condition_variable 实现一个最简单的有界阻塞队列templatetypename T class BlockingQueue { private: std::mutex mtx; std::condition_variable notEmpty; std::condition_variable notFull; std::queueT data; size_t capacity; public: explicit BlockingQueue(size_t cap) : capacity(cap) {} void push(const T item) { std::unique_lockstd::mutex lock(mtx); notFull.wait(lock, [this] { return data.size() capacity; }); data.push(item); notEmpty.notify_one(); } T pop() { std::unique_lockstd::mutex lock(mtx); notEmpty.wait(lock, [this] { return !data.empty(); }); T item data.front(); data.pop(); notFull.notify_one(); return item; } };注意 wait 的第二个参数是谓词用于处理“虚假唤醒”。这是多线程编程里必讲的话题操作系统唤醒等待线程时可能因为信号量内部实现而出现没有实际数据的情况所以必须在被唤醒后重新检查条件。如果直接用 if 判断条件就去睡觉高并发下会偶现“取出不存在元素”的 bug。谓词写法会自动用 while 循环重新检查这正是“阻塞队列”工程实现的精髓。5.2 线程池里的阻塞队列怎么选线程池的任务队列本质上就是一个阻塞队列工程上的选择主要围绕两个问题有界还是无界多个消费者竞争时是否公平无界队列任务可以无限堆积线程池队列永不拒收但内存会被任务堆满系统可能被拖垮适合任务规模可控的内部系统。有界队列队列满时生产者可以选择阻塞、丢弃、抛异常或执行拒绝策略能保护系统本身在高并发服务里几乎是必选。公平性如果多个生产者和消费者竞争同一个队列是否按先到先得处理。C 标准库里没有直接的公平阻塞队列当你需要严格公平时要注意锁的实现和唤醒顺序必要时可以把单个粗锁拆成细粒度控制。我在生产环境里的习惯是流量平稳的服务用有界队列容量给到日常峰值的 2~3 倍配好拒绝策略流量抖动大且内存充足的后台批处理系统才考虑无界队列。这个选择本质上是“可用性优先”和“稳定性优先”之间的取舍没有绝对答案所以面试官特别爱问。5.3 消息队列里的“重复消费”问题端上幂等才是解药分布式消息队列里的队列概念跟进程内队列不完全一样但它同样遵循先进先出的消息顺序约束并且有一个常见工程问题是“重复消费”消费者处理完消息后在提交消费位点之前宕机重启后消息会被重新投递或者生产者发送时超时重试产生了重复消息。要解决它单靠消息队列本身很难做到严格一次业界通用的做法是“业务幂等 消息去重”幂等消费逻辑对同一条消息执行多次结果和只执行一次相同比如数据库里根据唯一键做 insert-on-duplicate。去重在消费端维护一个消息 ID 的判重集合处理前先查、处理后标记配合过期清理控制集合大小。这个地方其实用的还是队列 FIFO 的思想消息按顺序进入处理管道但“成功标记”和“业务操作”必须保证原子性或可恢复性否则顺序会在乱序重试中被破坏。6. 高频考点与踩坑记录把这些坑提前踩一遍6.1 空容器访问最常见的未定义行为std::queue 的 front()、std::stack 的 top() 在容器为空时属于未定义行为程序可能返回垃圾值、可能崩溃、也可能“碰巧正常”。我调试过不少线上崩溃最终定位都是某个并发路径下队列被消费空了取 front 时没判 empty。规范做法是先 empty() 再访问或者依赖代码里自带的 bool 返回值判断 push/pop 是否成功。一句话所有的 pop 之前都要先问自己“我能保证它非空吗”。6.2 循环队列边界capacity 和 capacity-1 的糊涂账循环队列用“牺牲一个槽位”判断空满的写法细节是 (rear1) % capacity front 表示满。很多同学实现时存储容量写 capacity真正可用的却是 capacity-1然后计算 size 时用 (rear - front capacity) % capacity三个地方稍不留神就矛盾。我的建议是直接维护 count别用牺牲槽位的写法省下脑力用来检查业务逻辑。如果必须用经典写法请把“有效容量”作为独立常量写在注释里。6.3 两个栈实现队列为什么均摊是 O(1)用两个栈实现队列是面试高频题核心思想是把栈“后进先出”的顺序翻转两次变成“先进先出”class MyQueue { private: std::stackint inStack; std::stackint outStack; void transfer() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) transfer(); int top outStack.top(); outStack.pop(); return top; } int peek() { if (outStack.empty()) transfer(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };每次 pop 时如果 outStack 空了才把 inStack 整体倒过来每个元素最多被倒一次所以连续 n 次 push/pop 的总代价是 O(n)均摊到每次操作就是 O(1)。面试时如果只答出解法却说不出均摊复杂度分析这道题基本扣一半分。同理还有一个方向两个队列实现栈。我的做法是 push 时先把新元素放进空队列再把另一个队列的元素全部搬到它后面最后交替使用两个队列保证新元素永远在队首这样队首就等效于栈顶class MyStack { private: std::queueint q1; std::queueint q2; public: void push(int x) { q2.push(x); while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } std::swap(q1, q2); } int pop() { int top q1.front(); q1.pop(); return top; } int top() { return q1.front(); } bool empty() { return q1.empty(); } };这两个题不仅是考点还训练一种“结构转换”的思维当你手里只有一种结构时如何通过额外的空间和操作顺序实现另一种语义。这种能力在后端开发里非常实用比如把数据库操作串行化、把异步任务改成同步顺序处理本质上都在做类似的转换。6.4 栈在程序运行时的身影函数调用和栈回溯除了算法题栈还解释了程序本身为什么能正常运行。每次函数调用都会生成一个栈帧局部变量、参数、返回地址都压入调用栈函数返回时弹出栈帧——这就是 backtrace栈回溯的底层原理。调试器能打印出“谁调用了谁”靠的就是从当前栈帧往下遍历调用栈。理解了这一点你再去看递归爆栈Stack Overflow、尾递归优化思路都会清楚得多。我在实际使用中的一个体会是队列和栈这两个结构表面简单越往深处越能串起整个计算机体系的骨架。底层是内存布局和指针操作中层是 STL 的设计哲学和复杂度分析上层是线程池、消息队列、调用栈这些庞大的工程体系。所以每当有人跟我说“队列栈有什么好学的”我一般会反问一句那你解释一下为什么消息队列重复消费要用业务幂等来解决而不是在队列服务端直接把消息删掉能把这个问题想明白你对“队列”这两个字的理解就已经超出期末考试的水平了。