队列-栈 互相转换

232. 用栈实现队列

225. 用队列实现栈

用栈实现队列

题目详情可见 用栈实现队列

该部分介绍用双栈模拟队列的所有功能！！

假如我们现在push了两个元素到队列中，效果如下图所示：

如果我们现在需要pop或者peek元素怎么办？？

可以先把 inStack 中的元素转移到 outStack 中，然后在 outStack 中进行pop或者peek操作，效果如下图所示：

而且此时顺序也是正确的

那我们什么时候把 inStack 中的元素转移到 outStack 中呢？

很明显在 outStack 为空的时候，一次性把 inStack 所有的元素转移到 outStack 中

详细代码如下：

xxxxxxxxxx
class MyQueue {

    private Stack<Integer> outStack;
    private Stack<Integer> inStack;

    public MyQueue() {
        outStack = new Stack<>();
        inStack = new Stack<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) inToOut();
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) inToOut();
        return outStack.peek();
    }
    
    // 当 outStack 和 inStack 中的元素均为空的时候，模拟队列才为空
    public boolean empty() {
        return outStack.isEmpty() && inStack.isEmpty();
    }

    // 转移元素
    private void inToOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

用队列实现栈

题目详情可见 用队列实现栈

该部分介绍用单个队列来模拟栈的所有功能！！

主要分析如何实现下面两个功能

• int pop()移除并返回栈顶元素
• int top()返回栈顶元素

如下图所示，对于上面两个功能，首先肯定需要弹出元素 1 和 2，剩下的元素 3 才是我们需要移除或者返回的元素

那弹出的元素 1 和 2 怎么处理呢？从队尾放回去就行了！简单粗暴，哈哈哈哈哈。如下图所示：

根据上面的思路，我们可以很快实现：

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.add(x);
    }
    
    public int pop() {
        moveToBack();
        return queue.poll();
    }
    
    public int top() {
        moveToBack();
        int top = queue.poll();
        queue.add(top);
        return top;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    private void moveToBack() {
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) queue.add(queue.poll());
    }
}