By Long Luo
Leetcode 225. 用队列实现栈 ,难度为Easy:
- 用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的,返回 true;否则,返回 false。
注意:
- 你只能使用队列的基本操作 —— 也就是
push to back
、peek/pop from front
、size
和is 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
- 最多调用 100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
进阶:你能否仅用一个队列来实现栈。
这道题考察的是栈和队列两种数据结构知识。
栈是一种**后进先出(LIFO)**的数据结构,元素从顶端入栈,然后从顶端出栈。
队列是一种**先进先出(FIFO)**的数据结构,元素从后端入队,然后从前端出队。
2个队列
题目的要求是用 2 个队列实现一个栈,但是把一个队列中的数据导入另一个队列中,数据的顺序并没有发生改变,并不会变成先进后出的顺序。
那该如何做呢?
用 2 个队列 queue1 和 queue2:
- 有 1 个元素 A,那非常简单,直接压入弹出即可;
- 有 2 个元素 A,B,queue1 压入 A,queue2 压入 B,然后将 queue1 中元素压入 queue2,这样 queue2 中的元素顺序就是正确的;
- 因为 queue1 是主队列,所以还需要将 queue2 中元素重新导入到 queue1。
代码如下所示:
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 这里实际上只需要交换 queue1 和 queue2 即可,优化代码如下:
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(); } }
|
复杂度分析
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(); } }
|
复杂度分析
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. 😉😃💗