使用双端队列维护单调递减序列，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++免费学习笔记（深入）”；
基本上就这些，核心在于用双端队列维护单调性，从而快速获取最大值。
