概念用途

特殊的列表

队列顾名思义，可以想一下银行排队的人，排在前面的先办理业务

用在很多地方，比如打印任务池

定义

队列只能队尾插入元素，队首删除元素

是一种 先进先出（FIFO） 的数据结构

插入元素叫做 入队，删除叫做 出队

特殊情况，删除元素不必遵守先进先出的约定，如急诊插队。这种我们需要 优先队列 的数据结构模拟

代码实现

  1. function Queue() {
  2.     this.dataStore = []
  3.     this.inQ = inQ
  4.     this.outQ = outQ
  5.     this.getFirst = getFirst
  6.     this.getLast = getLast
  7.     this.toString = toString
  8.     this.clear = clear
  9.     this.priorityOut = priorityOut
  10. }
  11. function inQ(ele) {
  12.     this.dataStore.push(ele)
  13. }
  15. function outQ() {
  16.     this.dataStore.shift()
  17. }
  18. function getFirst() {
  19.     return this.dataStore[0]
  20. }
  21. function getLast() {
  22.     return this.dataStore[this.dataStore.length - 1]
  23. }
  24. function toString() {
  25.     return this.dataStore
  26. }
  27. function clear() {
  28.     this.dataStore = []
  29. }
  31. var q = new Queue(),
  32. log = console.log
  34. q.inQ('a')
  35. q.inQ('b')
  36. // log(q.toString())
  37. // log(q.outQ())
  38. q.inQ('c')
  39. q.inQ('a')
  40. // log(q.toString())
  41. // log(q.getFirst())
  42. // log(q.getLast())
  43. // log(q.clear())
  44. // log(q.toString())
  47. // 优先队列
  48. // 改造 outQ 方法，遍历队列，优先取出最高级的，一次for 循环解决
  50. function priorityOut() {
  51.     // 第一次写，写出了下面这个蠢东西
  52.     // 实际上我只关心index， priority根本不需要记录，只要大于当前
  53.     // var priority = 0,
  54.     //     index = 0
  55.     // for (var i = 0; i<this.dataStore.length; i++) {
  56.     //     priority = this.dataStore[i].priority > priority ?  this.dataStore[i].priority : priority
  57.     //     index = this.dataStore[i].priority > priority ? i : index
  58.     // }
  59.     //
  60.     // 然后有了如下精妙的排序，这个应该是排序的一个算法。  淦 赶紧学吧
  61.     var priority = 0
  62.     for (var i = 1; i < this.dataStore.length; i++) {
  63.         if (this.dataStore[i].priority > this.dataStore[priority].priority) {
  64.             priority = i
  65.         }
  66.     }
  67.     console.log(priority)
  68.     return this.dataStore.splice(priority, 1)
  69. }
  70. function Person(name, priority) {
  71.     this.name = name
  72.     this.priority = priority
  73. }
  75. personArr = {}
  76. personArr.p1 = new Person('a', 4)
  77. personArr.p2 = new Person('d', 5)
  78. personArr.p3 = new Person('g', 2)
  79. personArr.p4 = new Person('h', 177)
  80. personArr.p5 = new Person('6', 11)
  81. var personQueue = new Queue() 
  82. for (var i = 1; i <= 5; i++) {
  83.     personQueue.inQ(personArr[`p${i}`])
  84. }
  85. log(personQueue.toString())
  86. personQueue.priorityOut()
  87. log(personQueue.toString())

PS：优先队列是改变传统队列的出队方法，使用排序获取最大的index，然后splice出来即可