【双栈实现队列】Java——Stack类-526互联

题意：双栈实现队列；要求每个入队、出队操作均摊O(1)复杂度

题解：
用一个栈in维护入队元素，另一个栈out维护出队元素

出队或取队头元素：首先判断栈out是否为空，如果为空，将栈in中的元素pop()到栈out中，那么栈out栈顶元素即为原队列队头元素。（米奇妙妙屋啊～）

判断队空：栈in和栈out都空时队空

Java代码

class MyQueue {
    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();
    public MyQueue() {

    }
    
    public void push(int x) {
        in.push(x);
    }
    
    public int pop() {
        if(out.empty()) {
            inToOut();
        }
        return out.pop();
    }
    
    public int peek() {
        if(out.empty()) {
            inToOut();
        }
        return out.peek();
    }
    
    public boolean empty() {
        return in.empty() && out.empty();
    }

    public void inToOut() {
        while(!in.empty()) {
            out.push(in.pop());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */