队列和循环队列（图解队列）

到队列，我们会在很多地方听到或者看到，那我们来看一下这位不太说话的老朋友，从栈很容易联想到队列的实现。

栈是先进后出的数据结构，队列而言它是先进先出。

对栈而言，在栈顶有一个指针即可。

队列是需要两个指针，一个在队头，一个在队尾。对应着入队操作和出队操作。

基于数组实现的是顺序队列，基于链表实现的是链式队列。

一个数组实现的顺序队列，在 入队了 AA 、BB 、CC 后，

队头指针 head=0，队尾指针 tail=3。如下图：

紧接着，又有两次出队，同样，对于出队head指针往后移动两个：

以上两个图对应的如队出队操作，也是很容易看出问题所在：

随着入队出队一波操作，tail指针很容易移动到最后的位置，表面上不能再入队了。

但是极有可能如图二一样，头指针head前面有大片空地。

怎么办?搬!我在出队之后，后面的数据往前挪，我们可以称之为移动补位。

但是每一次出队操作都去搬数据，时间复杂度想想就会很高 O(n)

怎么优化?

tail指针抵达末尾，同时head指针不在队头。也就是tail到了最后，且head前面有空。

此时触发数据搬移，过程如下：

人的思想不断进步，并且思考如何做得更加轻巧灵活。

我们会思考，可不可以不用搬移数据呢?

可以，接下来轮到循环队列登场了。。。。。。

循环队列，顾名思义。首尾相连形成环。哝，就是这个样子：

长得这么好看，一定要对得起我们对它的期望。

经过一番出队入队，头部索引=2，尾部指针指向最后一个位置，即将接受FF入队，

此时看上去又到了挪动数组的时候了?

环形的存在就是为了避免队列的数据搬移，我想你已经想到了它的灵巧之处。

对，就是将数据FF填充到索引=5处，tail指针移动到下一个，也就是索引=0处，就成了这样：

队列在平时工作时用的机会场景比较少，但是在一些偏底层系统中确实应用比较广泛。

比如：阻塞队列、并发队列

阻塞队列，就是在队空时，取数据会被直接拒绝。直到有数据才会允许被访问。

这种模型类似于 生产-消费关系，对的，这也是很多的消息队列的思想和应用。

这种阻塞队列可以协调生产和消费的关系。当然，也可以生产的i消息被多个消费。

这又产生了一个线程并发问题，我们如何保证线程安全呢?这就需要并发队列。

基于数组的循环队列 CAS原子操作，可以很好的实现无锁并发队列。

基于以上，微软给我们所提供的这些源码：

队列 Queue ;

泛型队列 Queue;

阻塞泛型集合 BlockingCollection

以及微软强大的并行库中的并发泛型队列 ConcurrentQueue

我们着重看一下泛型队列和并发泛型队列

队列 Queue 、泛型队列 Queue

我们直接看一下泛型版本的：

0、注释说明：这是一个基于数组实现的环形队列，也就是循环队列

1、初始定义

2、重要的私有变量

3、入队：分为两块主逻辑，一个是队满，一个是正常插入。

第0步已经注释说明这是一个循环队列，所以我们借此机会分析一下这个循环队列。

队满

1if (_size == _array.Length) 2倍扩容并且有最小装载量判断。

正常

_tail = (_tail 1) % _array.Length; 下面我们来看看这句话怎么来的。

对于非循环队列，头尾指针和数组的关系好确认。

而循环队列，因为是一个环，所以怎样定位移动后的指针位置才是关键的。

数组长度=6

当我入队FF，原来尾部指针=5，当前尾部指针=0;

接着入队GG, 原来尾部指针=0，当前尾部指针=1;

当我入队HH，原来尾部指针=1，当前尾部指针=2;

规律：当前指针 = (原来指针 1) % 数组长度

4、出队同3

ConcurrentQueue

注释说的很明白，这是一个无锁并发队列

我们在看源码之前先来了解一些定义

对于现在的多CPU、以及超线程概念的操作系统来说，CPU和内存之前存在处理速度上的差距，所以中间加了寄存器和高速缓存来缓冲。

多线程并发情况下，多核计算机，一个CPU读取的是在寄存器中的值，另一个CPU读取的是内存中的值，这就造成了数据不同步。

对于产生的并发问题，我们来看看并发队列对这些的处理。

我们先来理解接下代码中涉及到的名词：

1、易失结构 volatile : 告诉编译器和CLR不需要优化代码顺序，使得代码可控。不用将字段缓存到寄存器，缓存早内存中就行。

2、互锁结构 Interlocked : CAS保证原子性读取操作

3、自旋锁 ：原地打转，直到达到条件才离开。对于线程来讲，一直持有资源不撒手。

4、线程类提供了几个方法：

Thread.Sleep(0)：挂起自身，让出剩余的时间片，强迫系统调度其他同级或者更高级的线程。

Thread.Sleep(1)：强迫进行一次上下文切换

Thread.Ylied()：提前结束剩余的时间片，使得同级或者低级线程可能被调度。

Thread.SpinWait()：超线程CPU模式下，强迫自身暂停，允许CPU调度其他线程。

5、CAS理论：compare and swap 比较并交换。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

,