前言

在JavaScript中，队列可以通过数组实现，也可以使用专门的队列数据结构（如使用链表实现的队列）。今天这篇文章我们将介绍JS中队列的特点以及如何将队列实际应用去解决算法题

正文

JavaScript中的队列和栈是两种常见的数据结构，我们先来看看二者之间的异同

相同点：

1. 都是线性数据结构： 队列和栈都是线性的数据结构，即其中的元素按照一定的顺序排列。
2. 支持添加和移除元素： 队列和栈都支持添加元素和移除元素的操作，但添加和移除的方式略有不同：

对于栈，我们可以使用数组的 push() 方法向栈顶添加元素，使用 pop() 方法从栈顶移除元素。符合栈的后进先出的原则

对于队列，我们可以使用数组的 push() 方法向队列尾部添加元素，使用 shift() 方法从队列头部移除元素。这符合队列的先进先出

不同点：

1. 操作方式：

   • 队列（Queue）： 遵循先进先出（FIFO）的原则，即最先进入队列的元素最先被移除。
   • 栈（Stack）： 遵循后进先出（LIFO）的原则，即最后压入栈的元素最先被移除。

2. 元素添加和移除的位置：

   • 队列（Queue）： 元素的添加和移除分别发生在队列的两端，即添加操作发生在队列的末尾，移除操作发生在队列的开头。
   • 栈（Stack）： 元素的添加和移除都发生在栈的同一端，即栈顶。

3. 使用场景：

   • 队列（Queue）： 适用于需要按顺序处理数据的场景，比如任务调度、消息传递等。
   • 栈（Stack）： 适用于需要后进先出顺序处理数据的场景，比如函数调用栈、表达式求值等。

• 使用数组来模拟队列

const queue2 = []
queue2.push('辣椒炒辣椒')
queue2.push('西红柿炒鸡蛋')
queue2.push('土豆烧牛腩')

 for (let i = 0; i< queue2.length;i++){
     const top = queue2.shift()
     console.log(top);
 }

在这段代码中我们创建了一个名为 queue2 的数组，并向其中依次添加了三个元素：'辣椒炒辣椒'、'西红柿炒鸡蛋' 和 '土豆烧牛腩'。这样，queue2 数组现在就代表了一个简单的队列，其中包含了三个元素，按照入队的顺序排列。这时我们用for循环来遍历并处理队列中的元素。这个数组中的3个元素都能被打印出来吗？

我们会发现只打印出来了前两个元素，这是为什么呢？

问题在于，在 for 循环中使用 shift() 方法会导致队列长度的变化，因为每次移除元素后，队列的长度都会减少。

    const queue2 = []
queue2.push('辣椒炒辣椒')
queue2.push('西红柿炒鸡蛋')
queue2.push('土豆烧牛腩')
while(queue2.length){
    const top = queue2.shift()
    console.log(top);
}

相比之下，使用 while 循环确保在每次迭代中都检查队列的长度，直到队列为空才结束循环，这样更安全可靠。也能成功打印出来这3个元素。

在了解完了JS中队列的基本属性后，我们可以看看下面的算法题

var MyQueue = function () {
    this.stack1 = [];
    this.stack2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.stack1.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    //栈2还有没有全部出栈，还有元素时，栈1的元素，不往栈2导入，否则会导致栈2出栈的不是真正的栈顶元素
    if (!this.stack2.length) {
        //遍历第一个栈，将第一个栈中的元素全部导入栈2中
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    //栈2还有没有全部出栈，还有元素时，栈1的元素，不往栈2导入，否则会导致栈2出栈的不是真正的栈顶元素
    if (!this.stack2.length) {
        //遍历第一个栈，将第一个栈中的元素全部导入栈2中
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop());
        }
    }
    const stack2Len = this.stack2.length;
    return this.stack2[stack2Len- 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    if(this.stack1.length == 0 && this.stack2.length == 0){
        return true;
    }
    return false;
    // return !this.stack1.length && !this.stack2.length;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

这段代码实现了使用两个栈来实现先入先出队列。这里是实现的思路：

• 使用两个数组 stack1 和 stack2 分别表示队列的两个栈。
• push 方法直接将元素压入 stack1。
• pop 方法先判断 stack2 是否为空，如果为空，则将 stack1 中的元素逐个弹出并压入 stack2，然后从 stack2 中弹出栈顶元素。如果 stack2 不为空，则直接从 stack2 中弹出栈顶元素。
• peek 方法实现与 pop 方法类似，但不会从 stack2 中弹出元素，只是返回栈顶元素。
• empty 方法直接判断两个栈是否均为空即可。

这种实现方式保证了入队和出队操作的时间复杂度为 O(1)，同时也满足了先进先出的队列特性。

总结

在本文中我们介绍了栈与队列的相似性以及它们与数组的区别，同时用队列解决算法题也是一个不错的方法。在日常开发中，充分理解队列的工作原理对于优化代码结构、提高程序执行效率具有重要意义。无论是处理异步任务，还是设计复杂的算法，队列都是一种非常实用的数据结构。通过深入学习队列，我们可以更好地应对各种编程挑战，并写出更加高效、健壮的JavaScript代码。

希望这篇文章能对大家有所帮助，同时我们将在下一篇介绍如何利用队列优化时间复杂度来解决算法题！