上一章我们讲到了栈，这次我们来讲队列。其实队列和栈有很多相似的地方，比如它们都是线性表，操作都是受限。区别也是比较明显，队列主要是先进先出，和排队一样，但是栈是先进后出。队列的先进先出这两个操作对应的是入队（enqueue）和出队（dequeue），入队是从队尾插入一个元素，出队是从队头使一个元素出队。
队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
队列和栈一样，可以通过数组和栈来实现。如果是数组实现的就叫顺序队列，链表实现的叫链式队列。下面通过JavaScript代码来分别实现链式队列和顺序队列：
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
class linkedList {
constructor(length) {
this.head = null
this.length = length // 声明队列长度
this.currLength = 0 // 队列实际长度
}
enqueue (item) {
let curr = this.head
let newNode = new Node(item)
if (curr == null) {
this.head = newNode
curr = this.head
}
else {
++this.currLength
if (this.currLength < this.length) {
while (curr) {
if (curr.next) {
curr = curr.next
}
else {
curr.next = newNode
break
}
}
}
else {
return false
}
}
}
dequeue () {
// 队列为空的情况下直接返回null
let curr = this.head
if (this.head != null) {
let next = this.head.next
this.head = next
--this.currLength
}
return curr
}
}这段链式队列的代码很好理解。在入队的时候将结点不断的插入到链表的最后一个结点的next结点里，出队的时候直接将头结点拿出来，并赋值给下一个结点。而顺序链表的操作上则要有两个指针，一个头指针一个尾指针，每次出队操作都会将数组往前移一位，代码如下：
class ArrayLisk {
constructor (length) {
this.queue = new Array(length)
this.head = 0
this.tail = 0
this.currLength = 0
}
enqueue (item) {
++this.currLength
if (this.currLength > this.queue.length) {
return false
}
++this.tail
this.queue[this.currLength - 1] = item
}
dequeue () {
if (this.head === this.tail) {
return null
}
else {
let current = this.queue[0]
for (let a = 0; a < this.queue.length - 1; a++) {
this.queue[a] = this.queue[a + 1]
if (a === this.queue.length - 2) {
this.queue[a + 1] = undefined
}
}
--this.currLength
this.tail = this.currLength
return current
}
}
}上面讲到一些特殊队列有某些额外特性，如循环队列、阻塞队列、并发队列等等，下面我们主要来看一下这三个特殊队列的具体用途。
首先讲的是循环队列。在上面的代码中，如果是用数组来实现一个队列的话，当进行出队操作的时候，数组里的元素都会往前移一位，元素的移动会造成需要更多的时间，这个时候我们就可以用一个循环队列来解决这个问题。循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。如下图：
我们可以看到，图中这个队列的大小为 10，当前 front=1，rear=·10。当有一个新的元素 a 入队时，我们放入下标为 10 的位置。但这个时候，我们并不把 tail 更新为 11，而是将其在环中后移一位，到下标为 1 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 1 的位置，然后 tail 加 1 更新为 2。通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码，我个人觉得，最关键的是，确定好队空和队满的判定条件。
在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？队列为空的判断条件仍然是 head == tail且当前head下标对应的值为空。但队列满的判断条件就稍微有点复杂了，当队满时，(tail+1)%n=head+1且当前tail下标对应的值不为空。下面用代码来实现一下：
class ArrayLisk {
constructor (length) {
this.queue = new Array(length)
this.head = 0
this.tail = 0
}
enqueue (item) {
if ((this.tail + 1) % this.queue.length === this.head + 1 && this.queue[this.tail] !== undefined) {
return false
}
this.queue[this.tail] = item
if (this.tail === this.queue.length - 1) {
this.tail = 0
}
else {
++this.tail
}
}
dequeue () {
if (this.head === this.tail && this.queue[this.head] === undefined) {
return false
}
this.queue[this.head] = undefined
if (this.head === this.queue.length - 1) {
this.head = 0
}
else {
++this.head
}
}
}前面讲的内容理论比较多，看起来很难跟实际的项目开发扯上关系。确实，队列这种数据结构很基础，平时的业务开发不大可能从零实现一个队列，甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
/**
* @description 这里用JavaScript单线程同步状态来模拟了一个阻塞队列，
* 当入队请求远大于出队请求并且队列已满的情况下记录入队数据，
* 下一次出队操作的时候将从溢出的入队数据中读取。
* 当出队请求远大于入队请求并且队列为空的情况下记录出队数量，
* 下一次入队操作的时候将把这数据返回并减少出队数量。
* */
class BlockingQueue extends Array{
constructor(args, size) {
super(...args)
this.sizeLength = args.length // 数组初始长度
this.maxSize = size // 数组限定最长长度
this.pushArr = [] // 溢出的入队数据
this.popSum = 0 // 溢出的出队请求数量
}
enqueue(val) {
if (this.maxSize === this.sizeLength) {
this.pushArr.push(val)
return false
}
if (this.popSum > 0) {
--this.popSum
return val
}
++this.sizeLength
return super.push(val)
}
dequeue() {
if (this.pushArr.length > 0) {
super.push(this.pushArr.shift())
return super.shift()
}
if (this.sizeLength === 0) {
++this.popSum
return false
}
--this.sizeLength
return super.shift()
}
}这里的代码按照上面的情况下做了一点修改，当生产者生产的数据远远多于消费者消费的数据的时候，我们这个时候就要阻塞生产者让消费者能够及时的处理完数据。同理，反过来说如果消费者消费的数据远远多于生产者生产的数据的时候，就阻塞消费者让生产者能够及时的生产数据。这个模式就是设计模式里生产者消费者模式。
上面的例子里可以改造一下，比如Java里的DelayQueue，就是加了个延时器当过了一段时间才开始生产数据或者消费数据。
前面我们讲了阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？
线程安全的队列我们叫作并发队列。。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。由于JavaScript是单线程的，所以模拟Java的多线程的时候一般都是采用异步来实现，这里由于博主水平不够，目前暂时不会用异步的方式实现一个线程安全的并发队列，所以就不贴代码了，感兴趣的可以看Java是如何实现的。
上一篇文章：数据结构与算法的重温之旅（六）——栈
下一篇文章：数据结构与算法的重温之旅（八）——递归
