494. 双队列实现栈

描述

利用两个队列来实现一个栈的功能

样例

push(1)
pop()
push(2)
isEmpty() // return false
top() // return 2
pop()
isEmpty() // return true

思路

一个 queue 用来存所有 push 进来的元素，另一个 queue 用来辅助，在要 top() 或者 pop() 的时候，因为要读取队尾的元素，可以将 queue1 中的元素弹出到只剩一个元素，弹出的元素由 queue2 接收,因为 queue 是先进先出，所以 queue2 中的元素顺序跟原先 queue1 中的元素顺序相同，
这之后 queue1 中剩下的那个元素就是需要的栈顶元素。如果是 top 方法那么只是读取这个元素，所以弹出之后再 offer 回来就可以了。

代码

class Stack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    
    public Stack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    private void moveItems() {
        while (queue1.size() != 1) {
            queue2.offer(queue1.poll());
        }
    }
    // O(1) 的时间操作;
    private void swapQueues() {
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /**
     * push a new item into the stack
     */
    public void push(int value) {
        queue1.offer(value);
    }
    
    /**
     * return the top of the stack
     */
    public int top() {
        moveItems();
        int item = queue1.poll();
        swapQueues();
        // 把元素重新添加到队列中去，保持原样，因为 top 不改变栈中的值
        // 实际上就是先把 queue1 中元素移到 queue2 中去，然后交换两个队列
        // queue1 变成 queue2，queue2 变成 queue1
        queue1.offer(item);
        return item;
    }
    
    /**
     * pop the top of the stack and return it
     */
    public void pop() {
        moveItems();
        queue1.poll();
        swapQueues();
    }
    
    /**
     * check the stack is empty or not.
     */
    public boolean isEmpty() {
        return queue1.isEmpty();
    }
}