[Leetcode][232. 用栈实现队列] 顺序翻转,使用两个栈:一个入队,一个出队

By Long Luo

Leetcode 232. 用栈实现队列 ,难度为Easy


  1. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push\texttt{push}pop\texttt{pop}peek\texttt{peek}empty\texttt{empty}):

实现MyQueue\texttt{MyQueue}类:

  • void push(int x)\texttt{void push(int x)}将元素xx推到队列的末尾
  • int pop()\texttt{int pop()}从队列的开头移除并返回元素
  • int peek()\texttt{int peek()}返回队列开头的元素
  • boolean empty()\texttt{boolean empty()}如果队列为空,返回true\textit{true};否则,返回false\textit{false}

说明:

你 只能 使用标准的栈操作 —— 也就是只有push to top, peek/pop from top, size, 和is empty操作是合法的。
你所使用的语言也许不支持栈。你可以使用list或者deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]

解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示:

  • 1 <= x <= 9
  • 最多调用100100push\texttt{push}pop\texttt{pop}peek\texttt{peek}empty\texttt{empty}
    假设所有操作都是有效的 (例如,一个空的队列不会调用pop\texttt{pop}或者peek\texttt{peek}操作)

进阶:

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


之前我们已经实现了 225. 用队列实现栈 ,今天我们来学习如何用队列来实现栈。

因为队列是FIFO,而栈是LIFO,所以我们需要用到两个栈,用其中一个来反转元素的入队顺序,而另一个则用来存储元素的最终顺序。

2个栈 (push - O(n), pop - O(1))

使用 22 个栈 stack1\textit{stack}_1stack2\textit{stack}_2stack1\textit{stack}_1 作为主栈,而 stack2\textit{stack}_2 是辅助栈。

入栈时:

  1. stack1\textit{stack}_1 中所有的元素移到 stack2\textit{stack}_2 中;
  2. stack2\textit{stack}_2 中压入新元素;
  3. stack2\textit{stack}_2 中所有的元素弹出,再把弹出的元素压入 stack1\textit{stack}_1

代码如下所示:

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
36
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;

public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}

public void push(int x) {
if (stack1.empty()) {
stack1.push(x);
return;
}

while (!stack1.empty()) {
stack2.push(stack1.pop());
}
stack2.push(x);
while (!stack2.empty()) {
stack1.push(stack2.pop());
}
}

public int pop() {
return stack1.pop();
}

public int peek() {
return stack1.peek();
}

public boolean empty() {
return stack1.empty() && stack2.empty();
}
}

复杂度分析

  • 时间复杂度:入队操作 O(n)O(n),其余操作都是 O(1)O(1),其中 nn 是队列内的元素个数。

    • push()\texttt{push()} 操作对于除了新元素之外的所有元素,它们都会被压入两次,弹出两次。新元素只被压入一次,弹出一次。这个过程产生了 4n+24n + 2 次操作,其中 nn 是队列的大小。由于压入操作和弹出操作的时间复杂度为 O(1)O(1), 所以时间复杂度为 O(n)O(n)
    • pop()\texttt{pop()} 出队操作对应将 stack1\textit{stack}_1 的元素出队,时间复杂度是 O(1)O(1)
    • peek()\texttt{peek()} 获得队首元素操作对应获得 stack1\textit{stack}_1 的前端元素,时间复杂度是 O(1)O(1)
    • empty()\texttt{empty()} 判断队列是否为空操作只需要判断 stack1\textit{stack}_1 是否为空,时间复杂度是 O(1)O(1)
  • 空间复杂度:O(n)O(n),其中 nn 是队列的元素个数。

2个栈 (push - O(1), pop - O(1))

方法一中在 push()\texttt{push()} 操作的次数太多,而进阶要求是实现均摊时间复杂度为 O(1)O(1) 的队列,而方法一中的辅助栈只在 push()\texttt{push()} 时有用,能否利用它来降低时间复杂度呢?

  1. 使用两个栈,一个栈(inStack\textit{inStack})用于元素进栈,一个栈(outStack\textit{outStack})用于元素出栈;

  2. pop()\texttt{pop()} 或者 peek()\texttt{peek()} 的时候:

    • 如果 inStack\textit{inStack} 里面有元素,直接从 outStack\textit{outStack} 里弹出或者 peek\texttt{peek} 元素;

    • 如果 outStack\textit{outStack} 里面没有元素,一次性将 inStack\textit{inStack} 里面的所有元素倒入 outStack\textit{outStack}

注意:
一定要保证 outStack\textit{outStack} 为空的时候,才能把元素从 inStack\textit{inStack} 里拿到 outStack\textit{outStack} 中。

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
36
37
38
39
40
41
class MyQueue {
Stack<Integer> inStack;
Stack<Integer> outStack;

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

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

public int pop() {
if (!outStack.empty()) {
return outStack.pop();
}

while (!inStack.empty()) {
outStack.push(inStack.pop());
}

return outStack.pop();
}

public int peek() {
if (!outStack.empty()) {
return outStack.peek();
}

while (!inStack.empty()) {
outStack.push(inStack.pop());
}

return outStack.peek();
}

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

复杂度分析

  • 时间复杂度:均摊操作均为 O(1)O(1),其中 nn 是栈内的元素个数。

    • push()\texttt{push()}O(1)O(1)
    • pop()\texttt{pop()}O(1)O(1)
    • peek()\texttt{peek()}O(1)O(1)
    • empty()\texttt{empty()}O(1)O(1)
  • 空间复杂度:O(n)O(n),其中 nn 是栈内的元素个数。需要使用两个队列存储队列内的元素。


All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