容器适配器深度解析：STL 中的 stack、queue 与优先队列底层实现

容器适配器深度解析：从 STL 的 stack、queue 到优先队列的底层实现

1. 栈的介绍和使用

1.1 栈的介绍

栈（stack）是一种后进先出（LIFO）的数据结构，它允许在一端进行插入和删除操作。在 C++ STL 中，stack 是一个容器适配器，提供了一组特定的成员函数来访问其元素。

1.2 栈的使用

函数	接口说明
stack()	构造空的栈
empty()	检测 stack 是否为空
size()	返回 stack 中元素的个数
top()	返回栈顶元素的引用
push()	将元素 val 压入 stack 中
pop()	将 stack 中尾部的元素弹出

最小栈实现

最小栈能够在 O(1) 时间内获取栈中的最小元素。

class MinStack {
public:
    void push(int x) {
        // 压栈时，先将元素保存到_elem
        _elem.push(x);
        // 如果 x 小于_min 中栈顶的元素，将 x 再压入_min 中
        if (_min.empty() || x <= _min.top()) {
            _min.push(x);
        }
    }

    void pop() {
        // 如果_min 栈顶的元素等于出栈的元素，_min 顶的元素要移除
        if (_min.top() == _elem.top()) {
            _min.pop();
        }
        _elem.pop();
    }

    int top() {
        return _elem.top();
    }

    int getMin() {
        return _min.top();
    }

private:
    std::stack<int> _elem; // 保存栈中的元素
    std::stack<int> _min;  // 保存栈的最小值
};

栈的弹出压入序列

验证一个序列是否是栈的弹出序列。

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> st;
    int j = 0;
    for (int i = 0; i < pushed.size(); ++i) {
        st.push(pushed[i]);
        while (!st.empty() && st.top() == popped[j]) {
            st.pop();
            j++;
        }
    }
    return st.empty();
}

逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (size_t i = 0; i < tokens.size(); ++i) {
            string& str = tokens[i];
            // str 为数字
            if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
                s.push(atoi(str.c_str()));
            } else {
                // str 为操作符
                int right = s.top(); s.pop();
                int left = s.top(); s.pop();
                switch (str[0]) {
                    case '+': s.push(left + right); break;
                    case '-': s.push(left - right); break;
                    case '*': s.push(left * right); break;
                    case '/': s.push(left / right); break;
                }
            }
        }
        return s.top();
    }
};

1.3 stack 的模拟实现

以下是使用容器适配器模式实现的 stack，支持自定义底层容器（默认使用 deque）：

#pragma once
#include <deque>

namespace bit {
    // container 适配器实现 stack
    template<class T, class Container = deque<T>>
    class stack {
    public:
        void push(const T& x) { _con.push_back(x); }
        void pop() { _con.pop_back(); }
        const T& top() const { return _con.back(); }
        size_t size() const { return _con.size(); }
        bool empty() { return _con.empty(); }

    private:
        Container _con;
    };
}

2. 队列的介绍和使用

2.1 队列的介绍

队列是一种先进先出（FIFO）的数据结构，元素从队尾入队列，从队头出队列。在 C++ STL 中，queue 是一个容器适配器。

queue 的特点：

1. 队列是一种容器适配器，专门用于在 FIFO 上下文（先进先出）中操作
2. 元素从队尾入队列，从队头出队列
3. 底层容器可以是 deque 或 list，默认使用 deque

2.2 queue 的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素 val 入队列
pop()	将队头元素出队列

2.3 queue 的模拟实现

使用容器适配器模式实现的 queue，支持自定义底层容器：

#pragma once
#include <deque>

namespace bit {
    template<class T, class Container = deque<T>>
    class queue {
    public:
        void push(const T& x) { _con.push_back(x); }
        void pop() { _con.pop_front(); }
        const T& front() const { return _con.front(); }
        const T& back() const { return _con.back(); }
        size_t size() const { return _con.size(); }
        bool empty() { return _con.empty(); }

    private:
        Container _con;
    };
}

3. 优先队列的介绍和使用

3.1 priority_queue 的介绍

优先队列是一种容器适配器，它的第一个元素总是它所包含的元素中最大的（默认大堆）。

priority_queue 的特点：

1. 第一个元素总是最大的（默认大堆）
2. 类似于堆，可以随时插入元素，只能检索最大堆元素
3. 默认使用 vector 作为底层容器
4. 支持随机访问迭代器

3.2 priority_queue 的使用

函数声明	接口说明
priority_queue()	构造一个空的优先级队列
priority_queue(first, last)	用迭代器范围构造优先级队列
empty()	检测优先级队列是否为空
top()	返回优先级队列中最大 (最小) 元素
push(x)	在优先级队列中插入元素 x
pop()	删除优先级队列中最大 (最小) 元素

使用示例：

#include <vector>
#include <queue>
#include <functional>

