• 数据结构之数组
• 数据结构之队列
• 数据结构之栈
• 数据结构之链表
• 数据结构之树
• 数据结构之图

队列是一种先来先服务，先进先出（FIFO）的数据结构。日常中排队就是最常见的队列。在计算机科学中，打印队列就是一种很常见的队列。

与创建栈类似，可以利用数组来创建队列，需要 enqueue（入列），dequeue（出列），front（返回队顶），isEmpty（是否为空），size（长度），print（打印）等方法。

function Queue() {let items = []
  this.enqueue = function(elem) {items.push(elem)
  }
  this.dequeue = function() {return items.shift()
  }
  this.front = function() {return items[0]
  }
  this.isEmpty = function() {return items.length === 0}
  this.size = function() {return items.length}
  this.print = function() {console.log(items.toString())
  }
}

以构造函数式声明类，与栈有相同的问题，虽然可以保证私有变量，但是当创建多个实例，类也会创建多个 items 副本，这样的情况下，无疑对性能损耗十分大。可以利用闭包，ES6 和 WeakMap 封装成一个高效且有私有变量 items 的队列类。注意声明的闭包切记 return Queue 的类，不然会报错 Queue not a constructor。

let Queue = (function() {const items = new WeakMap()
  class Queue {constructor() {items.set(this, [])
    }
    enqueue(elem) {let queue = items.get(this)
      queue.push(elem)
    }
    dequeue() {let queue = items.get(this)
      return queue.shift() }
    front() {let queue = items.get(this)
      return queue[0]
    }
    isEmpty() {let queue = items.get(this)
      return queue.length === 0
    }
    size() {let queue = items.get(this)
      return queue.length
    }
    print() {let queue = items.get(this)
      console.log(queue.toString())
    }
  }
  return Queue
})()

优先队列

类似医院急诊，或者登机头等舱等，队列有时也需要分队列等级，优先处理的队列叫做优先队列。可以这么理解，队列中有若干元素，而不同等级的元素扎堆，按等级形成不同等级的优先队列，如默认队列 [1,2,3,4,5,6,7]，根据优先级排列后，可以理解成 [[1,2,5][3,4][6,7]]。同一优先级按照 FIFO 原则。定义这类队列与传统队列不同的地方在于，在插入队列元素的时候，还要传一个代表优先级的参数，判断当前插入元素的优先级。

function PriorityQueue() {let items = [] // 私有变量 items，保证外界不能直接访问
  function QueueElement(elem, priority) {
    // 创建一个构造函数，每次插入就生成等待队列
    this.elem = elem
    this.priority = priority
  }
  this.enqueue = function(elem, priority) {
    // 优先队列的核心，插入方法
    let queueElement = new QueueElement(elem, priority) // 每次插入都生成等待队列的实例
    let added = false // 初始化已插入状态
    for (let i in items) {
      // 遍历 items 中的元素
      // 如果待插入元素的优先级高于（优先级数值越小，优先等级越高）items 中元素的优先级，则插入在 items 中原有的元素之前，同时将已插入状态（added）修改成 true
      if (queueElement.priority < items[i].priority) {items.splice(i, 0, queueElement)
        added = true
        break
      }
    }
    // 如果待插入元素的优先级比所有的 items 都小，那么就直接插入队列即可
    if (!added) {items.push(queueElement)
    }
  }
  this.dequeue = function() {return items.shift()
  }
  this.front = function() {return items[0]
  }
  this.isEmpty = function() {return items.length === 0}
  this.size = function() {return items.length}
  this.print = function() {for (let i in items) {console.log(`${items[i].elem} - ${items[i].priority}`)}}
}

封装成 ES6:

let PriorityQueue = (function() {const items = new WeakMap()
  class QueueElement {constructor(elem, priority) {
      this.elem = elem
      this.priority = priority
    }
  }
  class Queue {constructor() {items.set(this, [])
    }
    enqueue(elem, priority) {let queueElement = new QueueElement(elem, priority)
      let added = false
      let queue = items.get(this)
      for (let i in queue) {if (queueElement.priority < queue[i].priority) {queue.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      if (!added) {queue.push(queueElement)
      }
    }
    dequeue() {let queue = items.get(this)
      return queue.shift() }
    front() {let queue = items.get(this)
      return queue[0]
    }
    isEmpty() {let queue = items.get(this)
      return queue.length === 0
    }
    size() {let queue = items.get(this)
      return queue.length
    }
    print() {let queue = items.get(this)
      for (let i in queue) {console.log(`${queue[i].elem} - ${queue[i].priority}`)}}
  }
  return Queue
})()

循环队列

队列还有一种特殊形态，最常见的循环队列就是击鼓传花（传递热土豆）：

function hotPotato(nameList, num) {let queue = new Queue() // 声明一个队列
  for (let i in nameList) {queue.enqueue(nameList[i]) // 元素插入队列
  }
  let eliminated = '' // 初始化淘汰者
  while (queue.size() > 1) {
    // 若队列元素（人数）不止一个
    for (let i = 0; i < num; i++) {
      // 模拟鼓声停止之前，第一个人（拿着热土豆）把土豆传给下一个（也就是等价于自己排到队列最后了，所以自己出队列，插入队列最后）
      queue.enqueue(queue.dequeue())
    }
    eliminated = queue.dequeue() // 鼓声停止，第一个人淘汰（拿着热土豆）
    console.log(`${eliminated} 在游戏中被淘汰 `) }
  return ` 胜利者：${queue.dequeue()}` // 所有人出队列，最后的人胜出
}

此外，js 的任务处理也是队列，当浏览器打开新标签时，就会创建一个任务队列，因为每个标签都是单线程，所以这个标签内的所有事件（包括渲染 HTML，执行 js 脚本，io 处理，交互，http 请求，ajax 网络请求等）都会进入一个待处理队列，一项一项进行。这被称为事件循环。