Skip to content

队列结构

· 2 min

队列结构也是一种逻辑结构，它遵循先进先出（FIFO，First In First Out）的原则。队列中的元素总是从队列的前端（称为“队首”）被移除，而新的元素则被添加到队列的后端（称为“队尾”）。因此，第一个进入队列的元素会最先被移除，类似于排队等候的场景。

队列结构特点

  1. 先进先出（FIFO）：元素会按照顺序被处理，第一个进入队列的元素最先被移除。
  2. 队首和队尾：元素从队尾添加进入，从队首被移除。
  3. 动态大小

队列的基本操作

队列的基本操作包括以下几种：

  1. enqueue（入队）：添加一个元素到队尾
  2. dequeue（出队）：移除并返回队首的元素
  3. peek（或 front）：返回队首的元素，但是不移除
  4. back：返回队尾的元素，但是不移除
  5. isEmpty：是否为空
  6. size：返回队列中元素的数量

代码实现

JS 中没有直接提供队列这种数据结构，可以基于数组或链表来实现栈结构。

class Queue {
  constructor(...args) {
    this.queue = [...args]
  }
  enqueue(...item) {
    return this.queue.push(...item)
  }
  dequeue() {
    return this.queue.shift()
  }
  size() {
    return this.queue.length
  }
  isEmpty() {
    return this.size() === 0
  }
  front() {
    return this.isEmpty() ? undefined : this.queue[0]
  }
  back() {
    return this.isEmpty() ? undefined : this.queue[this.size() - 1]
  }
}

测试代码如下：

const queue = new Queue(1, 2, 3, 4, 5)
console.log(queue.size()) // 5
console.log(queue.front()) // 1
console.log(queue.back()) // 5
queue.enqueue(6, 7, 8)
console.log(queue.size()) // 8

常见场景

  1. 事件循环
  2. 动画队列
  3. 缓存系统

-EOF-