1.基于数组的实现

/* 基于环形数组实现的队列 */
class ArrayQueue {
  #nums // 用于存储队列元素的数组
  #front = 0 // 队首指针，指向队首元素
  #queSize = 0 // 队列长度

  constructor(capacity) {
    this.#nums = new Array(capacity)
  }

  /* 获取队列的容量 */
  get capacity() {
    return this.#nums.length
  }

  /* 获取队列的长度 */
  get size() {
    return this.#queSize
  }

  /* 判断队列是否为空 */
  isEmpty() {
    return this.#queSize === 0
  }

  /* 入队 */
  push(num) {
    if (this.size === this.capacity) {
      console.log('队列已满')
      return
    }
    // 计算队尾指针，指向队尾索引 + 1
    // 通过取余操作实现 rear 越过数组尾部后回到头部
    const rear = (this.#front + this.size) % this.capacity
    // 将 num 添加至队尾
    this.#nums[rear] = num
    this.#queSize++
  }

  /* 出队 */
  pop() {
    const num = this.peek()
    // 队首指针向后移动一位，若越过尾部，则返回到数组头部
    this.#front = (this.#front + 1) % this.capacity
    this.#queSize--
    return num
  }

  /* 访问队首元素 */
  peek() {
    if (this.isEmpty()) throw new Error('队列为空')
    return this.#nums[this.#front]
  }

  /* 返回 Array */
  toArray() {
    // 仅转换有效长度范围内的列表元素
    const arr = new Array(this.size)
    for (let i = 0, j = this.#front; i < this.size; i++, j++) {
      arr[i] = this.#nums[j % this.capacity]
    }
    return arr
  }
}

2.基于链表的实现

/* 基于链表实现的队列 */
class LinkedListQueue {
  #front // 头节点 #front
  #rear // 尾节点 #rear
  #queSize = 0

  constructor() {
    this.#front = null
    this.#rear = null
  }

  /* 获取队列的长度 */
  get size() {
    return this.#queSize
  }

  /* 判断队列是否为空 */
  isEmpty() {
    return this.size === 0
  }

  /* 入队 */
  push(num) {
    // 在尾节点后添加 num
    const node = new ListNode(num)
    // 如果队列为空，则令头、尾节点都指向该节点
    if (!this.#front) {
      this.#front = node
      this.#rear = node
      // 如果队列不为空，则将该节点添加到尾节点后
    } else {
      this.#rear.next = node
      this.#rear = node
    }
    this.#queSize++
  }

  /* 出队 */
  pop() {
    const num = this.peek()
    // 删除头节点
    this.#front = this.#front.next
    this.#queSize--
    return num
  }

  /* 访问队首元素 */
  peek() {
    if (this.size === 0) throw new Error('队列为空')
    return this.#front.val
  }

  /* 将链表转化为 Array 并返回 */
  toArray() {
    let node = this.#front
    const res = new Array(this.size)
    for (let i = 0; i < res.length; i++) {
      res[i] = node.val
      node = node.next
    }
    return res
  }
}

3.应用

• 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
• 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。