<p style="text-indent:2em;"> 什么是环形队列？</p> 讯享网
讯享网环形缓冲区是一个非常典型的数据结构，这种数据结构符合生产者，消费者模型，可以理解它是一个水坑，生产者不断的往里面灌水，消费者就不断的从里面取出水。</p> </p> 讯享网那就可能会有人问，既然需要灌水，又需要取出水，为什么还需要开辟一个缓冲区内存空间呢？直接把生产者水管的尾部接到消费者水管的头部不就好了，这样可以省空间啊。</p> </p> 讯享网答案是不行的，生产者生产水的速度是不知道的，消费者消费水的速度也是不知道的，如果你强制接在一起，因为生产和消费的速度不同，就非常可能存在水管爆炸的情况，你说这样危险不危险？</p> </p> 讯享网在音频系统框架下，alsa就是使用环形队列的，在生产者和消费者速度不匹配的时候，就会出现xrun的问题。</p> 环形队列的特点</p> 讯享网1、数组构造环形缓冲区</p> 假设我们用数组来构造一个环形缓存区，如下图</p> 讯享网<img src='https://file.elecfans.com/web1/M00/EE/DF/pIYBAGCaH1qADnHvAAABtcJl040728.png' alt='C语言' /></p> 我们需要几个东西来形容这个环形缓冲区，一个的读位置，一个是写位置，一个是环形缓冲区的长度</p> 讯享网<img src='https://file.elecfans.com/web1/M00/EE/DF/pIYBAGCaH1qAJFMaAAALl5qdz4c013.png' alt='C语言' /></p> 从图片看，我们知道，这个环形缓冲区的读写位置是指向数组的首地址的，环形缓冲区的长度是 5 。</p> 讯享网那如何判断环形缓冲区为空呢？</p> 如果 R == W 就是读写位置相同，则这个环形缓冲区为空</p> 讯享网那如何判断环形缓冲区满了呢？</p> 如果 （W - R ）= Len ，则这个环形缓冲区已经满了。</p> 讯享网2、向环形缓冲区写入 3个数据</p> </p> 讯享网写入 3 个数据后，W 的值等于 3 了，R 还是等于 0。</p> 3个企鹅已经排列</p> 讯享网3、从环形缓冲区读取2个数据</p> </p> 讯享网读出两个数据后，R = 2 了，这个时候，W还是等于 3，毕竟没有再写过数据了。</p> 4、再写入3个数据</p> 讯享网 </p> 如果 W 》 LEN 后，怎么找到最开始的位置的呢？这个就需要进行运算了，W%LEN 的位置就是放入数据的位置 ，6%5 = 1。</p> 讯享网5、再写入1个数据</p> </p> 讯享网这个时候环形队列已经满了，要是想再写入数据的话，就不行了，（W - R） = 5 == LEN</p> 代码实现</p> 讯享网/* 实现的最简单的ringbuff 有更多提升空间，可以留言说明 */</p> #include “stdio.h”</p> 讯享网#include “stdlib.h”</p> #define LEN 10</p> 讯享网/*环形队列结构体*/</p> typedef struct ring_buff{</p> 讯享网int array［LEN］;</p> int W;</p> 讯享网int R;</p> }*ring;</p> 讯享网/*环形队列初始化*/</p> struct ring_buff * fifo_init（void）</p> 讯享网{</p> struct ring_buff * p = NULL;</p> 讯享网p = （struct ring_buff *）malloc（sizeof（struct ring_buff））;</p> if（p == NULL）</p> 讯享网{</p> printf（“fifo_init malloc error</p> 讯享网”）;</p> return NULL;</p> 讯享网}</p> p-》W = 0;</p> 讯享网p-》R = 0;</p> return p;</p> 讯享网}</p> /*判断环形队列是否已经满了*/</p> 讯享网int get_ring_buff_fullstate（struct ring_buff * p_ring_buff）</p> {</p> 讯享网/*如果写位置减去读位置等于队列长度，就说明这个环形队列已经满*/</p> if（（p_ring_buff-》W - p_ring_buff-》R） == LEN）</p> 讯享网{</p> return （1）;</p> 讯享网}</p> else</p> 讯享网{</p> return （0）;</p> 讯享网}</p> }</p> 讯享网/*判断环形队列为空*/</p> int get_ring_buff_emptystate（struct ring_buff * p_ring_buff）</p> 讯享网{</p> /*如果写位置和读的位置相等，就说明这个环形队列为空*/</p> 讯享网if（p_ring_buff-》W == p_ring_buff-》R）</p> {</p> 讯享网return （1）;</p> }</p> 讯享网else</p> {</p> 讯享网return （0）;</p> }</p> 讯享网}</p> /*插入数据*/</p> 讯享网int ring_buff_insert（struct ring_buff * p_ring_buff，int data）</p> {</p> 讯享网if（p_ring_buff == NULL）</p> {</p> 讯享网printf（“p null</p> ”）;</p> 讯享网return （-1）;</p> }</p> 讯享网if（get_ring_buff_fullstate（p_ring_buff） == 1）</p> {</p> 讯享网printf（“buff is full</p> ”）;</p> 讯享网return （-2）;</p> }</p> 讯享网p_ring_buff-》array［p_ring_buff-》W%LEN］ = data;</p> p_ring_buff-》W ++;</p> 讯享网//printf（“inset：%d %d</p> ”，data，p_ring_buff-》W）;</p> 讯享网return （0）;</p> }</p> 讯享网/*读取环形队列数据*/</p> int ring_buff_get（struct ring_buff * p_ring_buff）</p> 讯享网{</p> int data = 0;</p> 讯享网if（p_ring_buff == NULL）</p> {</p> 讯享网printf（“p null</p> ”）;</p> 讯享网return （-1）;</p> }</p> 讯享网if（get_ring_buff_emptystate（p_ring_buff） == 1）</p> {</p> 讯享网printf（“buff is empty</p> ”）;</p> 讯享网return （-2）;</p> }</p> 讯享网data = p_ring_buff-》array［p_ring_buff-》R%LEN］;</p> p_ring_buff-》R++;</p> 讯享网return data;</p> }</p> 讯享网/*销毁*/</p> int ring_buff_destory（struct ring_buff * p_ring_buff）</p> 讯享网{</p> if（p_ring_buff == NULL）</p> 讯享网{</p> printf（“p null</p> 讯享网”）;</p> return （-1）;</p> 讯享网}</p> free（p_ring_buff）;</p> 讯享网return （0）;</p> }</p> 讯享网int main（）</p> {</p> 讯享网int i = 0;</p> /*定义一个环形缓冲区*/</p> 讯享网ring pt_ring_buff = fifo_init（）;</p> /*向环形缓冲区中写入数据*/</p> 
讯享网for（i = 0;i《10;i++）</p> {</p> 讯享网ring_buff_insert（pt_ring_buff，i）;</p> }</p> 讯享网/*从环形缓冲区中读出数据*/</p> for（i = 0;i《10;i++）</p> 讯享网{</p> printf（“%d ”，ring_buff_get（pt_ring_buff））;</p> 讯享网}</p> /*销毁一个环形缓冲区*/</p> 讯享网ring_buff_destory（pt_ring_buff）;</p> return （1）;</p> 讯享网}</p> <img src='https://file.elecfans.com/web1/M00/EE/DF/pIYBAGCaH1qAYSeiAAAPK8XswoA984.png' alt='C语言' /></p> 讯享网换一个写法，这个写法是各种大神级别的</p> /* 实现的最简单的ringbuff 有更多提升空间，可以留言说明 */</p> 讯享网#include “stdio.h”</p> #include “stdlib.h”</p> 讯享网#define LEN 64</p> /*环形队列结构体*/</p> 讯享网typedef struct ring_buff{</p> int array［LEN］;</p> 讯享网int W;</p> int R;</p> 讯享网}*ring;</p> /*环形队列初始化*/</p> 讯享网struct ring_buff * fifo_init（void）</p> {</p> 讯享网struct ring_buff * p = NULL;</p> p = （struct ring_buff *）malloc（sizeof（struct ring_buff））;</p> 讯享网if（p == NULL）</p> {</p> 讯享网printf（“fifo_init malloc error</p> ”）;</p> 讯享网return NULL;</p> }</p> 讯享网p-》W = 0;</p> p-》R = 0;</p> 讯享网return p;</p> }</p> 讯享网/*判断环形队列是否已经满了*/</p> int get_ring_buff_fullstate（struct ring_buff * p_ring_buff）</p> 讯享网{</p> /*如果写位置减去读位置等于队列长度，就说明这个环形队列已经满*/</p> 讯享网if（（p_ring_buff-》W - p_ring_buff-》R） == LEN）</p> {</p> 讯享网return （1）;</p> }</p> 讯享网else</p> {</p> 讯享网return （0）;</p> }</p> 讯享网}</p> /*判断环形队列为空*/</p> 讯享网int get_ring_buff_emptystate（struct ring_buff * p_ring_buff）</p> {</p> 讯享网/*如果写位置和读的位置相等，就说明这个环形队列为空*/</p> if（p_ring_buff-》W == p_ring_buff-》R）</p> 讯享网{</p> return （1）;</p> 讯享网}</p> else</p> 讯享网{</p> return （0）;</p> 讯享网}</p> }</p> 讯享网/*插入数据*/</p> int ring_buff_insert（struct ring_buff * p_ring_buff，int data）</p> 讯享网{</p> if（p_ring_buff == NULL）</p> 讯享网{</p> printf（“p null</p> 讯享网”）;</p> return （-1）;</p> 讯享网}</p> if（get_ring_buff_fullstate（p_ring_buff） == 1）</p> 讯享网{</p> printf（“buff is full</p> 讯享网”）;</p> return （-2）;</p> 讯享网}</p> //p_ring_buff-》array［p_ring_buff-》W%LEN］ = data;</p> 讯享网p_ring_buff-》array［p_ring_buff-》W&（LEN -1）］ = data;</p> p_ring_buff-》W ++;</p> 讯享网//printf（“inset：%d %d</p> ”，data，p_ring_buff-》W）;</p> 讯享网return （0）;</p> }</p> 讯享网/*读取环形队列数据*/</p> int ring_buff_get（struct ring_buff * p_ring_buff）</p> 讯享网{</p> int data = 0;</p> 讯享网if（p_ring_buff == NULL）</p> {</p> 讯享网printf（“p null</p> ”）;</p> 讯享网return （-1）;</p> }</p> 讯享网if（get_ring_buff_emptystate（p_ring_buff） == 1）</p> {</p> 讯享网printf（“buff is empty</p> ”）;</p> 讯享网return （-2）;</p> }</p> 讯享网//data = p_ring_buff-》array［p_ring_buff-》R%LEN］;</p> data = p_ring_buff-》array［p_ring_buff-》R&（LEN -1）］;</p> 讯享网p_ring_buff-》R++;</p> return data;</p> 讯享网}</p> /*销毁*/</p> 讯享网int ring_buff_destory（struct ring_buff * p_ring_buff）</p> {</p> 讯享网if（p_ring_buff == NULL）</p> {</p> 讯享网printf（“p null</p> ”）;</p> 讯享网return （-1）;</p> }</p> 讯享网free（p_ring_buff）;</p> return （0）;</p> 讯享网}</p> int main（）</p> 讯享网{</p> int i = 0;</p> 讯享网/*定义一个环形缓冲区*/</p> ring pt_ring_buff = fifo_init（）;</p> 讯享网/*向环形缓冲区中写入数据*/</p> for（i = 0;i《10;i++）</p> 讯享网{</p> ring_buff_insert（pt_ring_buff，i）;</p> 讯享网}</p> /*从环形缓冲区中读出数据*/</p> 讯享网for（i = 0;i《10;i++）</p> {</p> 讯享网printf（“%d ”，ring_buff_get（pt_ring_buff））;</p> }</p> 讯享网/*销毁一个环形缓冲区*/</p> ring_buff_destory（pt_ring_buff）;</p> 讯享网return （1）;</p> }</p> 讯享网总结</p> 环形队列的使用场景非常多，安卓的音频数据读写，很多都用到环形队列，我们在开发过程中使用的环形队列肯定比我上面的那个例子要复杂的多，我这里演示的是比较简单的功能，但是麻雀虽小，五脏俱全，希望这个麻雀让你们了解这个数据结构。在实际项目中大展身手。</p> 讯享网原文标题：C语言实现环形队列的原理和方法</p> 文章出处：【微信公众号：strongerHuang】欢迎添加关注！文章转载请注明出处。</p> 讯享网责任编辑：haq</p>
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/169376.html