LeetCode题解:232. 用栈实现队列,使用两个栈 入队 – O(1), 出队 – O(n),JavaScript,详细注释

微信扫一扫,分享到朋友圈

LeetCode题解:232. 用栈实现队列,使用两个栈 入队 – O(1), 出队 – O(n),JavaScript,详细注释

LeetCode题解:232. 用栈实现队列,使用两个栈 入队 – O(1), 出队 – O(n),JavaScript,详细注释

原题链接: leetcode-cn.com/problems/im…

解题思路:

  1. 所有元素都存在s1,同时缓存第一个入队元素为队首。
  2. 当出队时,先将除队首外的元素都缓存到s2,再将s1仅剩的一个元素pop。
  3. pop完成之后,再将s2缓存的元素依次返回s1。
/**
* Initialize your data structure here.
*/
var MyQueue = function () {
this.s1 = []; // 储存队列
this.s2 = []; // pop时临时存储数据
this.top = null; // 储存队首
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
// 将第一个入队元素存储为队首
if (!this.s1.length) {
this.top = x;
}
// 所有元素正常入栈
this.s1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
// s1长度为1时,栈会被清空,因此清空队首的值,但此处用例没有校验
if (this.s1.length <= 1) {
this.top = null;
}
// 将s1元素除队首全部都转移到s2
while (this.s1.length > 1) {
this.top = this.s1.pop();
this.s2.push(this.top);
}
// 将队首元素出栈并缓存
const pop = this.s1.pop();
// 让s2元素全部返回s1,保持元素的排列顺序
while (this.s2.length) {
this.s1.push(this.s2.pop());
}
return pop;
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function () {
return this.top;
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
return !this.s1.length;
};
复制代码

Spring IoC 到底是什么

上一篇

华为鸿蒙OS官网正式上线:提供源码下载 首批支持128KB~128MB设备运行

下一篇

你也可能喜欢

LeetCode题解:232. 用栈实现队列,使用两个栈 入队 – O(1), 出队 – O(n),JavaScript,详细注释

长按储存图像,分享给朋友