使用双端队列维护单调递减序列，1. 插入时移除尾部较小值并加入新元素；2. 出队时若为最大值则同步移除；3. 队首即为当前最大值，实现O(1)查询。
在C++中实现队列的获取最大值功能，不能直接通过标准库std::queue完成，因为其不支持高效查询最大值。为了实现O(1)时间获取队列当前最大值，通常使用双端队列（deque）辅助维护一个单调递减队列。
基本思路：用双端队列维护最大值
我们创建一个普通队列用于存储元素，同时用一个std::deque维护当前队列中的候选最大值，保证其前端始终是当前队列的最大值。
关键点：
- 每当插入元素时，从双端队列尾部移除所有小于当前元素的值，再将当前元素加入尾部。
- 这样双端队列保持单调递减，首元素即为当前最大值。
- 出队时，若出队元素等于双端队列首部，则将其从双端队列中移除。
代码实现示例
#include <iostream> #include <queue> #include <deque> class MaxQueue { private: std::queue<int> data; // 存储实际元素 std::deque<int> max_deque; // 维护最大值，单调递减 public: void push(int value) { data.push(value); // 移除所有小于value的元素，保持递减 while (!max_deque.empty() && max_deque.back() < value) { max_deque.pop_back(); } max_deque.push_back(value); } void pop() { if (data.empty()) return; int value = data.front(); data.pop(); // 如果弹出的值是当前最大值，也从max_deque中移除 if (value == max_deque.front()) { max_deque.pop_front(); } } int getMax() const { if (max_deque.empty()) { throw std::runtime_error("Queue is empty"); } return max_deque.front(); } bool empty() const { return data.empty(); } int front() const { if (data.empty()) { throw std::runtime_error("Queue is empty"); } return data.front(); } };
使用示例
int main() { MaxQueue mq; mq.push(3); mq.push(1); mq.push(4); mq.push(2); std::cout << "Current max: " << mq.getMax() << "n"; // 输出 4 mq.pop(); // 弹出3 std::cout << "Current max: " << mq.getMax() << "n"; // 仍为4 mq.pop(); // 弹出1 mq.pop(); // 弹出4，此时max_deque也弹出4 std::cout << "Current max: " << mq.getMax() << "n"; // 输出 2 return 0; }
该方法中，每个元素最多入队和出队一次，因此push、pop、getMax操作的均摊时间复杂度均为O(1)，适合高频查询最大值的场景。
立即学习“C++免费学习笔记（深入）”；
基本上就这些，核心在于用双端队列维护单调性，从而快速获取最大值。