目录
为什么要有环形缓冲器
当有大量数据的时候，我们不能存储所有的数据，那么计算机处理数据的时候，只能先处理先来的，那么处理完后呢，就会把数据释放掉，再处理下一个。那么，已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队，
如果要将剩余的数据都往前移动一次，那么效率就会低下了
，肯定不现实，所以，环形队列就出现了。
频繁的内存分配不但增加了系统开销，更使得内存碎片不断增多，非常不利于我们的服务器长期稳定运行。也许我们可以使用内存池，比如SGI STL中附带的小内存分配器。但是对于这种按照严格的先进先出顺序处理的，块大小并不算小的，而且块大小也并不统一的内存分配情况来说，更多使用的是一种叫做环形缓冲区的方案。
简介
圆形缓冲区
（circular buffer），也称作
圆形队列
（circular queue），
循环缓冲区
（cyclic buffer），
环形缓冲区
（ring buffer），是一种用于表示一个
固定尺寸、头尾相连
的
缓冲区
的数据结构，适合缓存
数据流
。
环形缓冲区通常有
一个读指针和一个写指针
。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下，
环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针
。如果
仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性
。如果有
多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区
。
图1、图2和图3是一个环形缓冲区的运行示意图。图1是环形缓冲区的初始状态，可以看到读指针和写指针都指向第一个缓冲区处；图2是向环形缓冲区中添加了一个数据后的情况，可以看到写指针已经移动到数据块2的位置，而读指针没有移动；图3是环形缓冲区进行了读取和添加后的状态，可以看到环形缓冲区中已经添加了两个数据，已经读取了一个数据。
区分缓冲区是否为满的策略
缓冲区是满、或是空，都有可能出现读指针与写指针指向同一位置：
有多种策略用于检测缓冲区是满、或是空.
总是保持一个存储单元为空
缓冲区中总是有一个存储单元保持未使用状态。缓冲区最多存入（size – 1） 个数据。如果读写指针指向同一位置，则缓冲区为空。如果写指针位于读指针的相邻后一个位置，则缓冲区为满。这种策略的优点是简单、鲁棒；缺点是语义上实际可存数据量与缓冲区容量不一致，测试缓冲区是否满需要做取余数计算。
使用数据计数
这种策略不使用显式的写指针，而是保持着缓冲区内存储的数据的计数。因此测试缓冲区是空是满非常简单；对性能影响可以忽略。缺点是读写操作都需要修改这个存储数据计数，对于
多线程
访问缓冲区需要
并发控制
。
镜像指示位
缓冲区的长度如果是n，逻辑地址空间则为0至n-1；那么，规定n至2n-1为镜像逻辑地址空间。本策略规定读写指针的地址空间为0至2n-1，其中低半部分对应于常规的逻辑地址空间，高半部分对应于镜像逻辑地址空间。当指针值大于等于2n时，使其折返（wrapped）到ptr-2n。使用一位表示写指针或读指针是否进入了虚拟的镜像存储区：置位表示进入，不置位表示没进入还在基本存储区。
在读写指针的值相同情况下，如果二者的指示位相同，说明缓冲区为空；如果二者的指示位不同，说明缓冲区为满。这种方法优点是测试缓冲区满/空很简单；不需要做取余数操作；读写线程可以分别设计专用算法策略，能实现精致的并发控制。 缺点是读写指针各需要额外的一位作为指示位。
这种方法的逻辑是，如果写指针超出了读指针n位，在普通情况下，读写指针重合，但在这种情况下，写指针在镜像空间的读指针+n位，不和读指针重合
如果缓冲区长度是2的
幂
，则本方法可以省略镜像指示位。如果读写指针的值相等，则缓冲区为空；如果读写指针相差n，则缓冲区为满，这可以用条件表达式（写指针 == (读指针
异或
缓冲区长度)）来判断。
java实现
使用4个数字
队列的长度，元素的个数，读指针，写指针
如果队列已满，不能写入元素
如果队列为空，不能拿出元素
package datastructure.list.ringbuffer;
import java.util.Arrays;
public class RingBuffer {
/**
* ringBuffer的总长度，最大能够存储的成员数
*/
private int length;
/**
* ringBuffer内部存储的现有的成员数
*/
private int size;
/**
* 写指针,代表下一次操作执行的位置
*/
private int writePos;
/**
* 读指针,代表下一次操作执行的位置
*/
private int readPos;
/**
* 放置成员的循环数组，长度为length
*/
private Object[] list;
/**ringBuffer的构造函数<br>
* 初始化各种参数和object数组
* @param length ringBuffer的总长度，最大能够存储的成员数
*/
public RingBuffer(int length){
this.length=length;
list=new Object[length];
size=0;
writePos=0;
readPos=0;
}
/**显示ringBuffer已满，是否还能插入新的元素
* @return 如果数组已满，不能插入，返回true<br>如果能插入，返回false
*/
public boolean isFull(){
if(size==length){
return true;
}
return false;
}
/**显示ringBuffer是否为空，是否还能取出元素
* @return 如果数组为空，不能取出元素，返回true <br> 如果能取出，返回false
*/
public boolean isEmpty(){
if(size==0){
return true;
}
return false;
}
/**在ringBuffer中插入一个元素，在写指针处插入元素
* @param object 被插入的元素
* @return 如果成功插入，返回true<br> 如果队列已满，返回false
*/
public boolean put(Object object){
if(isFull()){
//如果队列已满
return false;
}
if(writePos==length-1){
//如果这次写入的位置在队列的最后一个元素
list[writePos]=object;
//那么下次写入的位置为0
writePos=0;
}
else{
//这次写入的位置不是队列最后一个元素，那么现在writePos处写入，然后++
list[writePos++]=object;
}
//ringBuffer中的成员数增加
//size的处理在最后操作，防止size增加了，读操作却没有读到
size++;
return true;
}
/**从ringBuffer中取出一个元素
* @return 如果队列为空，返回null <br> 否则，返回读指针对应的元素
*/
public Object take(){
if(isEmpty()){
return null;
}
Object result;
if(readPos==length-1){
//如果这次取出的位置在队列的最后一个元素
result=list[readPos];
//将对于位置的元素清空
list[readPos]=null;
readPos=0;
}
else{
result=list[readPos];
list[readPos++]=null;
}
size--;
return result;
}
public void printRingBuffer(){
System.out.println("开始打印环形缓冲区");
System.out.println("length=" + length + ", size=" + size + ", writePos=" + writePos + ", readPos=" + readPos);
for(int i=0;i<length;i++){
System.out.println("区域位置坐标:"+i+" :"+list[i]);
}
System.out.println("打印环形缓冲区结束");
System.out.println();
}
}
测试
package datastructure.list.ringbuffer;
public class Main {
public static void main(String[] args) {
RingBuffer ringBuffer=new RingBuffer(5);
ringBuffer.put("0");
ringBuffer.put("1");
ringBuffer.put("2");
ringBuffer.put("3");
ringBuffer.put("4");
ringBuffer.put("5");
ringBuffer.take();
ringBuffer.take();
ringBuffer.put("5");
ringBuffer.printRingBuffer();
ringBuffer.take();
ringBuffer.take();
ringBuffer.take();
ringBuffer.take();
ringBuffer.take();
ringBuffer.printRingBuffer();
ringBuffer.put("5");
ringBuffer.printRingBuffer();
}
}