队列实现max操作，要求尽量提高效率。

结合之前实现的 maxStack 和 用两个stack 实现一个Queue， 实现 MaxQueue

 

import java.util.Stack;

public class MaxQueue {
    MaxStack in = new MaxStack();
    MaxStack out = new MaxStack();

public void enqueue(Integer a) {
        in.push(a);
    }

public Integer dequeue() {
        shiftItems();
return out.pop();
    }

public Integer peek() {
        shiftItems();
return out.peek();
    }

public Integer max() {
return Math.max(in.isEmpty() ? Integer.MIN_VALUE : in.max(), out.isEmpty() ? Integer.MIN_VALUE : out.max());
    }

private void shiftItems() {
if (!out.isEmpty())
return;
while (!in.isEmpty()) {
            out.push(in.pop());
        }
    }

public static void main(String[] args) {
        MaxQueue queue = new MaxQueue();
        queue.enqueue(1);
        System.out.println(queue.max());
        queue.enqueue(2);
        System.out.println(queue.max());
        queue.enqueue(3);
        System.out.println(queue.max());
        queue.enqueue(4);
        System.out.println(queue.max());
        queue.dequeue();
        System.out.println(queue.max());
        queue.dequeue();
        System.out.println(queue.max());
        queue.dequeue();
        System.out.println(queue.max());

    }
}

class MaxStack {
    Stack<Integer> val = new Stack<Integer>();
    Stack<Integer> max = new Stack<Integer>();

public boolean isEmpty() {
return val.isEmpty();
    }

public void push(Integer a) {
        val.push(a);
if (max.isEmpty() || a >= max.peek())
            max.push(a);
    }

public Integer pop() {
        Integer out = val.pop();
if (out == max.peek())
            max.pop();
return out;
    }

public Integer peek() {
return val.peek();
    }

public Integer max() {
return max.peek();
    }
}