59-2队列的最大值

下面是题目

下面是题目给出的代码

class MaxQueue {
private:
    queue<int>
public:
    MaxQueue() {
    }

    int max_value() {

    }

    void push_back(int value) {

    }

    int pop_front() {

    }
};

最简单的暴力搜索

class MaxQueue {
    //用数组模拟队列
    int q[20000];
    int begin = 0, end = 0;
public:
    MaxQueue() {
    }
    
    int max_value() {
        int ans = -1;
        for (int i = begin; i != end; ++i)
            ans = max(ans, q[i]);
        return ans;
    }
    
    void push_back(int value) {
        q[end++] = value;
    }
    
    int pop_front() {
        if (begin == end)
            return -1;
        return q[begin++];
    }
};

与155 最小栈不同，我们如果要维护一个最大队列，很难用pair实现

class MaxQueue {
public:
    MaxQueue() {

    }
    
    int max_value() {
        return que.empty()?-1:dq.front();
    }
    
    void push_back(int value) {
        que.push(value);
//更新deque双端队列，把比value小的全部pop，就是在queue队列中的第一大，第二大。。。
        while(!dq.empty()&&dq.back()<value)
            dq.pop_back();
        dq.push_back(value);
    }
    
    int pop_front() {
        if(que.empty())
            return -1;
        int t=que.front();
        que.pop();
//出队列的时候要判断一下是不是把当前的最大值给pop掉了，如果是，那么更新deque
        if(t==dq.front())
            dq.pop_front();
        return t;
    }
private:
    queue<int> que;
    deque<int> dq;
};