问题描述

请你仅使用两个栈实现一个先入先出队列。队列应当支持一般队列支持的所有操作：

• push：将元素x推到队列的末尾。
• pop：从队列的开头移除并返回元素。
• peek：返回队列开头的元素。
• empty：如果队列为空，返回true；否则返回false。

说明

• 只能使用标准的栈操作，即push to top，peek/pop from top，size和is empty。
• 语言内置的队列和双端队列（deque）不可使用。
• 只能使用两个栈来实现上述操作。

格式

输入

• 一系列操作序列和对应的参数。

输出

• 每个操作的返回值（对于无返回值的操作，如push，返回null）。

样例

样例1

输入

6
MyQueue push push peek pop empty
0 1 2 0 0 0

输出

null null null 1 1 false

解释

MyQueue myQueue = new MyQueue(); myQueue.push(1); // 队列是 [1] myQueue.push(2); // 队列是 [1, 2] myQueue.peek(); // 返回 1 myQueue.pop(); // 返回 1，队列变成 [2] myQueue.empty(); // 返回 false

提示

• 1 <= x <= 9
• 最多调用100次push、pop、peek和empty。
• 所有操作都是有效的，即不会调用空队列的pop或peek。

进阶

• 你能否实现**每个操作的平均时间复杂度为O(1)**的队列？
• 换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能会花费较长时间。