队列介绍

什么是队列

队列（Queue）是一种操作受限的线性数据结构，它遵循先进先出（First In First Out, FIFO）的原则。这意味着在队列中，新元素被添加至队列的尾部，而元素的移除（读取）发生在队列的头部。

队列是 FIFO，而栈是 LIFO。

队列的特点

1. 先进先出（FIFO）：队列的最基本特点是先进先出，即最先加入队列的元素将是最先被移除的元素。这一特性与现实生活中排队的情境类似，先到的人先服务。
2. 两端操作：队列有两个主要操作端，分别是： 队首（Front）：队列的一端，用于移除元素（出队操作）。 队尾（Rear/Back）：队列的另一端，用于添加新元素（入队操作）。
3. 操作受限：与普通的线性表不同，队列是一种操作受限的数据结构。只允许在队尾进行插入操作，在队首进行删除操作。
4. 时间复杂度：对于理想的队列实现，入队（enqueue）和出队（dequeue）操作的时间复杂度为 O(1)，也就是说，这些操作可以在常数时间内完成，独立于队列中元素的数量。
5. 顺序性：队列保持元素的顺序不变，元素的出队顺序与其入队顺序一致。
6. 数据访问：队列不允许随机访问队列中的元素，只能通过遍历（通常是隐式的，由出队操作实现）来访问元素。

和栈一样，JavaScript 没有内置的队列数据结构，下面有两种实现的队列的方法：

1. 创建一个队列类(Queue)，实现基本方法：enqueue（入队）、dequeue（出队）、peek（查看队首元素），isEmpty（检查队列是否为空）。

class Queue {
  constructor() {
    this.items = [];
  }
  
  enqueue(element) {
    this.items.push(element);
  }
  
  dequeue() {
    if (this.isEmpty()) {
      return 'No elements in Queue';
    }
    return this.items.shift();
  }
  
  peek() {
    return !this.isEmpty() ? this.items[0] : 'No elements in Queue';
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
}

1. 使用两个栈实现队列： 用两个栈来模拟一种队列的行为，实现队列的 enqueue 和 dequeue 操作。

class QueueFromStacks {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }

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

  dequeue() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop() || 'No elements in Queue';
  }
}

队列的应用场景

上面已经讲了队列的介绍和实现方式，可以很明显发现队列在前端领域中有很多应用场景

事件循环队列：

这个我就不多讲了，现在网上已经有很多讲的非常透彻的文章了。简而言之，JavaScript 的事件循环使用队列来管理异步事件的执行顺序。

异步数据加载

为了按照特定的顺序加载异步数据，我们可以创建一个队列来管理异步请求。每次请求完成后，我们可以启动队列中的下一个请求。

class AsyncDataLoader {
  constructor() {
    this.queue = [];
    this.isProcessing = false;
  }

  // 向队列添加异步任务（函数）
  enqueue(task) {
    this.queue.push(task);
    this.processQueue(); // 尝试处理队列
  }

  // 处理队列中的任务
  processQueue() {
    if (this.isProcessing) {
      return; // 如果已经在处理中，直接返回
    }

    // 否则，从队列中拿出下一个任务
    const nextTask = this.queue.shift();
    
    if (nextTask) {
      this.isProcessing = true; // 标记开始处理
      // 执行异步任务
      nextTask().then(() => {
        this.isProcessing = false; // 异步任务完成，标记处理结束
        this.processQueue(); // 递归处理下一个队列任务
      }).catch((error) => {
        console.error('An error occurred:', error);
        this.isProcessing = false; // 出错了也要继续处理下一个
        this.processQueue();
      });
    }
  }
}

// 使用示例
const dataLoader = new AsyncDataLoader();
// 假设 fetchData 是返回 Promise 的异步请求函数
const fetchData = (dataId) => {
  return new Promise((resolve) => {
    setTimeout(() => {
      console.log(`Data ${dataId} loaded.`);
      resolve();
    }, 1000 * dataId); // 模拟加载时间
  });
};

// 按顺序添加任务到队列
dataLoader.enqueue(() => fetchData(1));
dataLoader.enqueue(() => fetchData(2));
dataLoader.enqueue(() => fetchData(3)); // 依次加载 1, 2, 3

在这个例子中，AsyncDataLoader 类用来创建一个队列管理器，管理包含异步任务的队列。每当一个新任务被加入队列时，enqueue 方法会被调用并尝试处理队列。

之后，processQueue 方法检查是否有任务正在处理，如果没有，则从队列中取出下一个任务并执行。执行完毕之后，无论成功与否，它会递归地调用 processQueue 以继续处理队列中的下一个任务。

为了模拟异步数据加载，我们创建了一个 fetchData 函数，它返回一个结合 setTimeout 的 Promise，以模拟数据的异步加载。然后，我们按照特定的顺序将任务加入到 AsyncDataLoader 的实例中。

通过这种方式，我们可以确保即使异步任务的完成时间不同，它们的处理顺序仍然是按照它们被添加到队列中的顺序来执行的。

获取当前请求数量

要在特定时间内获取请求的个数，我们可以维护一个队列用于存储请求发生的时间戳。每次请求到来时，我们就将当前时间戳入队，同时检查并移除队列中超出特定时间窗口的请求时间戳。队列的长度随时反映了特定时间窗口内的请求个数

class RequestQueue {
  constructor(timeWindow) {
    this.queue = [];
    this.timeWindow = timeWindow; // 特定时间窗口（毫秒）
  }

  // 请求到来时调用此方法
  request() {
    const currentTime = Date.now();
    this.queue.push(currentTime); // 入队
    this.removeOldRequests(currentTime); // 移除超时请求
  }

  // 移除超出时间窗口的请求时间戳
  removeOldRequests(currentTime) {
    while (this.queue.length > 0 && currentTime - this.queue[0] > this.timeWindow) {
      this.queue.shift(); // 出队列
    }
  }

  // 获取特定时间窗口内的请求个数
  getRequestCount() {
    return this.queue.length; // 队列长度即为请求个数
  }
}

// 使用示例
const requestStats = new RequestQueue(30000); // 30秒的时间窗口

// 模拟请求的产生
function simulateRequest() {
  requestStats.request();
  console.log(`Requests in the last 30 seconds: ${requestStats.getRequestCount()}`);
}

// 模拟请求产生的随机时刻
setInterval(simulateRequest, Math.floor(Math.random() * 5000)); // 每随机0到5秒发起一次请求

在此例中，RequestQueue 类维护一个队列，其中存储请求发生的时间戳。request() 方法在每次请求到来时被调用，并将当前时间戳入队。removeOldRequests() 方法用于遍历队列并移除队头超出时间窗口范围的请求。getRequestCount() 方法简单返回队列的长度，即在特定时间窗口内的请求个数。

这样，我们就可以通过 requestStats.getRequestCount() 来获取和监控最近特定时间窗口内的请求频率了。