【设计数据结构】面试官：用队列实现栈 ...
题目描述
这是 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 这些操作。
示例：
输入：
["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 都保证栈不为空
进阶：你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。
基本思路
无论「用栈实现队列」还是「用队列实现栈」，思路都是类似的。
一个通用的思路是：通过使用两个栈/队列来解决问题。
「双队列」解法
我们可以使用「两个队列」来实现栈：
- 一个
队列，用于存储元素。
- 一个
队列，帮助实现 LIFO 的输出。
通常「倒腾」两个队列的操作可以放在「输入」的
里面，也可以放在「输出」的
和
中。
这取决于该数据结构是「偏写入」还是「偏读取」。
由于「倒腾」的操作是
的。
如果我们是一个「偏写入」的数据结构，那么应该确保
操作是
的，应该把「倒腾」的操作放在「输出」的
和
中；
同理，如果我们是一个「偏读取」的数据结构，那么应该确保
和
操作是
的，应该把「倒腾」的操作放在「输入」的
中。
三叶提供的是「偏写入」的实现。
代码：
class MyStack {
Deque<Integer> data = new ArrayDeque<>();
Deque<Integer> help = new ArrayDeque<>();
public void push(int x) {
data.addLast(x);
}
public int pop() {
while (data.size() > 1) {
help.addLast(data.pollFirst());
}
int u = data.pollFirst();
swap();
return u;
}
public int top() {
while (data.size() > 1) {
help.addLast(data.pollFirst());
}
int u = data.peekFirst();
help.addLast(data.pollFirst());
swap();
return u;
}
public boolean empty() {
return data.isEmpty() && help.isEmpty();
}
void swap() {
Deque<Integer> tmp = data;
data = help;
help = tmp;
}
}
- 时间复杂度：
和
方法的复杂度为
；而
和
的复杂度为
。
- 空间复杂度：
「单队列」解法
由于
队列的作用只是帮助我们存储「输出对象」前面的值，而无论是「队列」还是「栈」都是从尾部进行存储。
因此我们可以直接使用一个栈来解决。
代码：
class MyStack {
Deque<Integer> data = new ArrayDeque<>();
public void push(int x) {
data.addLast(x);
}
public int pop() {
int size = data.size();
while (size-- > 1) {
data.addLast(data.pollFirst());
}
return data.pollFirst();
}
public int top() {
int size = data.size();
while (size-- > 1) {
data.addLast(data.pollFirst());
}
int u = data.peekFirst();
data.addLast(data.pollFirst());
return u;
}
public boolean empty() {
return data.isEmpty();
}
}
- 时间复杂度：
和
方法的复杂度为
；而
和
的复杂度为
。
- 空间复杂度：
关于「均摊复杂度」的说明
我们用另外一个例子来理解「均摊复杂度」，大家都知道「哈希表」底层是通过数组实现的。
正常情况下，计算元素在哈希桶的位置，然后放入哈希桶，复杂度为
，假定是通过简单的“拉链法”搭配「头插法」方式来解决哈希冲突。
但当某次元素插入后，「哈希表」达到扩容阈值，则需要对底层所使用的数组进行扩容，这个复杂度是
显然「扩容」操作不会发生在每一次的元素插入中，因此扩容的
都会伴随着 n 次的
，也就是
的复杂度会被均摊到每一次插入当中，因此哈希表插入仍然是
的。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.225 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
