环形队列
基础知识
环形队列是什么
- 数据是按照 “先进先出” 的原则进行操作
- 是环形的，即队列头部的上个元素是队列尾部
- 通常是容纳元素数固定的一个闭环
原理
内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。因此环列队列的是逻辑上将数组元素 q[0] 与 q[MAXN-1] 连接，形成一个存放队列的环形空间。
为了方便读写，还要用数组下标来指明队列的读写位置。
场景
- 环形队列主要应用在单线程读或者写
- 一般应用于需要高效且频繁进行多线程通信传递数据的场景，例如：linux捕包、发包等等
- 广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列
优点
保证元素是先进先出的
是由队列的性质保证的，在环形队列中通过对队列的顺序访问保证。
元素空间可以重复利用
因为一般的环形队列都是一个元素数固定的一个闭环，可以在环形队列初始化的时候分配好确定的内存空间，当进队或出队时只需要返回指定元素内存空间的地址即可，这些内存空间可以重复利用，避免频繁内存分配和释放的开销。
为多线程数据通信提供了一种高效的机制
在最典型的生产者消费者模型中，如果引入环形队列，那么生成者只需要生成“东西”然后放到环形队列中即可，而消费者只需要从环形队列里取“东西”并且消费即可，没有任何锁或者等待，巧妙的高效实现了多线程数据通信。
工作场景
实际环形队列在工作时有3种情况：
入队速度=出队速度
这是环形队列的常态，即入队速度和出队速度大致一样，即使某个突然时刻入队速度陡然变高或者出队速度陡然变低，都能通过队列这个缓冲区把这些数据先存起来，等到能处理的时候再处理。
入队速度>出队速度
在这种情况下，队列 写入速度 > 读取速度，想象当这种状态持续一段时间之后，队列中大多数全是写入但没读取的元素，当又一个新的元素产生时，可以把这个新元素 drop 掉或者放在另一个缓冲区保存起来，这种情况的出现不是个好事情，说明你需要对出队处理元素的算法或逻辑优化处理速度了。
入队速度<出队速度
在这种情况下，队列 读取速度 > 写入速度，这种情况说明程序出队处理元素的速度很快，这是比较好的情况，唯一不足的是读取队列的时候可能经常会轮询队列是否有新的元素，造成 cpu 占用过高。
无锁环形队列的实现
环形队列的存储结构
链表和线性表都是可以的，但几乎都用线性表实现，比链表快很多，原因也是显而易见的，因为访问链表需要挨个遍历。
读写index
有2个index很重要，一个是写入index，标示了当前可以写入元素的index，入队时使用。一个是读取index，标示了当前可以读取元素的index，出队时使用。
元素状态切换
有种很巧妙的方法，就是在队列中每个元素的头部加一个元素标示字段，标示这个元素是可读还是可写，而这个的关键就在于何时设置元素的可读可写状态，参照linux内核实现原理，当这个元素读取完之后，要设置可写状态，当这个元素写入完成之后，要设置可读状态。
实现
下面是 Ruby 的简单实现, 出队和入队的时候都没有考虑队列中的元素是否已满或是否存在。
class RingBuffer < Array
attr_reader :max_size
def initialize(max_size, enum = nil)
@max_size = max_size
enum.each { |e| self << e } if enum
end
def <<(el)
if self.size < @max_size || @max_size.nil?
super
else
self.shift
self.push(el)
end
end
alias :push :<<
end
