题目：

队列的最大值。
请定义一个队列并实现函数max得到队列里的最大值，要求函数max、push_back和pop_front的时间复杂度都是O（1）。

 

题解：

使用队列，操持队列的排序为从大到小的顺序，最大值一直在队头

 

 1 class Queue
 2 {
 3 public:
 4     void push_back(const int &num)
 5     {
 6         List.push(num);
 7         while (!maxNum.empty() && maxNum.back() < num)maxNum.pop_back();
 8         maxNum.push_back(num);
 9     }
10     void pop_front()
11     {
12         if (!maxNum.empty() && maxNum.front() == List.front())maxNum.pop_front();
13         if(!List.empty())List.pop();
14     }
15     int getMax()
16     {
17         if (!maxNum.empty())return maxNum.front();
18         return -1;
19     }
20 private:
21     queue<int>List;
22     deque<int>maxNum;
23 };