1. 先搞清楚stack和queue到底是什么C初阶学到容器这块多半会撞上stack和queue。很多人一看名字栈、队列数据结构课本里背过的东西觉得不难实际一写代码就懵了——stack的top怎么用、queue的front和back哪个是哪个、为什么push不叫push_back这些细节全是要命的地方。先说一点最根本的认知stack和queue不是真正的容器而是容器适配器container adapter。它们是站在vector、deque、list这些底层容器肩膀上把接口重新封装了一层只对外暴露栈该有的操作和队列该有的操作。翻译成人话就是底层容器负责真正存数据stack和queue负责规定你只能怎么取数据。这就解决了一个很关键的疑问既然vector都能存数据为什么还要stack因为vector太自由了。你可以push_back也可以任意位置插入还能用下标访问。但栈这个数据结构的要求是严格的后进先出LIFO队列是严格的先进先出FIFO。如果你用vector裸着去模拟一个栈代码里全是push_back加pop_back还得时刻提醒自己别乱用下标访问很容易失控。stack等于帮你焊死了一道门只留下合法的出入口从设计上杜绝了误操作。所以这套笔记的核心就一句话stack和queue的价值不在存数据而在约束存取方式。2. 容器适配器的设计思路为什么标准库要这么封装2.1 从底层容器的选择看适配器思想C标准库里的容器是分层的。底层容器vector、deque、list负责具体的内存管理和元素存储每种容器都有自己的特点和适用场景。而stack、queue、priority_queue这一层是建立在底层容器之上的接口层它们不自己管内存而是调用底层容器的成员函数来完成操作。以stack为例它的模板声明是templateclass T, class Container std::dequeT class stack;第二个模板参数Container默认是deque。也就是说你写std::stackint st的时候背后其实实例化了一个deque来存数据。stack的所有操作都是在这个deque上做二次封装void push(const T value) { c.push_back(value); } void pop() { c.pop_back(); } T top() { return c.back(); }这里c就是内部那个底层容器对象。看到没有top操作对应的是底层容器的back——因为deque的尾部就是栈顶。如果你把底层容器换成vector逻辑完全一样只是尾部操作变成了vector的back。queue的封装逻辑同理void push(const T value) { c.push_back(value); } void pop() { c.pop_front(); } T front() { return c.front(); } T back() { return c.back(); }queue入队从尾部进出队从头部出所以底层容器的front和back各自承担了出口和入口的职责。2.2 为什么要允许换底层容器你可能会想既然默认deque用得好好的为什么还要留Container这个模板参数因为不同场景下性能特征不一样。如果你需要一个栈但你的程序对内存连续性要求高希望底层用vector存那就可以std::stackint, std::vectorint来实例化。如果你需要频繁在中间插入删除虽然用栈的场景一般不会这么干list作为底层容器也可以胜任。这个设计背后体现的是面向对象里面向接口编程的思想。调用方只依赖抽象的栈接口push/pop/top不依赖具体实现。以后想换底层存储方案只改模板参数一个地方业务逻辑一行都不用动。这不仅仅是省事更是架构层面的解耦。2.3 stack和queue不支持迭代器访问这可能是很多初学者最容易忽略的一条规则。stack和queue不允许遍历没有begin()和end()不支持范围for循环。解决方案就是倒腾想遍历栈只能不断pop到一个临时容器里看完了再倒回来想遍历队列只能出队再入队转一圈。有人觉得这是缺陷但其实这是设计上的刻意为之。栈和队列的核心语义就是受限的访问顺序。如果允许随意遍历你就退化成了一个肤浅的vector那还要它干什么从工程角度说让数据结构保持其核心语义不被破坏比功能丰富更重要。这种少即是多的克制恰恰是C标准库设计的精髓之一。3. 接口细节与底层原理这些坑新手必踩3.1 stack的常用接口速查直接上表看一眼就明白接口作用注意事项push(x)栈顶插入元素等价于底层容器的push_backpop()弹出栈顶元素无返回值只删不取top()返回栈顶元素的引用可读可写但引用可能失效empty()判断栈是否为空比size()0执行效率更直接size()返回栈内元素个数O(1)复杂度有一个典型的新手错误很多人以为pop()会把栈顶元素作为返回值返回像int x st.pop();这样写。这在C里编译不过。为什么标准库要这么设计两个原因。第一个原因是异常安全性。如果pop既返回元素又删除元素删除时万一抛出异常元素已经丢了你啥也没拿到状态就乱了。分成top和pop两步top负责安全地获取元素pop负责安全地删除各司其职。第二个原因是性能。返回元素会触发拷贝构造或移动构造被迫多一次构造开销。不返回直接void内部只做删除干净利落。这也是C和Java等语言设计风格差异的体现——C标准库极其在意不为不需要的东西买单。实际使用中取栈顶元素并弹出的标准写法是int value st.top(); // 先读取 st.pop(); // 再弹出3.2 queue的接口细节queue的接口数量跟stack基本对称接口作用注意事项push(x)队尾入队尾部插入pop()队头出队头部删除无返回值front()返回队头元素的引用最早入队的那个元素back()返回队尾元素的引用最晚入队的那个元素empty()判断队列是否为空同上size()返回队列内元素个数同上front()是很多人的易混淆点。queue的front是最早进来的也就是排队排在最前面的。你想想现实里排队买奶茶队头是第一个买到的人队尾是最后一个进队的对得上号了就好记了。还有一个细节值得注意queue的front()和back()返回的都是引用所以你可以直接通过它们修改元素std::queueint q; q.push(1); q.push(2); q.front() 100; // 队头元素从1变成100 q.back() 200; // 队尾元素从2变成200在写BFS广度优先搜索这类算法时这个特性偶尔会派上用场。不过也提醒一句修改了引用指向的内容等于是修改队列内部的数据别在不该改的地方动手。3.3 为什么默认底层容器是deque而不是vector这是个高频面试问题也是理解STL设计的一个绝佳切入点。先说结论deque双端队列同时支持头尾两端的O(1)插入删除正好同时满足stack和queue的需求。stack只需要尾部操作push_back/pop_backqueue需要尾部插入和头部删除push_back/pop_frontdeque两头都能干所以它是stack和queue的公共底座。如果只考虑stackvector其实也够用尾部操作同样是O(1)。但queue就不行了vector在头部删除的话需要把后面所有元素往前挪时间复杂度O(n)数据量一大直接卡死。list虽然头尾操作都O(1)但它每个节点要额外存前后指针内存碎片化严重缓存命中率也差。deque的底层实现可以简单理解成分段连续的缓冲区数组。它本质上是一个指针数组每个指针指向一段连续的内存块。这种结构让它既不像vector那样在头部操作时大量挪动元素又不像list那样每个元素独立分配内存。理论上deque可以做到头尾插入删除都是均摊O(1)而且随机访问也是O(1)比list强代价是比vector多一次指针间接跳转。综合下来作为stack和queue的默认适配容器deque是最均衡的选择。3.4 关于priority_queue的补充说明标题里是stack和queue但既然queue都讲了priority_queue也顺带提一句因为它也是同一族的东西。priority_queue优先队列也是容器适配器默认底层是vector元素按堆序排列支持自定义比较规则。它的接口和queue类似但pop出去的不是最早进来的而是优先级最高的。默认是大根堆也就是每次弹出的都是当前队列里最大的元素#include queue #include vector std::priority_queueint pq; pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5); while (!pq.empty()) { std::cout pq.top() ; // 输出 5 4 3 1 1 pq.pop(); }如果想实现小根堆就需要自定义比较器std::priority_queueint, std::vectorint, std::greaterint min_pq;这个std::greaterint是STL里的一个函数对象把它作为第三个模板参数传给priority_queue堆的排序规则就反过来了。**这里特别提醒一个初学陷阱greater的模板参数和堆顶方向是反直觉的。用greater反而得到的是小根堆堆顶是全区最小的元素。**我见过太多人在这里绕不明白建议直接背结论用多了就自然懂了。4. 动手实战stack和queue的经典应用场景4.1 用stack做括号匹配检查这是栈最经典的应用场景没有之一。题目一般长这样给定一个只包含( ) [ ] { }的字符串判断括号是否合法匹配。核心思路一句话遇到左括号就入栈遇到右括号就和栈顶比对匹配则弹出不匹配则直接失败。遍历结束后栈为空才代表全部匹配成功。bool isValid(const 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 {)) { st.pop(); } else { return false; // 括号类型不匹配 } } } return st.empty(); // 最后栈空才是全部匹配 }有的解法喜欢用map预先存配对关系代码更优雅但思路是一样的。这道题考察的不是coding能力而是对栈后进先出特性的理解。右括号必须和最近的那个左括号配对栈天然就是干这个的。4.2 用queue做层级遍历queue最典型的应用是二叉树的层序遍历BFS也就是一层一层地扫描树#include queue #include vector std::vectorstd::vectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint result; if (!root) return result; std::queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 关键先记录这一层的节点数 std::vectorint level; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }这里的levelSize q.size()是个核心技巧。每次循环开始时队列里刚好放着一层的节点先记录数量再一次性处理完这一层下一层就会进队列循环继续。如果不在循环前记录size而是直接用!q.empty()判断就会把下一层的节点也混进当前层的处理里层就分不清了。这个分层技巧在BFS里非常常用不只是二叉树图的最短路径、拓扑排序、多源BFS等场景里都会反复出现。建议彻底吃透。4.3 用两个栈模拟一个队列这是个面试高频题而且特别能检验你对两个数据结构的细节理解。思路用两个栈一个负责入队一个负责出队。入队push直接压入inStack。出队pop如果outStack为空就把inStack的所有元素依次弹出并压入outStack然后再从outStack弹出栈顶。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 val outStack.top(); outStack.pop(); return val; } int peek() { if (outStack.empty()) { transfer(); } return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } };原理是什么栈是LIFO的但两次LIFO叠加在一起就抵消成FIFO了。你把3个元素压进inStack出栈顺序是逆序的再压入outStack又逆序一次从outStack弹出来顺序就和原始入队顺序一致了。这里的优化点是transfer()只在outStack空的时候才执行。如果每pop一次就转移一次就是纯纯的O(n)操作毫无优化可言。摊还分析一下每个元素最多被移动两次进inStack一次、进outStack一次整体均摊复杂度是O(1)。这个摊还思想在很多数据结构里都会用值得记下来。5. 高频面试题与算法题里的stack、queue5.1 单调栈一个栈字能玩出花单调栈是算法学习中一个很重要的进阶话题单调指的是栈内元素始终保持有序单调递增或单调递减。最经典的入门题是每日温度或者下一个更大元素。拿下一个更大元素举例给你一个数组返回一个新数组每个位置存的是下一个比当前元素大的元素没有就填-1。std::vectorint nextGreater(std::vectorint nums) { int n nums.size(); std::vectorint result(n, -1); std::stackint st; // 存储下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { // 当前元素比栈顶大说明栈顶的下一个更大元素就是nums[i] result[st.top()] nums[i]; st.pop(); } st.push(i); } return result; }单调栈的精髓在于每个元素最多入栈一次、出栈一次整体时间复杂度O(n)。如果暴力解每个元素都要往后扫描O(n²)数据量一大就完蛋。单调栈题目变化很多但本质都是利用栈维护一个局部有序的序列快速找到每个元素左侧或右侧第一个更大或更小的值。学通这一题后面什么接雨水、柱状图中最大矩形就都好办很多。5.2 双端队列deque与单调队列deque本身就是stack和queue的底层在算法里也直接作为双端队列使用。单调队列最常见的场景是滑动窗口最大值给你一个数组一个固定大小的窗口从左往右滑输出每个窗口内的最大值。这道题用deque维护一个窗口内递减序列std::vectorint maxSlidingWindow(std::vectorint nums, int k) { std::vectorint result; std::dequeint dq; // 存下标队头永远是当前窗口最大值的下标 for (int i 0; i nums.size(); i) { // 从队尾弹出所有比当前元素小的 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 从队头弹出已经滑出窗口的 if (dq.front() i - k) { dq.pop_front(); } // 窗口形成后才能记录结果 if (i k - 1) { result.push_back(nums[dq.front()]); } } return result; }这里核心思路就两条新元素入队前把队尾所有比它小的元素全部弹出保证队列从头到尾递减窗口滑动时及时把过期的队头元素弹出。整个数组只遍历一遍O(n)搞定。这个写法如果你没见过第一次看可能觉得绕但多写几遍就会觉得其实就是在用deque的两个端口的O(1)操作维护一个动态单调序列而已。5.3 阻塞队列与多线程模型顺着queue往应用层走就不得不提阻塞队列Blocking Queue。这在操作系统、并发编程、消息队列中间件里都是核心概念。广义上它还是一个队列但多了阻塞能力队列空时消费者线程等待队列满时生产者线程等待。典型实现是条件变量condition_variable加互斥锁搞定。在C里你可以这样粗略模仿一个线程安全的阻塞队列templatetypename T class BlockingQueue { private: std::mutex mtx; std::condition_variable notEmpty; std::queueT data; public: void push(const T item) { std::unique_lockstd::mutex lock(mtx); 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(); return item; } };生产者消费者模型、线程池的任务队列、消息队列的底层全都是这个套路。理解queue的语义 条件变量 锁就能徒手写一个迷你任务队列。再往上延伸到消息队列的重复消费、ack机制那是中间件层面的事但底层的数据结构逻辑还是那个队列。6. 避坑实录平时写代码容易出的问题6.1 在空栈/空队列上调用top或front这是未定义行为标准库里不会给你任何安抚——不报错、不抛出异常直接就是垃圾值或者崩溃。这种bug特别隐蔽因为小规模数据测试可能碰不上一上大数据或者极端输入就翻车。使用前务必先检查empty()if (!st.empty()) { st.top(); // 安全 }6.2 先存top再pop引用失效问题stack的top()返回的是引用指向的是栈顶元素。一旦pop()这个引用就失效了因为底层容器已经把这个元素删了。如果你先拿了个引用再去pop然后把引用拿来用会读到未定义内容。int ref st.top(); st.pop(); std::cout ref; // 危险ref已失效正确的做法是先拷贝成值再popint value st.top(); st.pop(); std::cout value; // 安全6.3 queue的底层容器的接口约束queue的底层容器必须支持front()、back()、push_back()、pop_front()这四件套。vector不支持pop_front所以不能当queue的底层list和deque都可以。stack只需要push_back、pop_back、back所以vector、list、deque都能胜任。这个约束是编译期的概念静态断言会在模板实例化时检查。如果你哪天好奇写了std::queueint, std::vectorint大概率编译不过看到一长串模板报错不要慌核心信息就是vector没有pop_front。6.4 别用size()0替代empty()empty()在标准容器里通常是专门针对该容器结构实现的效率完全不输size()0甚至对某些链表结构来说更直接。可读性上empty()也更语义化。写代码用!st.empty()描述还有元素这个意图比st.size() 0清晰得多。这不是性能强迫症是代码表达力的提升。6.5 stack/queue没有clear()方法如果你想让一个stack重新为空最粗暴的方法是while (!st.empty()) { st.pop(); }或者更直接的——直接赋新对象st std::stackint(); // 或 st {};这个写法很冷门但确实存在相当于把旧的底层容器整个销毁换个新的。queue同理。7. 踩过坑之后的一些拓展想法学完stack和queue别急着往下一个章节跑。我个人的建议是去做三件事第一手动实现一个基于vector的stack不为别的就为了理解适配器到底是怎么包出来的。代码量不大十分钟的事但对封装这个概念的理解会完全不一样。第二把优先队列用好。std::priority_queue在贪心算法、Top K问题、Dijkstra最短路里无处不在。注意Dijkstra里通常要配pairint, int距离、节点编号默认的大根堆并不直接适用需要自定义比较逻辑。这也是一个高频bug来源pair的字典序比较会让距离大的排前面刚好搞反。第三多留意消息队列中间件比如Kafka、RabbitMQ或者更轻量的Redis List的文档。它们的核心工作模型说白了就是一个分布式、持久化、支持多消费者竞争的队列。你如果理解了单机队列的语义再去看这些中间件会发现很多概念是相通的。回到最初那句话stack和queue真正教会你的不是两个容器的接口怎么用而是**约束对软件设计的价值**。接口少不会让人困惑语义严格不会让人误用封装干净不会制造复杂度。写业务代码的时候如果发现一个容器被用得到处都是、什么操作都往上堆那大概率是抽象粒度出了问题。栈和队列这种小而专的姿态反而更值得借鉴。