36. STL容器（stack与queue）：适配器容器、LIFO与FIFO

说实话，刚学C++那会儿，我总觉得stack和queue没什么了不起的。不就是「先进后出」和「先进先出」嘛，自己用vector也能模拟。直到后来我在一个网络数据包处理项目里，亲手用queue做消息缓冲，用stack做函数调用回溯——我才真正体会到，适配器容器不是「弱化版」的容器，而是「精准版」的工具。

今天咱们就来聊聊这两个家伙。我会把我在项目中踩过的坑、用过的技巧，一并倒出来。

什么是适配器容器？

先问一个问题：stack和queue底层存数据吗？

答案是不存。它们只是「包装」了另一个容器。比如stack默认用deque，你也可以指定用vector或list。说白了，适配器容器就是给底层容器加了一层「行为约束」。

我个人习惯把适配器容器想象成「带盖子的桶」：

• stack：只能从顶部放、顶部取。你永远不知道桶底有什么。
• queue：只能从尾部放、头部取。像排队买奶茶，先来的先拿到。

这种约束不是缺点，而是设计意图——你不需要随机访问，你只需要按规则存取。

stack：后进先出的典型场景

我在写表达式解析器时，stack几乎是标配。比如括号匹配、后缀表达式求值，都离不开它。

来看一个最简单的例子：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "栈顶元素: " << s.top() << std::endl; // 30

    s.pop();
    std::cout << "弹出后栈顶: " << s.top() << std::endl; // 20

    return 0;
}

嗯，这里要注意：pop() 只删除元素，不返回它。想拿到栈顶再弹出，得先 top() 再 pop()。我见过不少新手写成 int val = s.pop()，然后编译报错一脸懵。

queue：先进先出的消息缓冲

queue在异步任务处理中特别常见。比如一个生产者线程往队列里放任务，消费者线程从队列里取任务。

#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> q;

    q.push("任务A");
    q.push("任务B");
    q.push("任务C");

    std::cout << "队首: " << q.front() << std::endl; // 任务A
    std::cout << "队尾: " << q.back() << std::endl;  // 任务C

    q.pop();
    std::cout << "弹出后队首: " << q.front() << std::endl; // 任务B

    return 0;
}

你想想看，queue的front和back都能访问，但pop只移除队首。这和stack的「只动一头」形成了鲜明对比。

底层容器怎么选？

stack和queue默认都用deque。为什么不用vector？因为deque在两端插入删除都是O(1)，而vector在头部插入是O(n)。

但你可以手动指定底层容器：

// 用vector做stack
std::stack<int, std::vector<int>> s;

// 用list做queue
std::queue<int, std::list<int>> q;

我个人建议：除非你有特殊理由，否则别换。deque是STL设计者为你选好的最优解。

性能对比一览

操作	stack（默认deque）	queue（默认deque）
push	O(1)	O(1)
pop	O(1)	O(1)
top / front	O(1)	O(1)
size	O(1)	O(1)

都是常数时间，性能上没得挑。但要注意：stack和queue都不支持遍历。你想从头到尾看一遍？不行，设计上就不允许。这也是适配器容器的特点——只给你需要的接口。

知识体系结构图

下面这张图帮你理清stack和queue在整个STL中的位置：

实际项目中的避坑经验

我记得有一次，我在一个多线程日志系统里用queue做缓冲。生产者疯狂push，消费者来不及pop，结果queue越来越大，内存直接爆了。

后来我加了一个最大长度限制：

class BoundedQueue {
    std::queue<std::string> q;
    size_t max_size;
public:
    bool push(const std::string& item) {
        if (q.size() >= max_size) {
            return false; // 队列满了，丢弃或阻塞
        }
        q.push(item);
        return true;
    }
};

嗯，这里要注意：STL的queue本身没有容量限制。你push多少它就装多少，直到内存耗尽。所以在生产环境中，一定要自己做边界控制。

总结一下

stack和queue虽然简单，但用好了能写出非常优雅的代码。它们不是「功能残缺」的容器，而是为特定场景量身定做的工具。

• 需要后进先出？用stack。
• 需要先进先出？用queue。
• 需要遍历或随机访问？别用它们，换vector或deque。

最后送大家一句话：选对容器，比写好算法更重要。我在项目里见过太多人用vector硬模拟stack，代码又长又容易出错。何必呢？STL已经帮你准备好了。

---

公众号:蓝海资料掘金营，微信deep3321