232.用栈实现队列

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    public void push(int x) {
        stackIn.push(x);
    }
    public int pop() {
        dumpstackIn();
        return stackOut.pop();
    }
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    public boolean empty() {
        return stackIn.isEmpty() & stackOut.isEmpty();
    }
    // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
    private void dumpstackIn() {
        if (!stackOut.isEmpty()) return;
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

225.用队列实现栈

如动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

/**
     * 使用2个队列
     */
class MyStack {
    Queue<Integer> queue1;  // 和栈一致的队列
    Queue<Integer> queue2;  // 辅助队列
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    public void push(int x) {
        // 先将x放入辅助队列中
        queue2.offer(x);
        // 如果queue中存在元素，将其插入到辅助队列中，使顺序和栈一致
        while(!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        // 将两个队列交换
        Queue tempQueue = queue2;
        queue2 = queue1;
        queue1 = tempQueue;
    }
    public int pop() {
        return queue1.poll();
    }
    public int top() {
        return queue1.peek();
    }
    public boolean empty() {
        return queue1.isEmpty();
    }
}
/**
     * 使用一个队列实现
     */
class MyStack {
    Deque<Integer> queue;
    public MyStack() {
        queue = new ArrayDeque<Integer>();  // 使用双端队列
    }
    public void push(int x) {
        queue.addLast(x);
    }
    public int pop() {
        int size = queue.size();
        size--;
        // 将除最后一个元素外，前面的再次入栈
        while (size-- > 0) {
            queue.addLast(queue.peekFirst());
            queue.pollFirst();
        }
        return queue.pollFirst();
    }
    public int top() {
        return queue.peekLast();
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}