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

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

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



解题思路:



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



入栈时将元素加入队列的队尾,之后将其之前元素依次出队,同时存入队尾。这样队列就被翻转了一次,出队操作就变成了出栈操作。



/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function (x) {
// 入栈的元素直接加入队列
this.q.push(x);
// 将队尾的元素依次出队,同时入队,如此操作this.q.length - 1次。
// 操作之后队列就按照出栈顺序进行排列,出队操作即为出栈。
for (let i = 0; i < this.q.length - 1; i++) {
this.q.push(this.q.shift());
}
};
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function () {
return this.q.shift();
};
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function () {
return this.q[0];
};
/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function () {
return !this.q.length;
};



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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

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