系列文章请查看 「数据结构&算法」必知必会系列：1. 开篇#计划路线
本文为系列文章：常见数据结构——队列，将具体介绍 队列 的特性和几个典型队列的实现，另外具体介绍了队列的几个常见应用。
队列的实现
队列（queue）的概念很好理解，类似现实生活中的排队。正如排队买票、排队等车、排队面试 …… 先到的人先得到服务并离开队列，后来的人加到队列最后。
队列显著的特点是 FIFO (First In, First Out，先进先出)
队列支持两个操作，入队和出队 。队列跟栈一样，也是一种 操作受限的线性表。
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
顺序队列
先思考下，你会如何实现入队和出队？
🙌 入队：数组增加一个新元素；出队：删除第一个元素
基于复杂度考虑，出队的删除不应改变数组长度，而应改变队列头元素 head 指向为下一个即可（如原数组 arr，长度>1，出队后 head 为 a[1]）
那入队呢？熟悉数组的应该会记得其特性——不支持动态扩容（这时，需要用到数据搬移的方法）
容器类，如 Golang slice、JS ArrayList 等已内置支持扩容，其和数据结构的数组实际是不同的。
可回炉：「数据结构&算法」必知必会系列：5. 常见数据结构——数组
若是 Golang 开发，须正确理解 Slice 和原数组的关系，以及熟悉切片操作
简单的 Golang 代码实现如下（slice 大法好，不用考虑扩容啦~ 😁）：
// Queue 是用于存放 int 的队列
type Queue struct {
nums []int
}
// NewQueue 返回 *kit.Queue
func NewQueue() *Queue {
return &Queue{nums: []int{}}
}
// Enqueue 入队
func (q *Queue) EnQueue(n int) {
q.nums = append(q.nums, n)
}
// Dequeue 出队
func (q *Queue) DeQueue() int {
res := q.nums[0]
q.nums = q.nums[1:]
return res
}
https://goplay.tools/snippet/wYzfO9VRT8B Go play~
链式队列
链式队列基于链表实现，再思考一下如何实现？
🙌 入队：相当于链表尾部增加元素；出队：链表头指向更改为下一个结点
这里，就产生了一个问题，如果我们只记录链表头head，入队的时间复杂度会是O(n)，若增加记录链表尾指针 tail，就能减至 O(1)，何乐而不为呢~
链表不熟悉的回炉：「数据结构&算法」必知必会系列：6. 常见数据结构——链表（上）
简单的 Golang 代码实现如下：
type ListNode struct {
Val int
Next *ListNode
}
// Queue 记录链式队列的 头 和 尾
type Queue struct {
head *ListNode
tail *ListNode
}
// NewQueue 返回 *kit.Queue
func NewQueue() *Queue {
return &Queue{nil, nil}
}
// EnQueue 入队 (注意头、尾 nil 的处理)
func (q *Queue) EnQueue(n int) {
newNode := &ListNode{n, nil}
if q.tail != nil {
q.tail.Next = newNode
q.tail = newNode
}
if q.head != nil && q.tail == nil {
q.tail = newNode
q.head.Next = newNode
}
if q.head == nil {
q.head = newNode
}
}
// DeQueue 出队 (注意头、尾 nil 的处理)
func (q *Queue) DeQueue() {
if q.head != nil {
q.head = q.head.Next
}
if q.head != nil && q.head.Next == nil {
q.tail = nil
}
}
https://goplay.tools/snippet/VGwr8RodoKT Go play~
循环队列
实现顺序队列，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？来看下「循环队列」的解决思路。
顾名思义，「循环队列」是一个环，所以也可称为「环形队列」。
假设队列大小为 8（n=8）空队列，头尾为 0，入队后，tail 后移，参考如下：
可以想象成队列变成圆环了，出队，head 后移至 1，入队 tail 后移；
这样，只要环未满，就不存在数据搬移的操作。
至此，我们避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件。
先思考一下如何判定对空？判断条件仍然是 head == tail
那队满呢？可以先自行实验下总结规律
比如，head=5, tail=4，如下图就是满的
head=0, tail=7
head=1, tail=0
head=2, tail=1
...
head=5, tail=4
...
head=7, tail=0
已知大小 n、head、tail
得出规律： (tail+1)%n=head 满足此条件时，队满
入队&出队也就是 head，tail 下标位的变化，操作也类似，自己思考下吧~
!!!注意：当队列满时，tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。所以，初始化的时候，队列长度需要+1
最后，试着自己写下代码吧，Go 示例代码如下：
// 队空的判断条件是 head == tail,
// 队满的判断条件，(tail+1)%n=head。
// 当队列满时，tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。
type CircularQueue struct {
Head int
Tail int
Value []int
}
// Set the size of the queue = n
func Constructor(n int) CircularQueue {
return CircularQueue{
Head: 0,
Tail: 0,
Value: make([]int, n + 1), // Init Value，!!! Pay attention +1
}
}
// Check empty
func (this *CircularQueue) IsEmpty() bool {
if this.Head == this.Tail {
return true
}
return false
}
// Check full: (tail+1)%n=head
func (this *CircularQueue) IsFull() bool {
if (this.Tail+1)%len(this.Value) == this.Head {
return true
}
return false
}
func (this *CircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
this.Value[this.Tail] = value
this.Tail = (this.Tail + 1) % len(this.Value)
return true
}
func (this *CircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
this.Head = (this.Head + 1) % len(this.Value)
return true
}
https://goplay.tools/snippet/v-nRk2jxfw0 Go play~
更多可参考： 622. 设计循环队列 此题为中等题哦~
队列的应用
阻塞队列和并发队列
平时的业务开发不大可能从零实现一个队列，甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。
阻塞队列 其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。如果队列已经满了，那么插入数据的操作就会被阻塞。
是否发现了？上述的定义就是一个“生产者 - 消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！
不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。
在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？
线程安全的队列我们叫作 并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。
实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
熟悉 Java 并发的应该会想到 Disruptor 无锁并发队列，有点深，找了篇相关文章参考 你应该知道的高性能无锁队列Disruptor
线程池中队列的应用
向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队的请求呢？
常见处理排队请求，我们会采取先进者先服务的策略，那么，队列这种数据结构很适合来存储排队请求。
基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
附，以上「阻塞队列和并发队列」以及 「线程池中队列的应用」讲解和附图 均来源 极客时间课程——数据结构与算法之美
Go Channel
讲到「队列」，如果是 Golang 研发，不知道有没有联想到 Channel ？
Channel 本身就很类似队列，其收发操作均遵循了 FIFO（先进先出）的设计，具体规则如下：
- 先从 Channel 读取数据的 Goroutine 会先接收到数据
- 先向 Channel 发送数据的 Goroutine 会得到先发送数据的权利
如果熟悉队列这一数据类型，上手 Channel 会更快且准确~
以下截取自 Go语言设计与实现——Channel 数据结构
Go 语言的 Channel 在运行时使用 runtime.hchan 结构体表示。我们在 Go 语言中创建新的 Channel 时，实际上创建的都是如下所示的结构：
type hchan struct {
qcount uint
dataqsiz uint
buf unsafe.Pointer
elemsize uint16
closed uint32
elemtype *_type
sendx uint
recvx uint
recvq waitq
sendq waitq
lock mutex
}
runtime.hchan 结构体中的五个字段 qcount、dataqsiz、buf、sendx、recv 构建底层的 循环队列：
qcount— Channel 中的元素个数；dataqsiz— Channel 中的循环队列的长度；buf— Channel 的缓冲区数据指针；sendx— Channel 的发送操作处理到的位置；recvx— Channel 的接收操作处理到的位置；
除此之外，elemsize 和 elemtype 分别表示当前 Channel 能够收发的元素类型和大小；sendq 和 recvq 存储了当前 Channel 由于缓冲区空间不足而阻塞的 Goroutine 列表，这些等待队列使用双向链表 runtime.waitq 表示，链表中所有的元素都是 runtime.sudog 结构：
type waitq struct {
first *sudog
last *sudog
}
runtime.sudog 表示一个在等待列表中的 Goroutine，该结构中存储了两个分别指向前后 runtime.sudog 的指针以构成链表。
以下截取自 「Go 语言原本」中 Channel
Channel 主要有两种形式：
- 有缓存 Channel（buffered channel），使用
make(chan T, n)创建 - 无缓存 Channel（unbuffered channel），使用
make(chan T)创建
其中 T 为 Channel 传递数据的类型，n 为缓存的大小，这两种 Channel 的读写操作都非常简单：
他们之间的本质区别在于其内存模型的差异，这种内存模型在 Channel 上体现为：
- 有缓存 Channel:
ch <- v发生在v <- ch之前 - 有缓存 Channel:
close(ch)发生在v <- ch && v == isZero(v)之前 - 无缓存 Channel:
v <- ch发生在ch <- v之前 - 无缓存 Channel: 如果
len(ch) == C，则从 Channel 中收到第 k 个值发生在 k+C 个值得发送完成之前
直观上我们很好理解他们之间的差异：
- 对于有缓存 Channel 而言，内部有一个缓冲队列，数据会优先进入缓冲队列，而后才被消费， 即向通道发送数据
ch <- v发生在从通道接受数据v <- ch之前； - 对于无缓存 Channel 而言，内部没有缓冲队列，即向通道发送数据
ch <- v一旦出现， 通道接受数据v <- ch会立即执行， 因此从通道接受数据v <- ch发生在向通道发送数据ch <- v之前。
总结
队列（Queue）也是一种操作受限的线性表，只允许入队和出队，特性是 FIFO (First In, First Out, 先进先出)。
队列可以用数组实现顺序队列，也可以用链表实现链式队列。
在数组实现队列的时候，会产生数据搬移操作，要想解决数据搬移的问题，我们需要循环队列。你应该可以准确用代码实现 循环队列。
此外，提了几种广泛的队列应用，很多的并发实现底层都应用了队列，若想理解源码，要熟悉队列哦~ 🐶
阶段总结
数据结构 —— 线性表：数组、链表（上、下）、栈、队列 总算完成了 😂，效率略差
接下来会开始常见算法的总结（基于线性表），先定如下这些：
- 二分（查找）法
- 双指针
- 排序 —— 插入排序 & 冒泡排序
- 排序 —— 快速排序 & 归并排序
- LRU 缓存淘汰算法
- 递归