JS中的算法与数据结构之队列(Queue)实例详解

什么是队列？

队列是一种线性数据结构，它是一种先进先出的数据结构(FIFO)，即最先进队列的元素也最先出队列。

队列有两个基本操作：入队和出队。入队将元素添加到队列的末尾，而出队则是从队列的前端删除元素。

队列的实现方式

我们可以用数组和链表来实现队列，这里我们介绍一下使用数组来实现队列的方式。

用数组实现队列

我们可以在数组的末尾添加元素，从数组头部删除元素。当元素出队列时，我们可以将数组的第一个元素删除。这个过程可以用 shift 方法来实现，而入队操作可以使用 push 方法来往数组的末尾添加元素。

下面是一个使用数组实现队列的示例：

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

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

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

以上代码中，我们定义了一个 Queue 类作为队列的实现，该类的构造函数里定义了一个 items 数组，这个数组存储着队列的元素。

我们使用 enqueue 方法将元素添加到数组的末尾，使用 dequeue 方法从数组的头部删除元素。

用链表实现队列

链表与数组不同，它们没有固定的大小。我们可以使用一个包含 value 和 next 属性的节点来实现链表队列。

下面是一个使用链表实现队列的示例：

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(item) {
    const node = new QueueNode(item);

    if (this.tail) {
      this.tail.next = node;
    } else {
      this.head = node;
    }

    this.tail = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return null;

    const item = this.head.value;

    if (this.head === this.tail) {
      this.tail = null;
    }

    this.head = this.head.next;
    this.length--;

    return item;
  }
}

以上代码中，我们定义了 QueueNode 类作为队列链表节点的实现，该类包含 value 和 next 属性，分别对应节点的值和下一个节点。

Queue 类定义了队列链表的实现，其中的 head 和 tail 属性分别表示队列的头节点和尾节点。我们使用 enqueue 方法向队列中添加元素，使用 dequeue 方法从队列中删除元素。

队列的应用场景

队列广泛应用于计算机科学和实际生活中诸如广告投放、大数据处理和操作系统等领域。以下是两种队列的应用场景的示例。

打印队列

考虑一个使用打印机的场景。多个人可以向打印队列中提交打印任务，队列会逐个打印所有的任务。这时我们可以使用队列来实现打印任务的队列，先进先出。

class PrintQueue {
  constructor() {
    this.queue = new Queue();
    this.timer = null;
    this.delay = 5000;
  }

  enqueue(item) {
    this.queue.enqueue(item);

    if (!this.timer) {
      this.timer = setTimeout(() => this.print(), this.delay);
    }
  }

  dequeue() {
    return this.queue.dequeue();
  }

  print() {
    if (!this.queue.length) {
      clearTimeout(this.timer);
      this.timer = null;
    } else {
      const item = this.queue.dequeue();
      console.log(`Printing ${item}...`);
      setTimeout(() => this.print(), this.delay);
    }
  }
}

const printQueue = new PrintQueue();
printQueue.enqueue("Document A");
printQueue.enqueue("Document B");

以上代码中，我们定义了一个 PrintQueue 类作为打印队列的实现，该类包含了一个队列和一个打印计时器。进入队列的任务将以先进先出的方式进行打印。

更长时间的排队队列

在很多场景中，用户在排队时可能需要等待较长时间。这里我们可以使用队列来管理排队用户。当排队人数超过一个给定的限制时，我们可以向队列中添加一个状态为等待的用户。当一个用户完成服务时，我们可以处于等待状态的用户中取出一个进行服务。

class WaitQueue {
  constructor(limit) {
    this.queue = new Queue();
    this.limit = limit;
  }

  push(item) {
    if (this.queue.length >= this.limit) return false;

    this.queue.enqueue(item);
    return true;
  }

  pop() {
    return this.queue.dequeue();
  }
}

const waitQueue = new WaitQueue(3);
waitQueue.push("User A");
waitQueue.push("User B");
waitQueue.push("User C");
waitQueue.push("User D"); // 队列已满，无法添加

console.log(waitQueue.pop()); // User A
console.log(waitQueue.pop()); // User B
console.log(waitQueue.pop()); // User C

以上代码中，我们定义了一个 WaitQueue 类作为排队队列的实现，该类有一个 limit 属性限制该队列长度。可以使用 push 方法向队列中添加元素，当队列已满时，将无法添加新元素。可以使用 pop 方法从队列中删除元素，这个队列遵循先进先出的原则。