232. 用栈实现队列

查看题目

简单

栈

队列

中频

解法一：栈

时间复杂度：O(1) amortized | 空间复杂度：O(n) | 推荐使用

动画演示

操作序列

代码实现

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());
        }
    }
}

时间复杂度：O(1) amortized

空间复杂度：O(n)

使用两个栈实现队列的思路是： 1. 使用一个输入栈（inStack）处理入队操作，所有元素先入栈到 inStack 2. 使用一个输出栈（outStack）处理出队和查看队首元素操作 3. 当需要出队或查看队首元素时，如果 outStack 为空，将 inStack 中的所有元素依次弹出并压入 outStack，这样元素顺序就被反转，符合队列的先进先出特性 4. 这样设计的好处是，每个元素最多只会被压入和弹出两次，因此平均时间复杂度为 O(1) 5. 空间复杂度为 O(n)，因为需要存储所有元素