深入探讨JavaScript中的队列，结合leetcode全面解读
前言
队列作为一种基本的数据结构，为解决许多实际问题提供了有效的组织和处理方式，对于提高系统的稳定性、可靠性和效率具有重要作用，所以理解队列是很重要的。
本文深入探讨JavaScript中的队列这种数据结构,结合leetcode题目讲解
题目直达：
什么是队列
队列是一种特殊的线性表数据结构，它遵循“先进先出”（First-In-First-Out，FIFO）的原则
即先进入队列的元素先出队列,进去是abc的顺序，出来也是abc的顺序
JavaScript实现队列
JavaScript 中，没有专门的一个关键词来直接表示队列。
可以使用数组的方法来模拟队列的行为。
常见的实现方式
-
数组的
push()方法在队尾添加元素，使用shift()方法在队首移除元素 -
数组的
pop()在队尾删除元素、unshift()方法在队添加元素
既然我们明白了这个点，我们就知道了，如果要从队列里面拿数据就一定会造成队列长度发生变化
所以队列的遍历不能用for循环，队列的长度是动态变化的
分析一下下面的代码
const queue = []
queue.push('a')
queue.push('b')
queue.push('c')
for (let i = 0; i < queue.length; i++) {
const top = queue.shift()
console.log(top);
}
这段代码的执行结果为
这并不是我们想要的结果，这就是因为在循环中使用 shift 方法会导致每次循环时队列的长度发生变化，从而导致循环次数不正确
我们可以使用两种方式去遍历
- 使用一个临时变量来保存队列的初始长度，然后基于这个长度进行循环操作
const queue = [];
queue.push('a');
queue.push('b');
queue.push('c');
const length = queue.length;
for (let i = 0; i < length; i++) {
const top = queue.shift();
console.log(top);
}
- 使用while循环去遍历，只要队列的长度大于 0，就会不断从队列中取出元素并打印
const queue = [];
queue.push('a');
queue.push('b');
queue.push('c');
while (queue.length > 0) {
const top = queue.shift();
console.log(top);
}
232. 用栈实现队列 - 力扣（LeetCode）
题目直达232. 用栈实现队列 - 力扣（LeetCode）
接下来我们用232题来讲解一下栈数据结构，首先分析题目
题目要求我们去打造一个栈结构，并且实现一系列的方法
既然是使用两个栈去实现，首先我们肯定是需要去准备两个栈
var MyQueue = function () {
this.stack1 = []
this.stack2 = []
};
接下来我们考虑如何通过这两个栈去实现队列效果呢？
从这个动画我们 可以看到，我们首先去存入到stack1，然后再存入stack2，这样就实现了翻转，就能够实现先进先出的效果了
接下来我们就编写代码
var MyQueue = function () {
this.stack1 = []
this.stack2 = []
};
MyQueue.prototype.push = function (x) {
this.stack1.push(x)
};
MyQueue.prototype.pop = function () {
if (this.stack2.length === 0) {
while (this.stack1.length) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2.pop()
};
MyQueue.prototype.peek = function () {
if (this.stack2.length === 0) {
while (this.stack1.length) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2[this.stack2.length - 1]
};
MyQueue.prototype.empty = function () {
return this.stack1.length === 0 && this.stack2.length === 0
};
-
MyQueue类的构造函数：- 初始化了两个空数组
stack1和stack2，用于模拟队列的操作。
- 初始化了两个空数组
-
push方法：- 接收一个参数
x，将其直接压入stack1。这相当于向队列的尾部添加元素。
- 接收一个参数
-
pop方法：- 首先检查
stack2是否为空。 - 如果为空，通过一个
while循环，将stack1中的元素逐个弹出并压入stack2。这样就实现了将stack1中的元素顺序反转，从而模拟出队列的出队操作。 - 最后，从
stack2中弹出并返回顶部元素。
- 首先检查
-
peek方法：- 与
pop方法类似，先检查stack2是否为空，如果为空则进行元素转移。 - 然后返回
stack2的最后一个元素，但不将其弹出，实现了查看队列头部元素的功能。
- 与
-
empty方法：- 检查
stack1和stack2的长度是否都为 0，如果都是 0 则表示队列为空，返回true；否则返回false。
- 检查
239. 滑动窗口最大值 - 力扣（LeetCode）
题目直达239. 滑动窗口最大值 - 力扣（LeetCode）
var maxSlidingWindow = function (nums, k) {
var a = 0;
var b = k - 1;
var arr = []
while (b < nums.length) {
var max = -Infinity
for (var i = a; i <= b; i++) {
if (max < nums[i])
max = nums[i];
}
arr.push(max)
a++
b++
}
return arr;
};
var maxSlidingWindow = function (nums, k) {
const len = nums.length
const res = []
const queue = []//维护一个递减队列
for (let i = 0; i < length; i++) {
while (queue.length && nums[i] > queue[queue.length - 1]) {
queue.pop()
}
queue.push(nums[i])
while (queue.length && queue[0] <= i - k) {
queue.shift()
}
if (i >= k - 1) {
arr.push(nums[queue[0]])
}
}
return res
}
第一段代码：
- 它使用了两个指针
a和b来表示滑动窗口的起始和结束位置。 - 在每次滑动窗口中，通过一个内层的循环遍历窗口内的所有元素来找到最大值，并将其添加到结果数组
arr中。 - 这种方法的时间复杂度较高，因为对于每个窗口都需要进行一次遍历查找最大值。
第二段代码：
- 它使用一个单调递减的队列
queue来维护滑动窗口内可能成为最大值的元素。 - 当新元素大于队列末尾的元素时，将末尾元素弹出，以保持队列的递减性质。
- 当队列头部的元素不在当前窗口范围内时，将其移出队列。
- 当窗口滑动到足够长度后，将队列头部的元素作为当前窗口的最大值添加到结果数组
res中。
总结
本文介绍了JavaScript中的队列，结合leetcode全面解读
希望看到这里的你能够有所收获！！！！！！！
原文地址：https://blog.csdn.net/weixin_56440777/article/details/140182134
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！