C++ STL 容器适配器详解：Stack、Queue 与 Priority Queue 的本质与实现

2. 队列（queue）

队列遵循先进先出（FIFO）原则。默认底层容器同样为 deque。

• push：在队尾插入，对应 push_back。
• pop：删除队头数据，对应 pop_front。
• front / back：分别获取队头和队尾数据。

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(); }
    bool empty()const { return _con.empty(); }
    size_t size()const { return _con.size(); }
private:
    Container _con;
};

3. 优先队列（priority_queue）

这是最复杂的一个。它默认使用 vector 作为底层容器，并基于堆（heap）算法维护优先级。默认是大根堆，即每次取出的都是最大值。

它的核心在于通过仿函数（Functor）控制排序规则。插入元素后会自动调整结构以满足优先级规则。

特性测试： 如果不指定比较器，默认建大堆，输出结果为降序。如果希望升序，可以传入小堆的比较器。

void test01() {
    priority_queue<int> pq; // 默认大堆
    pq.push(5); pq.push(2); pq.push(4);
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
}

三、仿函数（Functor）

为了让优先队列支持不同的排序规则（升序/降序），C++ 引入了仿函数的概念。仿函数本质是一个重载了 operator() 运算符的类，使得对象可以像函数一样被调用。

在优先队列中，第三个模板参数就是仿函数类型。我们可以自定义比较逻辑。

template<class T>
class Less {
public:
    bool operator()(const T& x, const T& y) {
        return x < y; // 小堆逻辑
    }
};

template<class T>
class Greater {
public:
    bool operator()(const T& x, const T& y) {
        return x > y; // 大堆逻辑
    }
};

四、模拟实现完整代码

为了加深理解，下面给出一个完整的模拟实现示例。注意修复了一些细节，比如返回类型应为 size_t，以及统一命名规范。

#include<iostream>
#include<vector>
#include<deque>
using namespace std;

// 仿函数定义
template<class T>
class Less {
public:
    bool operator()(const T& x, const T& y) {
        return x < y;
    }
};

template<class T>
class Greater {
public:
    bool operator()(const T& x, const T& y) {
        return x > y;
    }
};

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

    // Queue 实现
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(); }
    bool empty()const { return _con.empty(); }
    size_t size()const { return _con.size(); }
private:
    Container _con;
};

    // Priority Queue 实现
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue {
public:
    size_t size()const { return _con.size(); }
    const T& top() { return _con.front(); }
    
    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);
    }

    bool empty()const { return _con.empty(); }

private:
    Container _con;

    // 向上调整建堆
    void AdjustUp(int child) {
        Compare com;
        int parent = (child - 1) / 2;
        while (child >= 0) {
            if (com(_con[parent], _con[child])) {
                swap(_con[parent], _con[child]);
                child = parent;
                parent = (child - 1) / 2;
            } else break;
        }
    }

    // 向下调整建堆
    void AdjustDown(int parent) {
        Compare com;
        int child = 2 * parent + 1;
        while (child < _con.size()) {
            if ((child + 1) < _con.size() && com(_con[child], _con[child + 1])) {
                child++;
            }
            if (com(_con[parent], _con[child])) {
                swap(_con[parent], _con[child]);
                parent = child;
                child = 2 * parent + 1;
            } else break;
        }
    }
};
}

通过以上模拟，我们可以清晰地看到容器适配器是如何'借用'底层容器的能力，并通过限制接口和添加额外逻辑（如堆调整）来实现特定功能的。在实际开发中，理解这些底层机制有助于我们在性能敏感的场景下做出更合适的选择。