6、容器适配器 stack 与 queue：从底层到实战

容器适配器，这个名字听起来有点唬人。其实说白了，它们就是给现有的容器「套了一层皮」，限制了操作方式。我刚开始学 STL 的时候，总觉得 stack 和 queue 是独立的数据结构，后来才发现，它们底层都是拿 deque 或者 vector 改的。

这一章，咱们就把 stack、queue、priority_queue 这三个适配器彻底讲透。最后我会带你写一个括号匹配检查器，这是我在实际项目中经常用到的小工具。

6.1 stack：后进先出的底层实现

stack 的特性很简单——后进先出（LIFO）。就像一摞盘子，你只能从最上面拿，也只能往最上面放。

但它的底层是怎么实现的？默认情况下，stack 是用 deque 适配的。为什么选 deque 而不是 vector？

关键原因：deque 在头部和尾部插入删除都是 O(1)，而 vector 在头部插入是 O(n)。stack 虽然只用尾部操作，但 deque 的内存管理更高效，不会像 vector 那样频繁扩容拷贝。

来看一个简单的 stack 用法：

#include <stack>
#include <iostream>

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;
}

你可能会问：能不能换底层容器？当然可以。stack 的第二个模板参数就是底层容器类型：

std::stack<int, std::vector<int>> s1;   // 用 vector 实现
std::stack<int, std::list<int>> s2;     // 用 list 实现

我个人习惯用默认的 deque，除非有特殊需求。比如在嵌入式环境里，vector 的内存连续性可能更友好，但这种情况很少见。

避坑指南：stack 的 pop() 不会返回被删除的元素。如果你想获取并删除栈顶元素，需要先 top() 再 pop()。我曾经在代码审查时看到新手写成 int val = s.pop();，编译直接报错。

6.2 queue：先进先出的 FIFO 特性

queue 就是队列，先进先出（FIFO）。像排队买奶茶，先来的人先买到。

queue 默认也是用 deque 适配的。为什么？因为 queue 需要在尾部插入、头部删除，deque 两头操作都是 O(1)，完美匹配。

#include <queue>
#include <iostream>

int main() {
    std::queue<std::string> q;
    
    q.push("张三");
    q.push("李四");
    q.push("王五");
    
    std::cout << "队首: " << q.front() << std::endl;  // 张三
    std::cout << "队尾: " << q.back() << std::endl;   // 王五
    
    q.pop();
    std::cout << "弹出后队首: " << q.front() << std::endl;  // 李四
    
    return 0;
}

queue 的常用操作就这几个：push（入队）、pop（出队）、front（队首）、back（队尾）、empty（判空）、size（大小）。

注意：queue 不能用 vector 做底层容器，因为 vector 没有 pop_front() 方法。如果你非要用连续内存，可以考虑 deque 或者自己封装。

我在项目中用 queue 做过消息队列。比如一个日志系统，多个线程往队列里写日志，一个线程从队列里取日志写到文件。这种场景下，queue 的 FIFO 特性保证了日志的顺序性。

6.3 priority_queue：带优先级的队列

priority_queue 就更有意思了。它不按入队顺序出队，而是按优先级。优先级最高的元素永远在队首。

底层实现是堆（heap），默认用 vector 做容器，配合 std::less 实现最大堆。也就是说，默认情况下，最大的元素先出队。

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;
    
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    
    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // 输出: 50 30 20 10
        pq.pop();
    }
    
    return 0;
}

如果你想实现最小堆，可以这样：

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

三个模板参数分别是：元素类型、底层容器、比较器。比较器决定了优先级规则。

实战经验：我在做任务调度器时用过 priority_queue。每个任务有优先级，高优先级的任务先执行。但要注意，priority_queue 不是线程安全的，多线程环境下需要加锁。

自定义类型的优先级怎么处理？重载 operator< 或者传入自定义比较器：

struct Task {
    int id;
    int priority;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 优先级高的排前面
    }
};

std::priority_queue<Task> task_queue;

6.4 实战：括号匹配检查器

好了，理论讲完了，咱们来写点实在的。括号匹配检查器是 stack 的经典应用，也是编译器语法分析的入门级工具。

思路很简单：遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是否匹配。如果匹配就弹出，不匹配就报错。最后栈为空说明全部匹配。

#include <stack>
#include <string>
#include <iostream>

bool isMatching(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

bool checkBrackets(const std::string& expr) {
    std::stack<char> s;
    
    for (char ch : expr) {
        if (ch == '(' || ch == '[' || ch == '{') {
            s.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (s.empty()) {
                return false;  // 右括号多了
            }
            char top = s.top();
            if (!isMatching(top, ch)) {
                return false;  // 不匹配
            }
            s.pop();
        }
        // 其他字符忽略
    }
    
    return s.empty();  // 栈空说明全部匹配
}

int main() {
    std::string test1 = "{[()]}";
    std::string test2 = "{[(])}";
    std::string test3 = "({[}])";
    
    std::cout << test1 << " - " << (checkBrackets(test1) ? "匹配" : "不匹配") << std::endl;
    std::cout << test2 << " - " << (checkBrackets(test2) ? "匹配" : "不匹配") << std::endl;
    std::cout << test3 << " - " << (checkBrackets(test3) ? "匹配" : "不匹配") << std::endl;
    
    return 0;
}

输出结果：

{[()]} - 匹配
{[(])} - 不匹配
({[}]) - 不匹配

扩展思路：这个检查器可以扩展到 HTML/XML 标签匹配，甚至代码中的引号匹配。我在写一个简易的 JSON 解析器时，就用到了类似的逻辑。

你想想看，如果没有 stack，这个功能实现起来得多麻烦？用数组模拟栈也不是不行，但代码会变得又臭又长。STL 的 stack 封装好了所有细节，我们只需要关注业务逻辑。

6.5 知识体系总览

下面这张图总结了本章的核心内容，帮你理清三个适配器的关系：

容器适配器知识体系 容器适配器 stack（栈） LIFO 后进先出 queue（队列） FIFO 先进先出 priority_queue 优先级队列 底层实现 默认 deque 适配 默认 deque 适配 默认 vector + 堆 实战应用 括号匹配检查器 · 表达式求值 · 任务调度

嗯，这张图把三个适配器的关系、底层实现和实战应用都串起来了。你可以把它当作本章的思维导图。

总结一下：

  • stack 和 queue 默认用 deque，因为 deque 两头操作效率高
  • priority_queue 默认用 vector，因为堆操作需要随机访问
  • 三个适配器都提供了简洁的接口，屏蔽了底层细节
  • 括号匹配是 stack 的经典应用，面试常考

说实话，容器适配器是 STL 里被低估的部分。很多人觉得它们太简单，没什么好学的。但我在实际项目中，这三个适配器用的频率非常高。尤其是 priority_queue，在算法题和系统设计中都是利器。

下一章咱们会深入迭代器，这东西才是 STL 的「胶水」。不过那是后话了，先把这一章的代码敲一遍，尤其是括号匹配器，自己动手改一改，试试能不能支持更多类型的括号。

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

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