队列

概念

队列一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。

队列 - 图1

实现

这里会讲解两种实现队列的方式，分别是单链队列和循环队列。

单链队列

  1. class Queue {
  2.   constructor() {
  3.     this.queue = []
  4.   }
  5.   enQueue(item) {
  6.     this.queue.push(item)
  7.   }
  8.   deQueue() {
  9.     return this.queue.shift()
  10.   }
  11.   getHeader() {
  12.     return this.queue[0]
  13.   }
  14.   getLength() {
  15.     return this.queue.length
  16.   }
  17.   isEmpty() {
  18.     return this.getLength() === 0
  19.   }
  20. }

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度，所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

循环队列

  1. class SqQueue {
  2.   constructor(length) {
  3.     this.queue = new Array(length + 1)
  4.     // 队头
  5.     this.first = 0
  6.     // 队尾
  7.     this.last = 0
  8.     // 当前队列大小
  9.     this.size = 0
  10.   }
  11.   enQueue(item) {
  12.     // 判断队尾 + 1 是否为队头
  13.     // 如果是就代表需要扩容数组
  14.     // % this.queue.length 是为了防止数组越界
  15.     if (this.first === (this.last + 1) % this.queue.length) {
  16.       this.resize(this.getLength() * 2 + 1)
  17.     }
  18.     this.queue[this.last] = item
  19.     this.size++
  20.     this.last = (this.last + 1) % this.queue.length
  21.   }
  22.   deQueue() {
  23.     if (this.isEmpty()) {
  24.       throw Error('Queue is empty')
  25.     }
  26.     let r = this.queue[this.first]
  27.     this.queue[this.first] = null
  28.     this.first = (this.first + 1) % this.queue.length
  29.     this.size--
  30.     // 判断当前队列大小是否过小
  31.     // 为了保证不浪费空间，在队列空间等于总长度四分之一时
  32.     // 且不为 2 时缩小总长度为当前的一半
  33.     if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
  34.       this.resize(this.getLength() / 2)
  35.     }
  36.     return r
  37.   }
  38.   getHeader() {
  39.     if (this.isEmpty()) {
  40.       throw Error('Queue is empty')
  41.     }
  42.     return this.queue[this.first]
  43.   }
  44.   getLength() {
  45.     return this.queue.length - 1
  46.   }
  47.   isEmpty() {
  48.     return this.first === this.last
  49.   }
  50.   resize(length) {
  51.     let q = new Array(length)
  52.     for (let i = 0; i < length; i++) {
  53.       q[i] = this.queue[(i + this.first) % this.queue.length]
  54.     }
  55.     this.queue = q
  56.     this.first = 0
  57.     this.last = this.size
  58.   }
  59. }