前言

如果说先进后出的栈是个缸，那先进先出的队列就是根排水管。 今天我们就来聊聊队列这个数据结构。

正文

队列（Queue） 是一种线性数据结构，它遵循先进先出（First In First Out，简称FIFO）的原则。

在队列中，最先加入的元素将会是最先被移除的。

队列有两个主要的操作点：队尾（enqueue）和队首（dequeue）。

在队尾添加元素，在队首移除元素。

在JavaScript中，可以使用数组来模拟队列的行为。

但是，使用数组作为队列时需要注意，数组的 shift 和 unshift 方法的时间复杂度为O(n)，因为它们涉及到元素的移动。

因此，对于频繁的队首操作，使用数组可能不是最优的选择。

在高性能要求的场景下，可以考虑使用专门的队列数据结构实现。

队列的基本操作

1. enqueue: 在队列的尾部添加一个元素。
2. dequeue: 移除队列的头部元素并返回它。
3. peek/front: 查看队列的头部元素，但不移除它。
4. isEmpty: 检查队列是否为空。
5. size: 返回队列中元素的数量。

使用数组模拟队列

在 JavaScript 中，可以使用 push 和 shift 方法来模拟队列的行为。push 方法在数组的末尾添加元素，而 shift 方法移除并返回数组的第一个元素。也可以使用 unshift 和 pop 方法

const queue = [1, 2, 3]; // 用作队列，使用 push 和 shift 方法，或者 unshift 和 pop 方法

// 创建一个队列实例 queue1
const queue1 = [];
// 向队列中添加元素
queue1.push('a');
queue1.push('b');
queue1.push('c');

// 使用 while 循环来遍历并移除队列中的元素，直到队列为空
while (queue1.length) {
    const top = queue1.shift(); // 从队列前端移除元素
    console.log(top); // 打印移除的元素
}

使用类定义队列

class Queue {
   constructor() {
       this.items = [];
   }

   enqueue(element) {
       this.items.push(element);
   }

    dequeue() {
        if (this.isEmpty()) {
            return "Underflow";
        }
        return this.items.shift();
    }

    peek() {
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

使用示例

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.peek()); // 输出 1
console.log(queue.size()); // 输出 3
console.log(queue.dequeue()); // 输出 1
console.log(queue.dequeue()); // 输出 2
console.log(queue.isEmpty()); // 输出 false
console.log(queue.dequeue()); // 输出 3
console.log(queue.isEmpty()); // 输出 true

例题：用栈实现队列

题目地址：leetcode.cn/problems/im…

1. constructor()

   构造函数初始化两个空栈 stack1 和 stack2。

   • stack1 :模拟队列入队操作;
   • stack2 :模拟队列的出队和查看队首元素操作。

2. push(x)

   将元素 x 推入 stack1。

   由于栈的特性，新元素总是被添加到栈顶，但在队列的上下文中，这相当于元素入队。

3. pop() ：

   当调用 pop 方法时，首先检查 stack2 是否为空。

   如果 stack2 为空，那么将 stack1 中的所有元素依次弹出并推入 stack2。

   由于 stack1 的元素是以先进后出方式存储的，因此在 stack2 中它们将以先进先出方式排列。

   然后从 stack2 弹出顶部元素，模拟队列的出队操作。

4. peek()

   与 pop 类似，如果 stack2 为空，先将 stack1 中的元素全部转移到 stack2。

   然后返回 stack2 的顶部元素，但不弹出，模拟队列的查看队首元素操作。

5. empty()

   检查两个栈是否都为空，���果两个栈都没有元素，那么队列为空，返回 true；否则返回 false。

var MyQueue = function () {//初始化
    this.stack1 = []
    this.stack2 = []
};

MyQueue.prototype.push = function (x) {//入stack1，即入队
    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
};

双端队列

双端队列（Deque，Double-ended queue）也是一种线性数据结构，但它允许在两端进行插入和删除操作。也就是说，双端队列可以在队列的任意一端进行入队和出队操作。

双端队列的基本操作：

1. addFront: 在队列的前端添加一个元素。
2. addRear: 在队列的后端添加一个元素。
3. removeFront: 移除队列的前端元素并返回它。
4. removeRear: 移除队列的后端元素并返回它。
5. peekFront: 查看队列的前端元素，但不移除它。
6. peekRear: 查看队列的后端元素，但不移除它。
7. isEmpty: 检查队列是否为空。
8. size: 返回队列中元素的数量。

使用JavaScript数组模拟双端队列：

class Deque {
   constructor() {
       this.items = [];
   }

