Leetcode 232 用栈实现队列
文章目录
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空,返回true;否则,返回false
解题思路
- 栈后进先出,队列先进先出;
- 双栈可以实现序列倒置:添加元素的时候直接
push到stack1。当需要删除队首元素时,仅仅需要出栈stack2即可;如果stack2为空,则循环出栈stack1并将出栈元素进栈stack2,循环结束后元素已经倒置,再出栈stack2即可;
代码实现
class MyQueue {
private stack1: number[];
private stack2: number[];
constructor() {
this.stack1 = [];
this.stack2 = [];
}
// 将元素加入队尾
push(x: number): void {
this.stack1.push(x);
}
// 从队列开头移除元素
pop(): number {
if (this.stack2.length) {
return this.stack2.pop();
}
if (!this.stack1.length) return -1;
while (this.stack1.length) {
this.stack2.push(this.stack1.pop());
}
return this.stack2.pop();
}
// 返回队列开头的元素
peek(): number {
if (this.stack2.length) {
return this.stack2[this.stack2.length - 1];
}
if (!this.stack1.length) return -1;
while (this.stack1.length) {
this.stack2.push(this.stack1.pop());
}
return this.stack2[this.stack2.length - 1];
}
// 返回队列是否为空
empty(): boolean {
return (this.stack2.length === 0 && this.stack1.length === 0);
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论