队列的定义

队列是遵循先进先出原则的一组有序的项，与栈的不同的是，栈不管是入栈还是出栈操作都是在栈顶操作，队列则是在队尾添加元素，队顶移除，用一个图来表示大概是这样事的：

队列的创建

与栈的创建类似，首先创建一个表示队列的函数，然后定义一个数组用来保存队列里的元素：

function Queue() {  let items = []}

创建队列后需要为其定义一些方法，一般来说队列包含以下方法：

• enqueue(element)：向队的尾部添加一个新的项
• dequeue()：移除队列第一项，并返回被移除的元素
• front()：返回队列第一项，队列不做任何变动
• isEmpty()：如果队列中没有任何元素返回true，否则返回false
• size()：返回队列包含的元素个数

具体实现：

function Queue() {  let items = []  // 向队列的尾部添加新元素  this.enqueue = function (element) {    items.push(element)  }  // 遵循先进先出原则，从队列的头部移除元素  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())  }}

队列的使用

接下来让我们看看队列的使用：

let queue = new Queue()queue.enqueue('a')queue.enqueue('b')queue.enqueue('c')queue.dequeue()queue.print()

首先向队列中添加三个元素：a,b,c,然后移除队列中的一个元素，最后打印现有队列，让我们一起图解这个过程：

es6实现Queue

和实现Stack类一样，也可以用es6的class语法实现Queue类，用WeakMap保存私用属性items，并用闭包返回Queue类，来看具体实现：

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

优先队列

优先队列顾名思义就是：队列中的每个元素都会有各自的优先级，在插入的时候会根据优先级的高低顺序进行插入操作，和前面队列实现有点不太一样的地方，队列中的元素多了有先级的属性，下面来看具体代码：

function PriorityQueue() {  let items = []  // 队列元素，多定义一个优先级变量  function QueueElement(element, priority) {    this.element = element    this.priority = priority  }  this.enqueue = function (element, priority) {    let queueElement = new QueueElement(element, priority)    let added = false    for (let i = 0; i < items.length; i++) {      //数字越小优先级越高      if (queueElement.priority < items[i].priority) {        items.splice(i, 0, queueElement)        added = true        break      }    }    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 = 0; i < items.length; i++) {      console.log(`${items[i].priority}-${items[i].element}`)    }  }}let priorityQueue = new PriorityQueue()priorityQueue.enqueue('a', 3)priorityQueue.enqueue('b', 2)priorityQueue.enqueue('c', 1)priorityQueue.dequeue()priorityQueue.print()

入队时如果队列为空直接加入队列，否则进行比较，priority小的优先级高，优先级越高放在队列的越前面，下面用一个图来看调用过程：

循环队列

循环队列顾名思义就是：给定一个数，然后迭代队列，从队列开头移除一项，然后再将其加到队列末尾，当循环到给定数字时跳出循环，从队首移除一项，直至剩余一个元素，下面来看具体代码：

unction Queue() {  let items = []  this.enqueue = function (element) {    items.push(element)  }  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())  }}function loopQueue(list, num) {  let queue = new Queue()  for (let i = 0; i
    
      1) {    for (let j = 0; j
    

总结

这篇文章主要对队列做了简单介绍，对队列以及相关应用做了简单实现。如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞。