题目

标题和出处

标题：用栈实现队列

出处：232. 用栈实现队列

难度

4 级

题目描述

要求

请你仅使用两个栈实现一个先进先出的队列。实现的队列应该支持普通队列的全部操作（$\text{push}$、$\text{pop}$、$\text{peek}$ 和 $\text{empty}$）。

实现 $\text{MyQueue}$ 类：

• $\text{void push(int x)}$ 将元素 $\text{x}$ 推到队尾。
• $\text{int pop()}$ 移除并返回队首元素。
• $\text{int peek()}$ 返回队首元素。
• $\text{boolean empty()}$ 如果队列是空的，返回 $\text{true}$；否则，返回 $\text{false}$。

注意：

• 你只能使用栈的基本操作，只有在栈顶添加元素、在栈顶查看和删除元素、返回元素个数和判断是否为空的操作是有效的。
• 你所使用的语言也许不支持栈。你可以使用列表或者双端队列来模拟一个栈，只要所有的操作都是标准的栈操作即可。

示例

示例 1：

输入：
$\text{["MyQueue", "push", "push", "peek", "pop", "empty"]}$
$\text{[[], [1], [2], [], [], []]}$
输出：
$\text{[null, null, null, 1, 1, false]}$
解释：
$\text{MyQueue myQueue = new MyQueue();}$
$\text{myQueue.push(1);}$
$\text{myQueue.push(2);}$
$\text{myQueue.peek();}$ // 返回 $\text{1}$
$\text{myQueue.pop();}$ // 返回 $\text{1}$
$\text{myQueue.empty();}$ // 返回 $\text{False}$

数据范围

• $\text{1}\le \text{x}\le \text{9}$
• 最多调用 $\text{100}$ 次 $\text{push}$、$\text{pop}$、$\text{peek}$ 和 $\text{empty}$
• 每次调用 $\text{pop}$ 和 $\text{peek}$ 都是有效的

进阶

你能否实现每个操作均摊时间复杂度为 $\text{O(1)}$ 的队列？换句话说，执行 $\text{n}$ 个操作的总时间复杂度为 $\text{O(n)}$，即使其中一个操作可能花费较长时间。

解法

思路和算法

由于队列的特点是先进先出，因此使用栈实现队列时，需要维护栈内的元素顺序，在出队操作和查看队首元素操作时可以定位到最先添加的元素。

如果不考虑时间复杂度的限制，一种可行的解法是，每次入队操作时维护栈内的元素顺序，使得从栈顶到栈底的元素符合添加顺序。具体做法是，使用两个栈，其中 ${\text{stack}}_1$ 的作用是存储元素，${\text{stack}}_2$ 的作用是辅助操作，入队操作如下：

1. 将 ${\text{stack}}_1$ 的全部元素依次出栈并入栈到 ${\text{stack}}_2$；

2. 将待添加的元素入栈到 ${\text{stack}}_1$；

3. 将 ${\text{stack}}_2$ 的全部元素依次出栈并入栈到 ${\text{stack}}_1$。

完成上述操作后，${\text{stack}}_2$ 为空，${\text{stack}}_1$ 的栈底元素是新添加的元素，${\text{stack}}_1$ 内的其余元素和顺序不变。因此上述操作的效果是在 ${\text{stack}}_1$ 的栈底增加了新添加的元素，${\text{stack}}_1$ 的栈顶和栈底分别对应队首和队尾。

由于每次入队操作都维护了 ${\text{stack}}_1$ 内的元素顺序，因此出队操作和查看队首元素操作的时间复杂度是 $O(1)$，只要对 ${\text{stack}}_1$ 的栈顶元素执行相应的操作即可（移除并返回元素，或者返回元素但不移除）。

判断队列是否为空操作只要判断 ${\text{stack}}_1$ 是否为空即可。

上述做法虽然可以做到出队操作、查看队首元素操作和判断队列是否为空操作的时间复杂度是 $O(1)$，但是当队列内有 $n$ 个元素时，入队操作需要 $2n$ 次出栈操作和 $2n+1$ 次入栈操作，因此入队操作的时间复杂度是 $O(n)$。

为了做到均摊时间复杂度是 $O(1)$，需要使用优化的做法，将 ${\text{stack}}_1$ 用于入队操作，将 ${\text{stack}}_2$ 用于出队操作和查看队首元素操作。

对于入队操作，将待添加的元素入栈到 ${\text{stack}}_1$。

对于出队操作和查看队首元素操作，做法如下：

1. 判断 ${\text{stack}}_2$ 是否为空，如果为空，则将 ${\text{stack}}_1$ 的全部元素依次出栈并入栈到 ${\text{stack}}_2$；

2. 对 ${\text{stack}}_2$ 的栈顶元素执行相应的操作（移除并返回元素，或者返回元素但不移除）。

判断队列是否为空操作需要判断 ${\text{stack}}_1$ 和 ${\text{stack}}_2$ 是否都为空。

优化的做法中，入队操作和判断队列是否为空操作的时间复杂度是 $O(1)$，对于出队操作和查看队首元素操作，由于每个元素最多在两个栈都入栈和出栈各一次，因此均摊时间复杂度是 $O(1)$。

证明

对于优化的做法的正确性证明，需要证明出队操作和查看队首元素操作返回的元素是最先入队的元素。

1. 由于入队操作时将待添加的元素入栈到 ${\text{stack}}_1$，因此 ${\text{stack}}_1$ 从栈底到栈顶的元素顺序符合入队顺序。

2. 出队操作和查看队首元素操作时，如果 ${\text{stack}}_2$ 为空，则将 ${\text{stack}}_1$ 的全部元素依次出栈并入栈到 ${\text{stack}}_2$，此时 ${\text{stack}}_2$ 内的元素顺序和 ${\text{stack}}_1$ 内的元素顺序相反，${\text{stack}}_2$ 的全部元素中，栈顶元素是最先入队的元素。

3. 由于所有的元素在入栈到 ${\text{stack}}_2$ 之前首先会入栈到 ${\text{stack}}_1$，因此 ${\text{stack}}_2$ 内的元素的入队时间一定比 ${\text{stack}}_1$ 的入队时间早，${\text{stack}}_2$ 的栈顶元素是队列的全部元素中最先入队的元素。

代码

class MyQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;

    public MyQueue() {
        stack1 = new ArrayDeque<Integer>();
        stack2 = new ArrayDeque<Integer>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        preparePop();
        return stack2.pop();
    }
    
    public int peek() {
        preparePop();
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    private void preparePop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(1)$，入队和判断队列是否为空操作的时间复杂度都是 $O(1)$，出队和查看队首元素操作的均摊时间复杂度都是 $O(1)$。每个元素最多在两个栈都入栈和出栈各一次。

• 空间复杂度：$O(n)$，其中 $n$ 是队列内元素个数。需要使用栈存储元素。