友情支持
如果您觉得这个笔记对您有所帮助，看在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();
// }
// }
}