这是 LeetCode 上的「232. 用栈实现队列」,难度为 Easy。
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
说明:
进阶:
示例:
输入:
["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
提示:
无论「用栈实现队列」还是「用队列实现栈」,思路都是类似的。
都可以通过使用两个栈/队列来解决。
我们创建两个栈,分别为 out
和 in
,用作处理「输出」和「输入」操作。
其实就是两个栈来回「倒腾」。
而对于「何时倒腾」决定了是 「O(n) 解法」 还是 「均摊 O(1) 解法」。
我们创建两个栈,分别为 out
和 in
:
in
用作处理输入操作 push()
,使用 in
时需确保 out
为空」out
用作处理输出操作 pop()
和 peek()
,使用 out
时需确保 in
为空」class MyQueue {
Deque<Integer> out, in;
public MyQueue() {
in = new ArrayDeque<>();
out = new ArrayDeque<>();
}
public void push(int x) {
while (!out.isEmpty()) in.addLast(out.pollLast());
in.addLast(x);
}
public int pop() {
while (!in.isEmpty()) out.addLast(in.pollLast());
return out.pollLast();
}
public int peek() {
while (!in.isEmpty()) out.addLast(in.pollLast());
return out.peekLast();
}
public boolean empty() {
return out.isEmpty() && in.isEmpty();
}
}
事实上,我们不需要在每次的「入栈」和「出栈」操作中都进行「倒腾」。
「我们只需要保证,输入的元素总是跟在前面的输入元素的后面,而输出元素总是最早输入的那个元素即可。」
可以通过调整「倒腾」的时机来确保满足上述要求,但又不需要发生在每一次操作中:
class MyQueue {
Deque<Integer> out, in;
public MyQueue() {
in = new ArrayDeque<>();
out = new ArrayDeque<>();
}
public void push(int x) {
in.addLast(x);
}
public int pop() {
if (out.isEmpty()) {
while (!in.isEmpty()) out.addLast(in.pollLast());
}
return out.pollLast();
}
public int peek() {
if (out.isEmpty()) {
while (!in.isEmpty()) out.addLast(in.pollLast());
}
return out.peekLast();
}
public boolean empty() {
return out.isEmpty() && in.isEmpty();
}
}
pop()
和 peek()
操作都是均摊我们先用另外一个例子来理解「均摊复杂度」,大家都知道「哈希表」底层是通过数组实现的。
正常情况下,计算元素在哈希桶的位置,然后放入哈希桶,复杂度为
,假定是通过简单的“拉链法”搭配「头插法」方式来解决哈希冲突。
但当某次元素插入后,「哈希表」达到扩容阈值,则需要对底层所使用的数组进行扩容,这个复杂度是
显然「扩容」操作不会发生在每一次的元素插入中,因此扩容的
都会伴随着 n
次的
,也就是
的复杂度会被均摊到每一次插入当中,因此哈希表插入仍然是
的。
「同理,我们的「倒腾」不是发生在每一次的「输出操作」中,而是集中发生在一次「输出栈为空」的时候,因此 pop
和 peek
都是均摊复杂度为
的操作。」
由于本题的调用次数只有 100 次,所以铁定是一个人均 100% 的算法(0 ms)? ?
我们需要对操作进行复杂度分析进行判断,而不是看时间来判断自己是不是均摊 O(1) 哦 ~
这是我们「刷穿 LeetCode」系列文章的第 No.232
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。