   addFront(element) {
       this.items.unshift(element);
   }

    addRear(element) {
        this.items.push(element);
    }

    removeFront() {
        if (this.isEmpty()) {
            return "Underflow";
        }
        return this.items.shift();
    }

    removeRear() {
        if (this.isEmpty()) {
            return "Underflow";
        }
        return this.items.pop();
    }

    peekFront() {
        return this.items[0];
    }

    peekRear() {
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

例题：滑动窗口最大值

题目地址：leetcode.cn/problems/sl…

对于这题的思路就是不断地让窗口移动，在每个窗口里找到最大值，加入到数组里,但是如果我们采用常规的思路就会导致超时

超时：

var maxSlidingWindow = function(nums, k) {
   const len = nums.length; // 获取输入数组的长度
   const res = [];          // 初始化一个空数组，用于存储结果

    // 初始化窗口的起始和结束索引
    let i = 0; 
    let j = k - 1;

    // 当窗口的结束索引小于数组长度时，表示窗口还在数组范围内
    while (j < len) {
        // 调用 calMax 函数，计算当前窗口的最大值
        const max = calMax(nums, i, j);
        // 将当前窗口的最大值添加到结果数组中
        res.push(max);
        // 更新窗口的起始和结束索引，向右移动窗口
        i++;
        j++;
    }

    // 返回结果数组
    return res;
};

function calMax(arr, i, j) {
    let max = -Infinity; // 初始化最大值为负无穷大，确保任何数组元素都比它大

    // 遍历区间 [i, j] 内的所有元素
    for (let m = i; m <= j; m++) {
        // 如果当前元素比已知的最大值大，则更新最大值
        if (arr[m] > max) {
            max = arr[m];
        }
    }

    // 返回计算得到的最大值
    return max;
}

所以我们就需要一种更高效的方法：双端队列

在移动窗口时，我们只需要简单地添加和移除元素（添加队尾元素，删除队首元素，这样这个窗口还是只保留k个元素），而不需要重新遍历整个窗口来计算最大值。这种方法避免了重复计算，提高了算法的效率。

我们只需要判断新加进窗口的元素与删除的值，以及上个窗口的最大值 的关系即可

var maxSlidingWindow = function(nums, k) {
   const len = nums.length; // 获取数组的长度
    const res = [];          // 初始化结果数组，用于存储每个窗口的最大值
   
   // 单调队列，用于存储窗口内元素的索引
   const queue = []; 
   
   // 遍历整个数组
   for (let i = 0; i < len; i++) {
       // 保持队列的单调性
       // 当队列非空且队列尾部元素对应的值小于等于当前元素值时
       // 移除队列尾部元素，以保持队列的递减特性
       while (queue.length && nums[queue[queue.length - 1]] <= nums[i]) {
            queue.pop();
        }
        
        // 将当前元素的索引加入队列
        queue.push(i);
        
        // 处理窗口移动
        // 当队列头部元素的索引小于等于i-k时，表示该元素已经不在当前窗口内
        // 因此，从队列头部移除该元素的索引
        while (queue.length && queue[0] <= i - k) {
            queue.shift();
        }
        
        // 当窗口达到大小k时，记录窗口内的最大值
        // 队列头部的元素索引对应的就是窗口内的最大值
        if (i >= k - 1) {
            res.push(nums[queue[0]]);
        }
    }
    
    // 返回结果数组
    return res;
};

结语

以上就是对队列以及双端队列的介绍，

队列新元素入队尾，旧元素出队首。双端队列两端均可入队出队，灵活高效，兼具队列与栈特性。

希望本文对你有所帮助，感谢你的阅读！