C++ STL 容器适配器详解：Stack、Queue 与 Priority Queue

标准库中的 Queue

基本概念

Queue 遵循先进先出（FIFO）原则，允许在队尾插入，队头删除。

常用接口

模拟实现

namespace Queue {
    template<class T, class Con = std::deque<T>>
    class queue {
    public:
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_front(); }
        T& front() { return _c.front(); }
        T& back() { return _c.back(); }
        bool empty() const { return _c.empty(); }
    private:
        Con _c;
    };
}

标准库中的 Priority Queue

基本概念

Priority Queue 是一种以堆为底层结构的优先队列。默认情况下采用最大堆，即每次取出优先级最高的元素。可以通过自定义比较器实现最小堆。

常用接口

使用示例

默认创建的是大堆，如果需要小堆，可以传入 std::greater 比较器：

#include <queue>
#include <functional>

std::priority_queue<int> pq; // 大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; // 小堆

若存放自定义类型，需重载比较运算符。例如处理日期时：

class Date {
public:
    int year, month, day;
    bool operator<(const Date& d) const {
        if (year != d.year) return year < d.year;
        if (month != d.month) return month < d.month;
        return day < d.day;
    }
};

std::priority_queue<Date> pq; // 默认大堆，取最新日期

结语

掌握这些容器适配器能显著提升开发效率。理解其底层原理有助于在性能敏感的场景做出更合适的选择。