[数据结构与算法]队列的最大值

题目出处：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

?思路1：队列是一个元素先进先出的数据结构

1. 要在O(1)的时间复杂度下找出元素的最大值。可以考虑用map存放队列中的元素，其底层是红黑树，输的根节点存放数据的最大值。因此需要修改map的默认排序。
2. 要在O(1)的时间复杂度下插入和弹出元素，则可以用deque实现。

class MaxQueue {
private:
    deque<int> dq;
    map<int, int, greater<int>> mp;    
public:
    MaxQueue() {
        dq.clear();
        mp.clear(); 
    }
    
    int max_value() {
        if(mp.size() == 0){
           return -1; 
        }
        return mp.begin()->first; 
    }
    
    void push_back(int value) {
        dq.push_back(value);
        ++mp[value];
    }
    
    int pop_front() {
        if(dq.empty()){
           return -1;  
        }
        int value = dq.front();
        dq.pop_front();
        --mp[value];
        if(mp[value] == 0){
            mp.erase(value);
        }
        return value; 
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

思路2：队列是一个元素先进先出的数据结构

deque和queue

class MaxQueue {
    queue<int> q;
    deque<int> d;
public:
    MaxQueue() {
    }
    
    int max_value() {
        if (d.empty())
            return -1;
        return d.front();
    }
    
    void push_back(int value) {
        while (!d.empty() && d.back() < value) {
            d.pop_back();
        }
        d.push_back(value);
        q.push(value);
    }
    
    int pop_front() {
        if (q.empty())
            return -1;
        int ans = q.front();
        if (ans == d.front()) {
            d.pop_front();
        }
        q.pop();
        return ans;
    }
};