【剑指 Offer】59 - II. 队列的最大值

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

1. 两个队列

   解题思路：

   • 一个队列实现左进右出，存放所有进来的数
   • 一个队列用来取最大值（每次取最大值可以直接取，不用计算），也就是入队之前把左边小于它的值删除，这样当最大值出队后，后面还是会实时的有此队列的最大值（队头）

   详细代码如下：

   class MaxQueue {
       Deque q1=null;
       Deque q2=null;
       public MaxQueue() {
           q1=new linkedList<>();
           q2=new linkedList<>();
       }
   
       public int max_value() {
           return q1.isEmpty()?-1:q2.getFirst();
       }
   
       public void push_back(int value) {
           q1.addLast(value);
           while(!q2.isEmpty()&&value>q2.getLast()){
               q2.removeLast();
           }
           q2.addLast(value);
       }
   
       public int pop_front() {
           if (q1.isEmpty()) return -1;
           if (q1.getFirst().equals(q2.getFirst())) {
               q2.removeFirst();
           }
           return q1.removeFirst();
       }
   }