#2133. 用栈实现队列
用栈实现队列
问题描述
请你仅使用两个栈实现一个先入先出队列。队列应当支持一般队列支持的所有操作:
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),即使其中一个操作可能会花费较长时间。