[Leetcode][225. 用队列实现栈] 如何改变队列元素顺序?

By Long Luo

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


  1. 用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push\texttt{push}top\texttt{top}pop\texttt{pop}empty\texttt{empty})。

实现MyStack\texttt{MyStack}类:

  • void push(int x)\texttt{void push(int x)}将元素x\textit{x}压入栈顶。
  • int pop()\texttt{int pop()}移除并返回栈顶元素。
  • int top()\texttt{int top()}返回栈顶元素。
  • boolean empty()\texttt{boolean empty()}如果栈是空的,返回true\textit{true};否则,返回false\textit{false}

注意:

  • 你只能使用队列的基本操作 —— 也就是push to backpeek/pop from frontsizeis empty这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用list(列表)或者deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

示例:

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

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示:

  • 1 <= x <= 9
  • 最多调用100100push\texttt{push}pop\texttt{pop}top\texttt{top}empty\texttt{empty}
  • 每次调用pop\texttt{pop}top\texttt{top}都保证栈不为空

进阶:你能否仅用一个队列来实现栈。


这道题考察的是队列两种数据结构知识。

栈是一种**后进先出(LIFO)**的数据结构,元素从顶端入栈,然后从顶端出栈。

队列是一种**先进先出(FIFO)**的数据结构,元素从后端入队,然后从前端出队。

2个队列

题目的要求是用22个队列实现一个栈,但是把一个队列中的数据导入另一个队列中,数据的顺序并没有发生改变,并不会变成先进后出的顺序。

那该如何做呢?

22个队列queue1\textit{queue}_1queue2\textit{queue}_2

  1. 11个元素A\textit{A},那非常简单,直接压入弹出即可;
  2. 22个元素A\textit{A}B\textit{B}queue1\textit{queue}_1压入AAqueue2\textit{queue}_2压入BB,然后将queue1\textit{queue}_1中元素压入queue2\textit{queue}_2,这样queue2\textit{queue}_2中的元素顺序就是正确的;
  3. 因为queue1\textit{queue}_1是主队列,所以还需要将queue2\textit{queue}_2中元素重新导入到queue1\textit{queue}_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
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;

public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}

public void push(int x) {
while (!queue1.isEmpty()) {
queue2.add(queue1.poll());
}

queue1.add(x);
while (!queue2.isEmpty()) {
queue1.add(queue2.poll());
}
}

public int pop() {
return queue1.poll();
}

public int top() {
return queue1.peek();
}

public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}

上述代码可以进行优化,push\texttt{push}这里实际上只需要交换queue1\textit{queue}_1queue2\textit{queue}_2即可,优化代码如下:

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
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;

public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}

public void push(int x) {
queue2.offer(x);

while (!queue1.isEmpty()) {
queue2.add(queue1.poll());
}

Queue<Integer> temp = queue2;
queue2 = queue1;
queue1 = temp;
}

public int pop() {
return queue1.poll();
}

public int top() {
return queue1.peek();
}

public boolean empty() {
return queue1.isEmpty();
}
}

复杂度分析

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

    • push()\texttt{push()}入栈操作需要将queue1\textit{queue}_1中的nn个元素出队,并入队n+1n+1个元素到queue2\textit{queue}_2,共有2n+12n+1次操作,每次出队和入队操作的时间复杂度都是O(1)O(1),因此入栈操作的时间复杂度是O(n)O(n)
    • pop()\texttt{pop()}出栈操作对应将queue1\textit{queue}_1的前端元素出队,时间复杂度是O(1)O(1)
    • top()\texttt{top()}获得栈顶元素操作对应获得queue1\textit{queue}_1的前端元素,时间复杂度是 O(1) 。
    • empty()\texttt{empty()}判断栈是否为空操作只需要判断queue1\textit{queue}_1是否为空,时间复杂度是 O(1) 。
  • 空间复杂度:O(n)O(n),其中nn是栈内的元素个数。需要使用两个队列存储栈内的元素。

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
class MyStack {
Queue<Integer> queue;

public MyStack() {
queue = new LinkedList<>();
}

public void push(int x) {
int len = queue.size();
queue.offer(x);
for (int i = 0; i < len; i++) {
queue.offer(queue.poll());
}
}

public int pop() {
return queue.poll();
}

public int top() {
return queue.peek();
}

public boolean empty() {
return queue.isEmpty();
}
}

复杂度分析

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

    • push()\texttt{push()}入栈操作需要将队列中的nn个元素出队,并入队n+1n+1个元素到队列,共有2n+12n+1次操作,每次出队和入队操作的时间复杂度都是O(1)O(1),因此入栈操作的时间复杂度是O(n)O(n)
    • pop()\texttt{pop()}出栈操作对应将队列的前端元素出队,时间复杂度是O(1)O(1)
    • top()\texttt{top()}获得栈顶元素操作对应获得队列的前端元素,时间复杂度是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. 😉😃💗