void TestPriorityQueue() {
    // 默认情况下，创建的是大堆，其底层按照小于号比较
    vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
    priority_queue<int> q1;
    for (auto& e : v) q1.push(e);
    cout << q1.top() << endl; // 输出 9

    // 创建小堆，将第三个模板参数换成 greater 比较方式
    priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl; // 输出 0
}

注意：

1. 默认情况下，priority_queue 是大堆
2. 如果要创建小堆，需要指定第三个模板参数为 greater<T>
3. 如果存放自定义类型，需要在自定义类型中提供 > 或 < 的重载

3.3 priority_queue 的模拟实现

以下是完整的优先队列模拟实现，包含大堆和小堆支持：

#pragma once
#include <vector>

namespace bit {
    // 仿函数类：Less（升序/大堆）
    template<class T>
    class Less {
    public:
        bool operator()(const T& x, const T& y) {
            return x < y;
        }
    };

    // 仿函数类：Greater（降序/小堆）
    template<class T>
    class Greater {
    public:
        bool operator()(const T& x, const T& y) {
            return x > y;
        }
    };

    // 优先队列实现
    // 模板参数：
    // T - 元素类型
    // Container - 底层容器，默认 vector<T>
    // Compare - 比较器，默认 Less<T>（大堆）
    template<class T, class Container = vector<T>, class Compare = Less<T>>
    class priority_queue {
    public:
        // 向上调整（插入时使用）
        void AdjustUp(int child) {
            Compare com;
            size_t parent = (child - 1) / 2;
            while (child > 0) {
                // 使用仿函数进行比较
                if (com(_con[parent], _con[child])) {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                } else {
                    break;
                }
            }
        }

        // 向下调整（删除时使用）
        void AdjustDown(int parent) {
            int child = parent * 2 + 1;
            Compare com;
            while (child < _con.size()) {
                // 找出较大（或较小）的孩子
                if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
                    ++child;
                }
                // 如果父节点小于（或大于）孩子节点，交换
                if (com(_con[parent], _con[child])) {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                } else {
                    break;
                }
            }
        }

        // 插入元素
        void push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }

        // 删除堆顶元素
        void pop() {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }

        // 获取堆顶元素
        const T& top() {
            return _con[0];
        }

        // 获取元素个数
        size_t size() const {
            return _con.size();
        }

        // 判断是否为空
        bool empty() const {
            return _con.empty();
        }

    private:
        Container _con;
    };
}

4. 容器适配器

4.1 什么是适配器

适配器是一种设计模式，将一个类的接口转换成客户希望的另外一个接口。

4.2 STL 标准库中 stack 和 queue 的底层结构

stack 和 queue 在 STL 中称为容器适配器，它们只是对其他容器的接口进行了包装。STL 中 stack 和 queue 默认使用 deque 作为底层容器。

4.3 deque 的简单介绍

4.3.1 deque 的原理介绍

deqeue（双端队列）是一种双开口的'连续'空间的数据结构：

• 可以在头尾两端进行插入和删除操作，时间复杂度为 O(1)
• 与 vector 比较，头插效率高，不需要搬移元素
• 与 list 比较，空间利用率比较高

deqeue 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际类似于一个动态的二维数组。

4.3.2 deque 的缺陷

• 不适合遍历，因为迭代器要频繁检测是否移动到小空间边界
• 在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list
• deque 的应用并不多，主要作为 stack 和 queue 的底层数据结构

4.4 为什么选择 deque 作为 stack 和 queue 的底层默认容器

1. stack 和 queue 不需要遍历（因此没有迭代器），只需要在固定的一端或两端操作
2. 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）
3. queue 中的元素增长时，deque 不仅效率高，而且内存使用率高

4.5 容器适配器设计的关键点

从上面的模拟实现可以看出容器适配器的核心设计思想：

1. 模板参数灵活性：
   • stack 和 queue 都支持自定义底层容器
   • priority_queue 支持自定义比较器，实现大堆/小堆切换
2. 接口统一性：
   • 所有适配器都提供 push、pop、top/front/back、size、empty 等标准接口
   • 隐藏底层容器的具体实现细节
3. 代码复用：
   • 通过组合已有的容器实现新功能
   • 减少代码重复，提高开发效率

总结

栈、队列和优先队列是三种基础且重要的数据结构，在 C++ STL 中通过容器适配器的方式实现。理解它们的底层原理、使用场景和实现方式，对于提高编程能力和解决实际问题都有重要意义。

通过模拟实现这些数据结构，我们可以：

1. 深入理解容器适配器设计模式
2. 掌握仿函数在泛型编程中的应用
3. 理解堆算法的实现原理
4. 学会如何设计灵活的、可扩展的数据结构

在实际开发中，根据具体需求选择合适的数据结构：

• 需要后进先出操作时选择栈
• 需要先进先出操作时选择队列
• 需要快速获取最大/最小值时选择优先队列