c++中如何实现队列的最大值功能_c++队列最大值实现方法-C++-PHP中文网

c++中如何实现队列的最大值功能_c++队列最大值实现方法

穿越時空

发布： 2025-09-27 18:19:01

原创

974人浏览过

使用双端队列维护单调递减序列，1. 插入时移除尾部较小值并加入新元素；2. 出队时若为最大值则同步移除；3. 队首即为当前最大值，实现O(1)查询。

c++中如何实现队列的最大值功能_c++队列最大值实现方法

在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)，适合高频查询最大值的场景。