目标
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["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说明：
- 1 <= x <= 9
- 最多调用 100 次 push、pop、peek 和 empty
- 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
思路
这道题是让我们仅使用push压入栈顶、peek获取栈顶元素、pop弹栈等API实现先进先出队列。
关键是要想明白一点，入栈与出栈操作的是不同的栈，出栈s2中的元素是从入栈s1中获取的，并且，只能在s2为空的时候，将s1中的元素一个个弹栈再入s2，这样才能保证顺序反转。
代码
import java.util.ArrayDeque;
import java.util.Deque;
/**
* @date 2024-03-04 0:42
*/
public class MyQueue {
private final Deque<Integer> s1;
private final Deque<Integer> s2;
public MyQueue() {
s1 = new ArrayDeque<>();
s2 = new ArrayDeque<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
if (s2.isEmpty()) {
throw new RuntimeException();
}
return s2.peek();
}
public boolean empty() {
return s2.isEmpty() && s1.isEmpty();
}
}Stack注释中有这么一段话，告诉我们应该优先使用Deque接口及其实现。
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.
For example: Deque<Integer> stack = new ArrayDeque<Integer>();
在Java中，Stack类是基于Vector实现的，而Vector是一个线程安全的、可动态增长的数组。虽然Stack也是数组实现的，但由于Vector的一些内部机制（例如，每次增长时都会分配更大的数组，并将旧数组的内容复制到新数组中），它可能在某些操作上不如ArrayDeque高效。
相比之下，ArrayDeque是基于循环数组实现的，它避免了不必要的内存分配和复制操作。循环数组意味着当数组的一端达到容量限制时，元素会从另一端开始填充，从而充分利用了数组空间。这种实现方式通常比Vector或Stack更高效。
因此，即使Stack也是数组实现的，但由于Deque（如ArrayDeque）使用了不同的内部机制和优化，它在某些情况下可能会提供更好的性能。
另外，值得注意的是，在Java中，Stack类已经被标记为遗留（legacy），不建议在新的代码中使用。相反，应该使用Deque接口及其实现，如ArrayDeque，因为它们提供了更完整、更一致的操作集合，并且通常具有更好的性能。
性能
时间复杂度：push（数组赋值），empty为O(1)，pop与peek虽然涉及到移动数据，但只有在出栈为空的时候才执行，均摊后为O(1)。
空间复杂度为O(n)。