Implement Queue by Two Stacks

https://leetcode.com/problems/implement-queue-using-stacks/description/

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. Notes: You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Thoughts

一个stack肯定不能实现queue. 自然想到要用两个. 利用stack和queue顺序相反的性质，用另一个stack把顺序反过来。注意只有2为空才需要从1中倒元素进来, 否则顺序会乱.

Code

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

    public Queue() {
       stack1 = new Stack<Integer>();
       stack2 = new Stack<Integer>();
    }

    public void push(int element) {
        stack1.push(element);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            stack1TO2();
        }
        return stack2.pop();
    }

    public int top() {
        if (stack2.isEmpty()) {
            stack1TO2();
        }
        return stack2.peek();
    }

    private void stack1TO2() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
}

Analysis

做题耗时: 10 min Errors: 1. pop()时直接就把stack1中元素倒往2了. 应该是2有元素就直接pop(), 直到2为空才倒.

平均每个元素进出栈两次，每次O(1)时间。