队列的定义
队列是遵循先进先出原则的一组有序的项，与栈的不同的是，栈不管是入栈还是出栈操作都是在栈顶操作，队列则是在队尾添加元素，队顶移除，用一个图来表示大概是这样事的：用一个更形象的例子就是：排队服务，总是先排队的人会先接受服务，当然不考虑插队的情况
队列的创建
与栈的创建类似，首先创建一个表示队列的函数，然后定义一个数组用来保存队列里的元素：
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<list.length; i++) {
queue.enqueue(list[i])
}
while (queue.size() > 1) {
for (let j = 0; j<num; j++) {
queue.enqueue(queue.dequeue())
}
let out = queue.dequeue()
console.log(‘ 出队列：’ + out)
}
return queue.dequeue()
}
console.log(‘last：’ + loopQueue([‘a’, ‘b’, ‘c’, ‘d’, ‘e’], 3))
总结
这篇文章主要对队列做了简单介绍，对队列以及相关应用做了简单实现。如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞。