Problem

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.

思路

• 沿用Implement Stack by Two Queues的思路是不对的
• 于是改成maintain 一个 stack1, 里面都是pop出来的都是正序
• 所以push只到stack2, pop() 和 peek() 先检查stack1是否空, 若空则将Stack2中的传到stack1, 这样顺序便变成正序了.

public class MyQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    private int size;

    public MyQueue() {
       stack1 = new Stack<>();
       stack2 = new Stack<>();
       size = 0;
    }

    public void push(int element) {
        stack2.push(element);
        size++;
    }

    public int pop() {
        updateQueue1();
        int res = stack1.pop();
        size--;
        return res;
    }

    public int peek() {
        updateQueue1();
        return stack1.peek();
    }

    public boolean empty() {
        return size == 0;
    }

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