外观
使用两个栈实现队列
⭐ 题目日期：
腾讯 - 2024/8/19
🌳 题目描述：
使用两个栈实现队列，支持 poll，offer，peek 操作； 队列：按照先进先出的原理运作，在队尾加入元素，在队头弹出元素
示例 1：
输入：["MyQueue", "offer", "offer", "offer", "offer","peek", "poll","peek"]
[[], [1], [3], [2], [4], [], [], []]
输出：[null, null, null, null, null, 1, 1, 3]
🕵🏽 面试评估：
这道题考察候选人对队列先进先出特性的理解，能否结合栈的特性模拟队列，且能够正确处理边界条件（如空队列时的返回值）。
🧗难度系数：
⭐️ ⭐️
📝思路分析：
队列的特性是先进先出，而栈的特性是先进后出，顺序完全相反。那么我们可以用另外一个栈去存储栈中的元素，顺序刚好调过来，满足先进先出。
以顺序存储 1， 2， 3， 4为例
栈 A：底部 || 1 2 3 4
栈 B：底部 ||
此时，如果从栈 A 中取出元素，顺序就乱了，不满足先进先出的队列特性。因此，我们需要借助栈 B 来压入 A 中的元素实现顺序翻转。
栈 A：底部 ||
栈 B：底部 || 4 3 2 1
此时如果从B中取出元素，就符合队列的特性，先进先出。
如果此时有元素 5 来存入这个队列系统，5 应该压入到 A，(如果压入到 B，顺序会乱)，得到：
栈 A：底部 || 5
栈 B：底部 || 4 3 2 1
此时 5 的出队顺序必须在 1 2 3 4 之后，所以在 1 2 3 4 取出之前，也就是 B 空栈之前，5 不能加入到 B。
总结以上的规律，我们用一个栈 A 来存储入队元素，另外一个栈 B 来负责调配出队元素。调配的原则为：当 B 中无元素时，将 A 中所有元素压入到 B，B 中有元素时，取出/查看 B 中的元素，这样就实现了一个队列的先进先出的功能。
我们用 inStack 来用于存储入队的元素，outStack 用于弹出元素，且按照先进元素在最顶部的原则。
基础操作图解如下
当执行 push(x) ,首先更新 top 栈顶指针的值，随后将 x 加入数组中，同时判断当前的数是否大于等于 MaxStack 数组中最顶端的数，或者是当前的数是否为第一个数，如果是，便将其压入 MaxStack 数组中，确保 MaxStack 数组总是包含当前 stack 数组中的最大值。
当执行 pop()，将栈顶指针的值 -1即可
当执行 top()，返回当前数组栈顶指针所指的数值
当执行 max()，返回 MaxStack 数组栈顶指针所指的数值
💻代码：
Java
public class MyQueue {
private Stack<Integer> inStack; // 存储队列入队中的元素
private Stack<Integer> outStack; // 弹出元素
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void offer(int x) {
inStack.push(x);
}
public int peek() {
if (outStack.isEmpty()) {
loadItems(inStack, outStack);
}
return outStack.isEmpty() ? -1 : outStack.peek();
}
public int poll() {
if (outStack.isEmpty()) {
loadItems(inStack, outStack);
}
return outStack.isEmpty()? -1 : outStack.pop();
}
public boolean isEmpty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void loadItems(Stack<Integer> source, Stack<Integer> destination) {
while (!source.isEmpty()) {
destination.push(source.pop());
}
}
}Python
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def offer(self, x: int) -> None:
self.in_stack.append(x)
def peek(self) -> int:
if not self.out_stack:
self.load_items(self.in_stack, self.out_stack)
return self.out_stack[-1] if self.out_stack else -1
def poll(self) -> int:
if not self.out_stack:
self.load_items(self.in_stack, self.out_stack)
return self.out_stack.pop() if self.out_stack else -1
def is_empty(self) -> bool:
return not self.in_stack and not self.out_stack
def load_items(self, source: list, destination: list) -> None:
while source:
destination.append(source.pop())🚵🏻复杂度分析：
时间复杂度：offer(x) 是 O(1)，常数级操作，直接将元素加入 instack；poll() 平均时间复杂度为 O(1)，当 outStack 为空时，需要将 inStack 中的元素压入 outStack，假定，此时 inStack 中有 n 个元素，则需要 O(n) 的时间将所有元素压入 outStack, 而后面的 n 次 poll() 操作我们都可以用 O(1) 的时间从 outStack 中取元素，所以这 n 次 poll 操作，每次的平均时间复杂度为 O(n) / n = O(1)。peek() 平均时间复杂度也为 O(1)，原理跟 poll() 相同。
空间复杂度：O(n)，使用两个栈来存储数据，其中 n 为“队列”中存储元素的个数。
🔬在线评测(Online Judge):
题目相似：题目链接