友情支持
如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜
有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi 。因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出(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(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
输入: ["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
都保证栈不为空
进阶:你能否仅用一个队列来实现栈。
思路分析
就是用两个队列来回倒腾。添加元素的时候,哪个空就放那个队列中,把另外一个队列里的值都倒腾过来。
使用一个队列来求解,则在添加新记录之前,把队列长度记录下来,添加完新元素,再出队入队原来队列长度次数。
-
一刷
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-02 16:59:24
*/
class MyStack {
// 一个队列解法
private Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
int size = queue.size();
queue.offer(x);
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
// // 两个队列的解法
// private Queue<Integer> q1;
// private Queue<Integer> q2;
//
// public MyStack() {
// q1 = new LinkedList<>();
// q2 = new LinkedList<>();
// }
//
// public void push(int x) {
// if (q1.isEmpty()) {
// q1.offer(x);
// while (!q2.isEmpty()) {
// q1.offer(q2.poll());
// }
// } else {
// q2.offer(x);
// while (!q1.isEmpty()) {
// q2.offer(q1.poll());
// }
// }
// }
//
// public int pop() {
// if (q1.isEmpty()) {
// return q2.poll();
// } else {
// return q1.poll();
// }
// }
//
// public int top() {
// if (q1.isEmpty()) {
// return q2.peek();
// } else {
// return q1.peek();
// }
// }
//
// public boolean empty() {
// if (q1.isEmpty()) {
// return q2.isEmpty();
// } else {
// return q1.isEmpty();
// }
// }
}