232. 用栈实现队列
232. 用栈实现队列
题目
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push
, peek
, pop
, and empty
).
Implement the MyQueue
class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes the element from the front of the queue and returns it.int peek()
Returns the element at the front of the queue.boolean empty()
Returnstrue
if the queue is empty,false
otherwise.
Notes:
- You must use only standard operations of a stack, which means only
push to top
,peek/pop from top
,size
, andis empty
operations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
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
Constraints:
1 <= x <= 9
- At most
100
calls will be made topush
,pop
,peek
, andempty
. - All the calls to
pop
andpeek
are valid.
Follow-up: Can you implement the queue such that each operation is amortized O(1)
time complexity? In other words, performing n
operations will take overall O(n)
time even if one of those operations may take longer.
题目大意
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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
(双端队列)来模拟一个栈,只要是标准的栈操作即可。
解题思路
使用两个栈,将一个栈当作输入栈,用于压入 push
传入的数据;另一个栈当作输出栈,用于 pop
和 peek
操作。
每次 pop
或 peek
时,若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
代码
class MyQueue {
constructor() {
this.pushList = [];
this.popList = [];
}
// @param {number} x
// @return {void}
push(x) {
this.pushList.push(x);
}
// @return {number}
pop() {
if (this.popList.length === 0) {
while (this.pushList.length > 0) {
this.popList.push(this.pushList.pop());
}
}
return this.popList.pop();
}
// @return {number}
peek() {
if (this.popList.length === 0) {
while (this.pushList.length > 0) {
this.popList.push(this.pushList.pop());
}
}
return this.popList[this.popList.length - 1];
}
// @return {boolean}
empty() {
let len = this.pushList.length + this.popList.length;
return len === 0;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = new MyQueue()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
225 | 用队列实现栈 | [✓] | 栈 设计 队列 |