232. 用栈实现队列

leetcode链接：
https://leetcode.cn/problems/implement-queue-using-stacks/

题目分析

使用两个堆栈，其中 L 用于临时的反转Stack。以此来实现先进先出的现象。所以可以直接理解为 R 就是Queue（队列）。

方案一

class MyQueue {

    private Stack stackLeft = null;
    private Stack stackRight = null;

    public MyQueue() {
        stackLeft = new Stack<Integer>();
        stackRight = new Stack<Integer>();
    }
    
    public void push(int x) {
        // 将在右侧的堆栈全部弹出放入到左侧堆栈
        while (!stackRight.isEmpty()){
            Integer pop = (Integer)stackRight.pop();

            stackLeft.push(pop);
        }

        stackRight.push(x);

        while (!stackLeft.isEmpty()){
            Integer pop = (Integer)stackLeft.pop();

            stackRight.push(pop);
        }
    }
    
    public int pop() {
        return (Integer) stackRight.pop();
    }
    
    public int peek() {
        return (Integer) stackRight.peek();
    }
    
    public boolean empty() {
        return stackRight.isEmpty();
    }
}

因为Stack被弃用，使用 Deque 来实现相关代码，被启用的相关参考链接见：
https://www.yuanql.top/2023/07/03/02_leetcode/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80/

只是修改了堆栈初始化的状态，相关修改后的代码如下：

private Deque stackLeft = null;  
private Deque stackRight = null;  
  
public MyQueue() {  
stackLeft = new LinkedList<Integer>();  
stackRight = new LinkedList<Integer>();  
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.2 MB,击败了84.51% 的Java用

官方题解

https://leetcode.cn/problems/implement-queue-using-stacks/solution/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/

思路

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。
每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

代码

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/implement-queue-using-stacks/solution/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

• 时间复杂度：push 和 empty 为 O(1)，pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。
• 空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。