40. 用栈实现队列

描述

正如标题所述，你需要使用两个栈来实现队列的一些操作。
队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。
pop和top方法都应该返回第一个元素的值。

样例

比如push(1), pop(), push(2), push(3), top(), pop()，你应该返回1，2和2

挑战

仅使用两个栈来实现它，不使用任何其他数据结构，push，pop 和 top的复杂度都应该是均摊O(1)的

思路

队列加入元素即往栈2里添加元素，如果队列要抛出和查询队列顶端元素，先检查栈1是否为空，如不为空直接对栈1操作，若栈1为空则需要先把元素从栈2转移到栈1中然后再进行抛出和查询操作

代码

public class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
       // do initialization if necessary
       stack1 = new Stack<Integer>();
       stack2 = new Stack<Integer>();
    }
    
    private void stack2ToStack1(){
        while (! stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
    }
    
    public void push(int element) {
        stack2.push(element);
    }

    public int pop() {
        if (stack1.empty() == true){
            this.stack2ToStack1();
        }
        return stack1.pop();
    }

    public int top() {
        if (stack1.empty() == true){
            this.stack2ToStack1();
        }
        return stack1.peek();
    }
}