环形队列 - gmtalang/test GitHub Wiki

• ## 普通队列

• • 普通队列一般由数组构成。都是先进先出，队列中容量有限制。但是主要不同是在处理方式上。
• • 第一种处理方式：计算机由队头开始处理，前面的处理完，后面的数据移到前面继续处理。这样很明显效率很慢
• • 第二种处理方式：计算机从队头开始处理，前面的处理完后，计算机移到下一个单元处理 。这样的话，前面的存储单元用完后就空着，要知道队列容量是* 有限的，这样便造成了队列的空间浪费。

• ## * 环形队列

• 环形队列能够很好的解决这个问题，它有如下特点。它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。因为有简单高效的原因，甚至在硬件都实现了环形队列。环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列。

• 环形队列原理：内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个* 的转回是通过取模操作来执行的。 因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。

• ## * * 为多线程数据通信提供了一种高效的机制

• 在最典型的生产者消费者模型中，如果引入环形队列，那么生成者只需要生成“东西”然后放到环形队列中即可，而消费者只需要从环形队列里取“东* * 西”并且消费即可，没有任何锁或者等待，巧妙的高效实现了多线程数据通信。

## * 环形队列的工作场景

• 一般应用于需要高效且频繁进行多线程通信传递数据的场景，例如：linux捕包、发包等等，（linux系统中对PACKET_RX_RING和PACKET_TX_RING的支持实质就是内核实现的一种环形队列）