10. stack与queue容器适配器：stack的构造与操作、queue的构造与操作、适配器模式在STL中的应用

这一章我们来聊聊两个非常实用的容器适配器——stack和queue。说实话，这两个东西在项目中出现的频率极高。我个人习惯把它们叫做“包装好的数据结构”，因为它们本质上不是独立的容器，而是对底层容器的二次封装。

你想想看，我们平时写代码，很多时候需要的不是“万能容器”，而是“有规矩的容器”。比如后进先出、先进先出——这些场景太常见了。STL的设计者早就想到了这一点，于是就有了容器适配器。

10.1 适配器模式：STL里的“套壳”哲学

在讲具体用法之前，我觉得有必要先聊聊适配器模式。为什么？因为理解了它，你才能真正明白stack和queue的设计初衷。

适配器模式，说白了就是“给现有的东西套个壳，换个接口”。举个例子：你有一个std::deque，它既能从头插也能从尾插，功能很强大。但如果你只需要“只能从尾部插入、从尾部取出”的功能，那直接暴露deque的全部接口反而容易出错。这时候，stack就登场了——它把deque包起来，只给你push、pop、top这几个操作。

核心思想： 适配器不创造新数据，只约束旧接口。

我在项目中遇到过好几次这样的情况：新人直接用vector模拟栈，结果不小心调用了insert或erase，破坏了栈的结构。用stack适配器，这种低级错误根本不会发生。

10.2 stack容器适配器：后进先出的规矩

stack，栈，后进先出（LIFO）。这个大家应该都很熟悉了。STL中的stack默认底层容器是deque，但你也可以指定vector或list。

10.2.1 stack的构造

构造方式很简单，主要有三种：

#include <stack>
#include <vector>
#include <list>

// 1. 默认构造，底层使用deque
std::stack<int> stk1;

// 2. 指定底层容器为vector
std::stack<int, std::vector<int>> stk2;

// 3. 从已有容器构造
std::deque<int> dq = {1, 2, 3};
std::stack<int> stk3(dq);  // 复制deque的内容到stack

嗯，这里要注意：stack的构造函数其实不多，因为它就是个适配器，不需要太复杂的构造逻辑。我个人习惯用默认的deque版本，除非有特殊性能要求才换成vector。

10.2.2 stack的核心操作

栈的操作非常少，但每个都很关键：

操作 说明 时间复杂度
push(val) 将元素压入栈顶 O(1)
pop() 弹出栈顶元素（无返回值） O(1)
top() 返回栈顶元素的引用 O(1)
empty() 判断栈是否为空 O(1)
size() 返回栈中元素个数 O(1)
避坑指南： 我曾经在代码里直接写 stk.pop() 然后想获取被弹出的值——结果发现 pop() 不返回任何东西。你必须先用 top() 取值，再 pop()。这是很多新手容易犯的错误。

来看一个完整的例子：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stk;
    
    // 压入三个元素
    stk.push(10);
    stk.push(20);
    stk.push(30);
    
    std::cout << "栈大小: " << stk.size() << "\n";  // 3
    
    // 依次弹出并打印
    while (!stk.empty()) {
        std::cout << stk.top() << " ";  // 30 20 10
        stk.pop();
    }
    
    return 0;
}

输出结果：30 20 10。后进先出，一目了然。

10.3 queue容器适配器：先进先出的规矩

queue，队列，先进先出（FIFO）。默认底层容器也是deque，但你不能用vector做底层——因为vector没有pop_front操作。

10.3.1 queue的构造

#include <queue>
#include <list>

// 1. 默认构造，底层使用deque
std::queue<int> q1;

// 2. 指定底层容器为list
std::queue<int, std::list<int>> q2;

// 3. 从已有容器构造
std::deque<int> dq = {1, 2, 3};
std::queue<int> q3(dq);

10.3.2 queue的核心操作

操作 说明 时间复杂度
push(val) 将元素加入队尾 O(1)
pop() 弹出队首元素（无返回值） O(1)
front() 返回队首元素的引用 O(1)
back() 返回队尾元素的引用 O(1)
empty() 判断队列是否为空 O(1)
size() 返回队列中元素个数 O(1)
小技巧： 如果你需要遍历队列，记得先复制一份。因为 queue 没有迭代器，你只能通过不断 pop() 来访问所有元素。我一般会先 auto tmp = q，然后遍历 tmp。

来看一个实际例子：

#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> q;
    
    q.push("任务A");
    q.push("任务B");
    q.push("任务C");
    
    std::cout << "队首: " << q.front() << "\n";  // 任务A
    std::cout << "队尾: " << q.back() << "\n";   // 任务C
    
    // 处理所有任务
    while (!q.empty()) {
        std::cout << "处理: " << q.front() << "\n";
        q.pop();
    }
    
    return 0;
}

输出：任务A 任务B 任务C。先进先出，公平合理。

10.4 适配器模式在STL中的深层应用

讲到这里，我想聊聊适配器模式在STL中更深层的意义。你可能会问：为什么不直接用deque？非要套一层stack或queue？

原因有三：

  1. 接口约束：限制操作，防止误用。就像我前面说的，stack只给你栈操作，你没法乱来。
  2. 语义清晰：看到std::stack<int>，别人立刻知道这是个栈。看到std::deque<int>，别人还得猜你打算怎么用。
  3. 底层可替换：你可以随时换底层容器，而不影响上层代码。比如从deque换成vector，只需要改模板参数。
我的经验： 在大型项目中，代码的可读性和可维护性往往比微小的性能差异更重要。用适配器，就是告诉阅读者“这个数据结构有固定的行为模式”。

10.5 知识体系结构图

下面这张图展示了stack和queue在STL中的位置，以及它们与底层容器的关系：

STL容器适配器体系 stack<T> 后进先出 (LIFO) queue<T> 先进先出 (FIFO) 底层容器 (默认 deque<T>) deque<T> (默认) vector<T> (仅stack) list<T> 对外暴露的操作接口 push() / pop() top() / front() back() empty() / size()

从这张图可以看得很清楚：stack和queue位于上层，它们不自己存储数据，而是委托给底层的deque、vector或list。对外只暴露有限的操作接口——这就是适配器模式的精髓。

10.6 避坑与最佳实践

最后，分享几个我在实际项目中积累的经验：

  • 不要用stack或queue做遍历：它们没有迭代器，强行遍历只能通过pop()，这会破坏数据。如果需要遍历，说明你选错了容器。
  • 注意pop()不返回值：这是STL设计者故意的——如果pop()返回值，就会涉及拷贝构造和异常安全的问题。先top()再pop()是标准做法。
  • 选择合适的底层容器：默认deque在大多数场景下表现良好。如果你对内存连续性有要求，stack可以换成vector；如果你需要频繁在中间插入（虽然适配器不允许），那应该直接用list。
  • 自定义类型的注意事项：如果你的元素类型没有默认构造函数，stack和queue的某些操作可能会受限。比如top()返回引用，没问题；但如果你试图emplace一个需要参数的对象，记得用emplace而不是push。
一句话总结： stack和queue不是容器，是容器的“管家”。它们帮你管好数据进出顺序，让你少犯错。

好了，这一章的内容就到这里。适配器模式在STL中的应用远不止stack和queue，后面我们还会看到priority_queue——它也是个适配器，但底层用的是堆。不过那是后话了。

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

← 上一章 📖 返回目录 下一章 →