单调队列完整代码，c++

单调队列是一种特殊的队列数据结构，其中元素按照某种单调性（如升序或降序）排列。在插入新元素时，如果它破坏了这种单调性，那么队头的元素会被弹出，直到保持单调性为止。

以下是C++实现单向单调递增队列的简单示例（假设我们只支持整数并按升序排列）：

#include <iostream>
#include <vector>

template <typename T>
class MonotonicQueue {
private:
    std::vector<T> queue;
    bool increasing;

public:
    // 构造函数，初始化为递增队列
    MonotonicQueue(bool is_increasing = true) : increasing(is_increasing) {}

    // 插入操作，维护单调性
    void push(T value) {
        if (increasing && value <= queue.empty() ? T{} : queue.back()) {
            queue.push_back(value);
        } else {
            while (!queue.empty() && (increasing ? queue.back() > value : queue.back() < value)) {
                queue.pop_back();
            }
            queue.push_back(value);
        }
    }

    // 删除操作，返回队头元素，不做任何处理
    T pop() {
        if (!queue.empty()) {
            T top = queue.front();
            queue.erase(queue.begin());
            return top;
        } else {
            throw std::out_of_range("Queue is empty");
        }
    }

    // 检查队列是否为空
    bool empty() const {
        return queue.empty();
    }
};

int main() {
    MonotonicQueue<int> inc_queue(true);  // 升序队列
    inc_queue.push(5);
    inc_queue.push(7);
    inc_queue.push(4);  // "4"会将"5"移除，因为违反了升序

    std::cout << "Popped element: " << inc_queue.pop() << std::endl;  // 输出 4

    return 0;
}