如果你写过带撤销功能的编辑器或者做过任务排队处理那你已经隐隐约约用到了栈和队列背后的思想。这篇博文要讲的是 C 标准库里的两个容器适配器std::stack和std::queue。它们不自己管理内存而是在已有容器上面重新包装一套受限接口栈只允许在栈顶进出队列只允许队尾进、队头出。这种限制不是麻烦而是帮你减少出错的概率。这篇文章适合谁看适合刚学完vector/list想搞明白 C 容器家族里这两个“看着简单但有点怪”的成员的人也适合准备面试需要把括号匹配、双栈实现队列这类高频题吃透的人。文中会从设计思路、接口细节、底层容器、手写模拟、实战例题到避坑建议一次讲清楚保证你读完能直接用在项目和刷题里。1. 先把栈和队列的定位搞清楚它们是适配器不是新容器1.1 栈和队列到底约束了什么很多初学朋友第一次接触std::stack时第一反应是“这不就是用vector也能实现吗为什么还要单独搞一个类型”确实是vector完全可以模拟栈的行为用push_back入栈用back()看栈顶用pop_back()出栈。但这恰恰漏掉了问题的关键栈本质上一套语义约束。你希望一个线性结构只允许在一端插入和删除那就应该把这种约束写死在接口上而不是靠使用者自律。队列也一样。deque本身已经提供了push_back、pop_front但它同时还会暴露operator[]、迭代器遍历、中间的插入删除等一堆接口。如果你写一个任务队列本来只想让别的模块“从尾部加、从头部取”结果同事一不小心用了q[2] xxx直接改中间的数据这个问题在 code review 时极难发现运行时报错又隐蔽。而std::queue把对外接口收敛成push、pop、front、back别人想乱来也没有入口。我打过一个比方vector是一台手动挡汽车所有操作都暴露给你上限高但误操作风险也高stack/queue是自动挡把最容易出错的复杂操作拿掉你只能按正确的节奏开。做业务模块时接口约束越明确协作越不容易出问题这是我在实际项目里逐步体会到的。1.2 为什么 C 要绕一层适配器C 标准库中stack、queue、priority_queue都属于容器适配器。所谓适配器就是“我有底层容器但我对外重新定义一套接口”。设计意图非常清晰底层容器负责真正存储数据和分配内存适配器负责提供贴近语义的方法名、隐藏不相关的能力使用者可以按需指定底层容器一行代码替换存储策略。这种分层的好处是极大的灵活性。同样一个std::stackint默认底层是deque你可以改成std::stackint, std::vectorint st1; std::stackint, std::listint st2;代码中调用push、pop、top的位置完全不用变底层存储策略却可以随意切换。适配器模式让“语义”和“存储”解耦这在大型项目中是缩短重构成本的关键。理解这一层之后栈和队列在你眼里就不是“两个新容器”而是“在熟悉的容器上套的新行为”。后面咱们看接口和底层时就会顺很多。2. 接口不多但每个都要吃透2.1 stack 常用接口与复杂度std::stack对外提供的方法很少总共就六个左右但每个都有明确的使用场景接口作用复杂度push(x)将 x 压入栈顶O(1)pop()删除栈顶元素不返回被删元素O(1)top()返回栈顶元素的引用O(1)empty()判断栈是否为空O(1)size()返回栈中元素个数O(1)emplace(args...)原地构造元素压入栈顶O(1)注意pop()的返回值是void。很多从 Python 转过来的朋友会习惯性写int x st.pop();在 C 里这是编译不过的。正确姿势是int x st.top(); // 先取 st.pop(); // 再删之所以这样设计一方面是为了避免多一次元素拷贝带来的性能损耗另一方面是防止“先删除再拷贝时元素已经没了”的异常安全问题。在刷题或写业务代码时这个习惯要从一开始就养成。2.2 queue 常用接口与复杂度std::queue的接口同样简洁但方向正好相反接口作用复杂度push(x)在队尾插入元素O(1)pop()删除队头元素不返回被删元素O(1)front()返回队头元素引用O(1)back()返回队尾元素引用O(1)empty()判断队列是否为空O(1)size()返回队列中元素个数O(1)队列强调先进先出所以你会同时拿到队尾和队头两个口。front对应最早进来的元素back对应最近进来的元素。实际业务里最常见的组合是while (!q.empty()) { Task t q.front(); // 取出当前要处理的队头任务 q.pop(); // 处理完立即弹出 }这里有一个我踩过的坑如果Task是个拷贝成本很高的对象上面写法会多拷贝一次。更稳妥的做法是用引用拿到对象后再弹出或者结合移动语义while (!q.empty()) { Task t q.front(); process(t); q.pop(); }因为process内部如果只是读取引用完全够用如果需要把任务转走再考虑std::move(q.front())。总之别为了省事去复制重对象。2.3 用一段代码把增删查串起来拿一个模拟消息队列的场景来演示。假设要给用户发通知通知按到达顺序依次处理#include iostream #include queue #include string int main() { std::queuestd::string messages; messages.push(你的订单已确认); messages.push(包裹正在运输中); messages.push(包裹已签收); std::cout 当前待处理消息数: messages.size() \n; std::cout 队头消息: messages.front() \n; while (!messages.empty()) { std::cout 正在处理: messages.front() \n; messages.pop(); } return 0; }输出顺序一定是先下单确认、再运输、再签收这正是队列的核心价值——顺序保真。如果你在这个场景错用了栈消费者处理到的顺序就会倒过来那用户收到的通知就乱套了。3. 底层容器是怎么选的deque 凭什么成为默认3.1 deque 的真实结构分段连续数组为什么stack和queue默认底层都是deque要回答这个问题得先知道deque长什么样。deque是 double-ended queue 的缩写中文叫双端队列。它在逻辑上是连续的但在物理上并不是一整块大数组而是由若干段固定大小的缓冲区拼接而成再由一个中央控制器map维护这些缓冲区的指针顺序。当在头部插入元素时只需在当前首缓冲区前面再挂一个新缓冲区不需要像vector那样搬动已有元素。因此deque拿到了一个非常漂亮的平衡点push_back、push_front都是均摊O(1)按下标随机访问是O(1)虽然比vector多一次间接跳转内存利用率高于list缓存友好性也优于list。对于栈来说需要在一端频繁进出deque很合适对于队列来说需要头尾两端分别读写deque更是完美命中。这就是它被选为默认底层容器的原因。3.2 三种容器做底层时的对比我自己维护过一个小型任务调度模块最初底层用的是std::list后来换成deque吞吐量提升非常明显。这里有一个公平对比底层容器stack场景一端进出queue场景尾进头出随机访问内存碎片vector极好但固定容量/扩容有开销不好头部删除需要搬移所有元素极好低list好但每个节点有额外指针开销好但节点分散、缓存不友好差较高deque极好均摊常数极好均摊常数好低如果queue用vector做底层pop()对应erase(begin())是O(n)操作队列越长性能越炸。如果stack用list做底层虽然进出也是O(1)但每个元素都要分配一次节点内存小对象高频入栈时malloc的开销比数组式存储高一个量级。3.3 控制底层容器一行切 vector/list再强调一下适配器带来的便利。当你知道栈元素总量很小、又想追求更优缓存命中率时可以显式指定vectorstd::stackint, std::vectorint st;当队列元素是超大对象、且频繁动态增删时可以换list试试std::queueBigObject, std::listBigObject q;这种切换不需要修改任何调用代码只改模板参数即可。我在项目里就靠这个能力做过一次存储层替换改动量是零业务代码。这也是标准库设计的高明之处把选择权留给使用者而不是替你做死决定。4. 手写一个 stack 和 queue模板适配器其实很好模拟4.1 模拟 stack理解了适配器原理之后手写模拟版本就成了最好的练习。下面是一个最小可用的stack#include deque templateclass T, class Container std::dequeT class my_stack { public: void push(const T x) { _con.push_back(x); } void pop() { _con.pop_back(); } T top() { return _con.back(); } const T top() const { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; };核心代码就这么点。push对应底层push_backpop对应底层pop_backtop对应底层back。底层容器必须支持这些操作否则编译报错。这就是适配器的本质把已有的功能重新命名、裁剪对外呈现新语义。4.2 模拟 queuequeue的模拟稍微多一点技巧因为需要在队尾入、队头出#include deque templateclass T, class Container std::dequeT class my_queue { public: void push(const T x) { _con.push_back(x); } void pop() { _con.pop_front(); } T front() { return _con.front(); } T back() { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; };注意pop调用的是pop_front而不是pop_back方向别搞反。如果新写代码的人不小心调成pop_back队列就退化成栈了而且这种逻辑错误在单元测试里不一定能暴露要格外小心。4.3 手写时最容易栽的跟头第一个坑const 版本缺失。如果你没写const T top() const这样重载那么一个 const 的栈实例是无法取到栈顶值的。我在代码 review 中不止一次看到新人漏掉这个重载编译一跑error: passing const stack as this argument discards qualifiers才回来补。第二个坑底层容器不匹配导致编译失败。如果拿std::vectorT给queue做底层pop_front是不存在的模板在实例化时才会报错报错信息很长容易让人懵圈。遇到这种问题先检查底层容器的方法是否符合需求栈只需要push_back、pop_back、back队列需要push_back、pop_front、front、back。第三个坑忘记处理空容器。手写版本里没有没有做任何保护top()或front()在容器为空时是未定义行为。标准库也一样使用者必须在调用前判断。真实开发中我见过线上崩溃就是消费线程在队列瞬间为空时强行front()所以无论代码怎么封装空判断永远不能省。5. 高频实战从括号匹配到循环队列5.1 括号匹配栈思路的经典应用栈最常见的应用场景是“最近的元素优先匹配”括号匹配就是这个思路的完美例子#include stack #include string bool isValid(std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; } st.pop(); } } return st.empty(); }这个题考察的核心点遇到右括号时要和“最近尚未匹配”的左括号配对栈天然记录这种先后关系。我面试新人时最想看到的不是背题而是能回答出“为什么用栈而不用队列”——因为配对遵循后进先出和他肩并肩走的括号是最近的那个。5.2 用两个队列实现栈巧妙的逆序思维面试里还有一道高频变体只能用队列的基本操作实现一个栈。思路是用第二个队列做缓冲每次入栈时把新元素放到队头位置#include queue #include algorithm class MyStack { private: std::queueint q1, 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 x q1.front(); q1.pop(); return x; } int top() { return q1.front(); } bool empty() { return q1.empty(); } };核心技巧在于队列是 FIFO栈是 LIFO要让队列模拟栈就必须让“最后入队的元素”待在队头。每次push都把旧元素重新放到新元素后面于是队头永远是“最后进来的”。这里push代价是O(n)pop是O(1)。面试时可以顺手分析一下均摊复杂度这是加分项。5.3 用两个栈实现队列惰性搬运反过来用两个栈实现队列也非常经典。思路一个栈负责入队一个栈负责出队出队栈为空时再把入队栈整体倒进去#include stack class MyQueue { private: std::stackint inStack; std::stackint outStack; public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } int x outStack.top(); outStack.pop(); return x; } int peek() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };为什么叫惰性搬运因为只有outStack空了才去倒数据而不是每次pop都倒腾一遍。这样一来每个元素最多被压入和弹出两次均摊下来pop是O(1)而不是每次都是O(n)。很多新手在这里会写错成每次pop前都搬运导致性能低下白白丢了复杂度分。5.4 手写循环队列用数组解决空间复用如果想自己造队列而不靠标准库循环队列是绕不开的。它用数组加头尾指针模拟环形结构出队后腾出的位置可以继续复用。关键实现#include vector class MyCircularQueue { private: std::vectorint vec; int head; int tail; int count; int capacity; public: MyCircularQueue(int k) : vec(k), head(0), tail(0), count(0), capacity(k) {} bool enQueue(int value) { if (isFull()) return false; vec[tail] value; tail (tail 1) % capacity; count; return true; } bool deQueue() { if (isEmpty()) return false; head (head 1) % capacity; --count; return true; } int Front() { return isEmpty() ? -1 : vec[head]; } int Rear() { return isEmpty() ? -1 : vec[(tail - 1 capacity) % capacity]; } bool isEmpty() { return count 0; } bool isFull() { return count capacity; } };这里要注意两个细节取队尾元素时tail指向的是“下一个空位”队尾实际在tail - 1如果tail是 0减 1 会变成负数所以先加capacity再取模。head和tail的移动都用% capacity让指针冲过数组末尾后自然回到开头。我用这个结构写过音频采样环形缓冲效果非常好。它的优势是内存固定、无动态扩容、读写互不干扰非常适合“生产者–消费者”模型。6. 常见报错场景与避坑指南6.1 空容器 pop 引发的崩溃这是初学者最容易踩的雷。标准库的pop()、top()、front()在容器为空时是未定义行为不同编译器表现不同可能在 Debug 版本直接断言崩溃也可能在 Release 版本悄无声息返回垃圾值。正确姿势是统一加保护if (!st.empty()) { st.pop(); } if (!q.empty()) { Task t q.front(); q.pop(); }如果是多线程环境业务逻辑里“判断非空”和“pop”之间也可能被别的线程插一脚这种场景需要 mutex 或者原子操作来保护。单纯靠 if 判断不能解决并发问题这一点在写消费者模型时要特别留意。6.2 别把函数调用栈和 std::stack 搞混操作系统层面的“调用栈”call stack和标准库里的std::stack是两码事。调用栈是程序运行期间记录函数调用的内存区域局部变量放在这里递归层数太深或局部变量太大就会栈溢出stack overflow。而std::stack是一个容器适配器它管理的数据通常存储在堆上和函数调用栈没有任何关系。这个混淆非常常见因为中文都叫“栈”。如果面试官问“栈溢出是什么”答成“容器的 top 越界”就闹笑话了。平时写代码时我会刻意区分这两个概念一个说运行时内存区一个说数据结构容器。6.3 deque 迭代器失效与修改原则deque的迭代器失效规则比vector复杂一些。在非两端的中间位置插入或删除会使得所有迭代器失效在头部或尾部插入其他位置的迭代器仍可能失效因为头部插入可能触发 map 扩容。实际踩过的坑std::dequeint d {1, 2, 3}; auto it d.begin() 1; d.push_front(0); // 可能使 it 失效解决办法很简单不要在持有迭代器期间修改 deque 的两端。如果必须这样做重新获取迭代器。另一方面正因为deque支持两端快速插入标准库选中它做queue的默认底层这点在项目选型时也要记住。6.4 性能选择速查表最后给一张实战速查表帮大家在不同场景下快速决策场景推荐方案理由撤销/重做功能stack天然后进先出恢复上一步操作逐层遍历树queue层次顺序遍历依赖先进先出冒泡排序优化stack 下界比较用栈记录比边界减少无效比较消息/任务排队queue严格顺序处理队列语义清晰高并发消费者循环队列 / 阻塞队列固定内存、读写分离、无锁化空间大我在实际项目里做任务的深度优先遍历用过deque直接当栈用做广度优先遍历用过queue做层级管理。栈和队列这两个基础数据结构几乎是所有调度、搜索、状态转换算法的底层骨架。把它们从“语法层面”理解到“语义层面”写起代码来会稳很多。我个人在实际操作中的一个体会是遇到问题先问自己“这里需要先进先出还是后进先出”答案直接决定用队列还是栈。很多设计混乱的代码改掉一个容器选择逻辑瞬间就清晰了。拿不准的时候就用最简单的原则判断——要顺序就用队列要回溯就用栈。