JS中队列和双端队列实现及应用详解

什么是队列？

队列是指一种线性数据结构，它按照先进先出（FIFO）的原则进行排序。队列只允许在后端（称为tail）进行插入操作，在前端（称为head）进行删除操作。例如，当你在一家银行排队等待服务时，由于先来的人先获得服务的原则，所以你必须在队列中等待，直到你到达前面。当有人从银行窗口出来时，他们排在你的前面的所有人都必须离开，直到你才能接受服务。

在编程中，队列常见的应用场景包括：任务调度，缓存管理以及消息队列等。

队列的实现

使用数组实现队列

最简单的实现方式就是使用数组来模拟队列。我们可以使用push方法往数组的尾部插入元素，使用shift方法从数组的头部删除元素。这样就能够满足队列的先进先出原则。

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

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

  dequeue() {
    return this.elements.shift();
  }

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

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

双端队列的实现

双端队列是队列的一种扩展，它允许我们在头部和尾部同时进行插入和删除操作。这种特性使得双端队列非常适合用来实现某些算法和数据结构，如双端搜索、滑动窗口等。

在JavaScript中，我们可以使用数组来模拟双端队列。我们可以使用push方法往数组的尾部插入元素，使用shift方法从数组的头部删除元素，使用unshift方法从数组的头部插入元素，使用pop方法从数组的尾部删除元素。

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

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

  addBack(element) {
    this.elements.push(element);
  }

  removeFront() {
    return this.elements.shift();
  }

  removeBack() {
    return this.elements.pop();
  }

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

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

应用场景

任务调度

在任务调度中，队列被用于维护待执行任务的队列。每个任务都被封装为一个函数，当任务执行完毕时，我们将其从队列中删除。任务调度器不断地从队列中取出任务并执行，直到队列为空。

function taskA() {
  console.log("Task A");
}

function taskB() {
  console.log("Task B");
}

function taskC() {
  console.log("Task C");
}

class Scheduler {
  constructor() {
    this.queue = new Queue();
    this.maxConcurrent = 2;
    this.running = 0;
  }

  addTask(task) {
    this.queue.enqueue(task);
    this.schedule();
  }

  schedule() {
    while (!this.queue.isEmpty() && this.running < this.maxConcurrent) {
      const task = this.queue.dequeue();
      task();
      this.running++;
      setTimeout(() => {
        this.running--;
        this.schedule();
      }, 1000);
    }
  }
}

const scheduler = new Scheduler();
scheduler.addTask(taskA);
scheduler.addTask(taskB);
scheduler.addTask(taskC);

上面的代码中，我们定义了三个任务taskA、taskB和taskC，并将它们添加到任务调度队列中。我们使用Scheduler类来管理任务调度，它的addTask方法用于添加任务。我们使用了一个while循环来检查队列中是否有任务可供执行，同时也保证了我们的任务调度器最多会同时执行两个任务。

滑动窗口

滑动窗口算法是一种用于解决字符串和数组问题的常用算法，它可以用队列来实现。滑动窗口算法用来在一个大字符串中寻找一个长度固定的子串，满足一些限定条件。

function findSubstring(s, t) {
  const n = s.length, m = t.length;
  const ans = [];

  if (n < m) return ans;

  const cntS = new Array(128).fill(0);
  const cntT = new Array(128).fill(0);

  for (let i = 0; i < m; i++) {
    cntT[t.charCodeAt(i)]++;
  }

  const check = () => {
    for (let i = 0; i < 128; i++) {
      if (cntT[i] > cntS[i]) return false;
    }
    return true;
  }

  for (let i = 0; i < m; i++) {
    cntS[s.charCodeAt(i)]++;
  }

  if (check()) ans.push(0);

  for (let i = m; i < n; i++) {
    cntS[s.charCodeAt(i - m)]--;
    cntS[s.charCodeAt(i)]++;
    if (check()) ans.push(i - m + 1);
  }

  return ans;
}

上面的代码中，我们定义了一个findSubstring方法，用于在字符串s中寻找子串t。我们首先统计了子串t中每个字符的出现次数，并存储在cntT数组中。然后，我们设定一个长度为m的窗口，从字符串s的开头向右滑动。每次滑动窗口，我们都会更新cntS数组，它存储了当前窗口中每个字符的出现次数。如果当前窗口中的字符出现次数满足要求，那么我们就将窗口的起始位置加入到答案列表中。

总结

队列和双端队列是非常常见的数据结构，它们具有广泛的应用场景。JavaScript提供了很多实现队列和双端队列的方法，包括使用数组实现，使用链表实现等等。在实际开发中，我们通常会选择最简单、最直接的实现方式，以便能够满足我们的需求。在设计算法和数据结构时，我们需要根据具体情况灵活地选择合适的数据结构以及相应的实现方式。