写点什么

LeetCode 题解:225. 用队列实现栈,两个队列,压入 -O(1), 弹出 -O(n),JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 09 月 08 日
LeetCode题解:225. 用队列实现栈,两个队列,压入 -O(1), 弹出 -O(n),JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/implement-stack-using-queues/



解题思路:



参考了官方题解的方法一 (两个队列,压入 -O(1)O(1), 弹出 -O(n)O(n))。



入栈时直接将元素存入队列q1,出栈时将q1的非队尾元素存入队列q2,q1中剩下的元素即为栈顶。



  1. 使用两个对列,q1用来存储栈,q2保持为空。

  2. 每次入栈都将元素存入q1,此时栈顶元素在q1队尾,无法被查看,需要用一个变量缓存栈顶的值,供top方法获取。

  3. 出栈时将q1的非队尾元素存入队列q2,q1中剩下的元素即为栈顶,将其出队即为出栈操作。



/**
* Initialize your data structure here.
*/
var MyStack = function () {
this.q1 = []; // 保存栈
this.q2 = []; // 用于pop时缓存队列中除栈顶外的其他元素
this.tail = null; // 保存栈顶元素
};
/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function (x) {
this.q1.push(x); // 入栈时将元素直接存入队列
this.tail = x; // 由于存入队列的元素无法被作为栈顶查看,因此需要用变量存储此时的栈顶元素
};
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
// 如果队列长度<=1,则出栈之后栈顶为空
if (this.q1.length <= 1) {
this.tail = null;
}
// 将队列元素除队尾外都移动到q2,q1中剩下的1个元素即为栈顶元素
while (this.q1.length > 1) {
this.tail = this.q1.shift();
this.q2.push(this.tail);
}
// 队列中只剩1个元素,即为栈顶
const top = this.q1.shift();
// 将q1和q2对调,保证每次操作的队列都为q1。
const temp = this.q1;
this.q1 = this.q2;
this.q2 = temp;
// 返回出栈的元素
return top;
};
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function () {
return this.tail;
};
/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function () {
return !this.q1.length;
};



发布于: 2020 年 09 月 08 日阅读数: 40
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:225. 用队列实现栈,两个队列,压入 -O(1), 弹出 -O(n),JavaScript,详细注释