双队列实现
解题思路
一个队列为主队列 mainQueue ，一个为辅助队列 subQueue；
当入栈操作时，直接将值 push 到 mainQueue 里面；
当出栈操作时，操作 mainQueue：
- 如果 mainQueue 为空，则交换 mainQueue 和 subQueue 的值，然后把 mainQueue 里面的值的个数只留下一个，其他全部 shift 出队，然后 push 到 subQueue 里面；
- 如果 mainQueue 不为空，则把 mainQueue 里面的值的个数只留下一个，其他全部 shift 出队，然后 push 到 subQueue 里面；
图解
复杂度
-
时间复杂度：入栈操作
O(n)，其余操作都是O(1)； -
空间复杂度：
O(n)，其中 n 是栈内的元素个数，需要使用两个队列存储栈内的元素；
代码实现
var MyStack = function () {
this.mainQueue = []; // 主队列
this.subQueue = []; // 辅助队列
};
MyStack.prototype.push = function (x) {
this.mainQueue.push(x);
};
MyStack.prototype.pop = function () {
// 减少两个队列交换的次数， 只有当 主队列 为空时，交换两个队列
if (!this.mainQueue.length) [this.mainQueue, this.subQueue] = [this.subQueue, this.mainQueue];
//当 主队列 的元素数量 >1 的时候不断将元素 push 进备份队列
while (this.mainQueue.length > 1) this.subQueue.push(this.mainQueue.shift());
//最后将 主队列 最后一个元素出队
return this.mainQueue.shift();
};
MyStack.prototype.top = function () {
const x = this.pop();
this.mainQueue.push(x);
return x;
};
MyStack.prototype.empty = function () {
return !this.mainQueue.length && !this.subQueue.length;
};
单队列实现
解题思路
入栈操作时，首先获得入栈前的元素个数 len ，然后将新元素 push 入队；
再将队列中的前 len 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列尾部；
此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底；
图解
复杂度
-
时间复杂度：入栈操作
O(n)，其余操作都是O(1)； -
空间复杂度：
O(n)，其中 n 是栈内的元素个数，需要使用两个队列存储栈内的元素；
代码实现
var MyStack = function () {
this.queue = [];
};
MyStack.prototype.push = function (x) {
let len = this.queue.length;
this.queue.push(x);
while (len--) this.queue.push(this.queue.shift());
};
MyStack.prototype.pop = function () {
return this.queue.shift();
};
MyStack.prototype.top = function () {
let top = this.pop();
this.push(top);
return top;
};
MyStack.prototype.empty = function () {
return this.queue.length === 0
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 109. 有序链表转换二叉搜索树
上一篇
评论
