用Java实现一个查询最大元素值的时间复杂度为O(1)的队列

解题思路：因为队列是FIFO（先进先出）型数据结构，而栈是LIFO（后进先出/先进后出）型数据结构，因此可以用2个栈可以实现队列（一个栈是入栈，负责队列的入队操作；另一个栈是出栈，负责队列的出队操作）。
此题要求更为严格：要实现查询最大值的时间复杂度为O(1)，则必须先将最大值挑选出放在其中一个栈的栈顶。

可以先实现一个O(1)时间复杂度实现出栈的最大值栈，然后用2个最大值栈实现最大值队列即可。
具体操作：

1.先实现一个O(1)时间复杂度实现出栈那段最大值栈。
此最大值栈可由2个普通栈构成数据栈与最大值栈（其中一个负责存储数据：数据栈stack1；另一个负责存储数据中的最大值：stack2）

class MaxStack{
    Deque stack1;  //stack1为存储数据栈
    Deque stack2;  //stack2栈存储了stack1中的最大值元素

    private void Twotack() {
        stack1 = new LinkedList();
        stack2 = new LinkedList();
    }
    
    //入栈元素
    public void Push(int value){
        stack1.push(value);     //不论存入的值是什么，必须都存入数据栈
        if(stack2.isEmpty()){   //最大值元素栈为空，直接将存入数据栈的值放入最大值栈
            stack2.push(value);
        }else if(value >= stack2.peek()){
            stack2.push(value);  //若value值大于最大值栈的栈顶值，将value值存入最大值元素栈（此时最大值为value）
        }
    }

    //返回数据栈的栈顶元素
    public int peek(){
        return stack1.peek();
    }

    //出栈元素
    void Pop(){
        //若stack1与stack2栈顶元素相等,出stack2栈顶元素
        if(stack1.peek() == stack2.peek()){
            stack2.pop();
        }
        stack1.pop();  //数据栈stack1也出栈，表示该元素已经出栈
    }

    //判空,stack1为空，则栈为空
    boolean isEmpty(){
        return stack1.isEmpty();
    }

    //取最大值
    public int Max(){
        if(!stack2.isEmpty())
            return stack2.peek();
    }
}

2.再用2个最大值栈实现一个O(1)时间复杂度的最大值队列

class MaxQueue {

    Deque MaxStack3;   //入栈
    Deque MaxStack4;   //出栈

    public void Queue() {
        MaxStack3 = new LinkedList();
        MaxStack4 = new LinkedList();
    }

    //入队操作
    public void Push(int value){
        MaxStack3.push(value);
    }

    //取队首元素
    public void GetFront(){
        if(MaxStack4.isEmpty()){           //出栈为空且入栈不空 ，将入栈栈顶元素值存入出栈，并将出、入栈栈顶元素同时出栈
            while(!MaxStack3.isEmpty()){   
                MaxStack4.push(MaxStack3.peek());
                MaxStack3.pop();
            }
        }
    }

    //判空操作
    public boolean isEmpty(){
        return MaxStack3.isEmpty() && MaxStack4.isEmpty();
    }

    //取最大值
    public void GetMax(){
        if(!MaxStack3.isEmpty() && !MaxStack4.isEmpty()){
            return MaxStack3.Max() > MaxStack4.Max() ?MaxStack3.Max():MaxStack4.Max();//出入栈都不空，返回2者中的最大值
        }else if(MaxStack3.isEmpty() && !MaxStack4.isEmpty()){
            return MaxStack4.Max();//入栈为空出栈不空，返回出栈最大值
        }else if(!MaxStack3.isEmpty() && MaxStack4.isEmpty()){
            return MaxStack3.Max();//入栈不空出栈为空，返回入栈最大值
        }else {
            throw Error;
        }
    }
}

总结：整个O(1)时间复杂度获取最大值的队列由2个最大值栈构成：
分别是最大值入栈（由2个普通栈构成）、最大值出栈（由2个普通栈构成）。
所以O(1)时间复杂度获取最大值的队列由4个普通栈构成。