Leetcode - Implement Queue using Stacks

My code:

class MyQueue {
    Stack<Integer> st = new Stack<Integer>();
    // Push element x to the back of queue.
    public void push(int x) {
        Stack<Integer> temp = new Stack<Integer>();
        while (!st.isEmpty()) {
            temp.push(st.pop());
        }
        st.push(x);
        while (!temp.isEmpty()) {
            st.push(temp.pop());
        }
    }

    // Removes the element from in front of queue.
    public void pop() {
        st.pop();
    }

    // Get the front element.
    public int peek() {
        return st.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return st.isEmpty();
    }
}

我采用的还是最简单的做法。所以，
push O(n)
pop O(1)

然后看了下答案，发现有更好的方法。

My code:

class MyQueue {
    Stack<Integer> st1 = new Stack<Integer>();
    Stack<Integer> st2 = new Stack<Integer>();
    int front = 0;
    // Push element x to the back of queue.
    public void push(int x) {
        if (st1.isEmpty()) {
            front = x;
        }
        st1.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (st2.isEmpty()) {
            while (!st1.isEmpty()) {
                st2.push(st1.pop());
            }
        }
        st2.pop();
    }

    // Get the front element.
    public int peek() {
        if (!st2.isEmpty()) {
            return st2.peek();
        }
        return front;
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return st1.isEmpty() && st2.isEmpty();
    }
}

push O(1)
pop amortized time O(1), worst O(n)

就是维护两个栈，每次要pop了，就把第一个栈里面的元素全部pop到第二个栈上，正好reverse下，然后以后pop都先从这第二个栈pop，没了之后，再去栈1 拿元素进来。

reference:
https://leetcode.com/articles/implement-queue-using-stacks/

Anyway, Good luck, Richardo! -- 09/11/2016