2025年环形队列是一种什么结构（环形队列是一种什么结构类型）

大家好，我是讯享网，很高兴认识大家。

 <p> <strong>一、什么是<u>环形</u>队列？</strong></p>

讯享网

讯享网环形缓冲区是一个非常典型的数据结构，这种数据结构符合生产者，消费者模型，可以理解它是一个水坑，生产者不断的往里面灌水，消费者就不断的从里面取出水。</p>

  那就可能会有人问，既然需要灌水，又需要取出水，为什么还需要开辟一个缓冲区内存空间呢？<strong>直接把生产者水管的尾部接到消费者水管的头部不就好了，这样可以省空间啊。</strong></p>

讯享网<strong>答案是不行的，</strong>生产者生产水的速度是不知道的，消费者消费水的速度也是不知道的，如果你强制接在一起，因为生产和消费的速度不同，就非常可能存在水管爆炸的情况，你说这样危险不危险？</p>

在<u>音频</u>系统框架下，alsa就是使用环形队列的，在生产者和消费者速度不匹配的时候，就会出现xrun的问题。</p>

讯享网<strong>二、环形队列的特点</strong></p>

<strong>1、数组构造环形缓冲区</strong></p>

讯享网假设我们用数组来构造一个环形缓存区，如下图所示：</p>

<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbqAHmc3AAABtcJl040283.png" alt="1fa557a0-34ba-11ee-9e74-dacad0.png" /></p>

讯享网我们需要几个东西来形容这个环形缓冲区，一个的读位置，一个是写位置，一个是环形缓冲区的长度。</p>

<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbqAaq5fAAALl5qdz4c555.png" alt="1fb3b796-34ba-11ee-9e74-dacad0.png" /></p>

讯享网从图片看，我们知道，这个环形缓冲区的读写位置是指向数组的首地址的，环形缓冲区的长度是 5 。</p>

那如何判断环形缓冲区为空呢？</p>

讯享网如果 R == W  就是读写位置相同，则这个环形缓冲区为空</p>

那如何判断环形缓冲区满了呢？</p>

讯享网如果 （W - R ）= Len ，则这个环形缓冲区已经满了。</p>

<strong>2、向环形缓冲区写入3个数据</strong></p>

讯享网<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbuAbGXoAABL4OLb_qY904.png" alt="1fc798ce-34ba-11ee-9e74-dacad0.png" /></p>

写入 3 个数据后，W 的值等于 3 了，R 还是等于 0。</p>

讯享网3个企鹅已经排列~</p>

<strong>3、从环形缓冲区读取2个数据</strong></p>

讯享网<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbuAT-1_AAAypogR3u8718.png" alt="1fd0a72a-34ba-11ee-9e74-dacad0.png" /></p>

读出两个数据后，R = 2 了，这个时候，W还是等于 3，毕竟没有再写过数据了。</p>

讯享网<strong>4、再写入3个数据</strong></p>

<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbuAC4OVAABV-wc4UvU855.png" alt="1fea1494-34ba-11ee-9e74-dacad0.png" /></p>

讯享网如果 W > LEN 后，怎么找到最开始的位置的呢？这个就需要进行运算了，W%LEN 的位置就是放入数据的位置 ，6%5 = 1。</p>

<strong>5、再写入1个数据</strong></p>

讯享网<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbuAROhnAABcvX1Ht_g913.png" alt="20096ed4-34ba-11ee-9e74-dacad0.png" /></p>

这个时候环形队列已经满了，要是想再写入数据的话，就不行了，<strong>(W - R) = 5 == LEN</strong></p>

讯享网<strong>三、代码实现</strong></p>

 </p>

讯享网 /* 实现的最简单的ringbuff 有更多提升空间，可以留言说明 */ #include “stdio.h” #include “stdlib.h” #define LEN 10 /环形队列结构体/ typedef struct ring_buff{ int array[LEN]; int W; int R; }*ring; /环形队列初始化/ struct ring_buff * fifo_init(void) { struct ring_buff * p = NULL; p = (struct ring_buff *)malloc(sizeof(struct ring_buff)); if(p == NULL) {   printf(“fifo_init malloc error “);   return NULL; } p->W = 0; p->R = 0; return p; } /判断环形队列是否已经满了/ int get_ring_buff_fullstate(struct ring_buff * p_ring_buff) { /如果写位置减去读位置等于队列长度，就说明这个环形队列已经满/ if((p_ring_buff->W - p_ring_buff->R) == LEN) { return (1); } else { return (0); } } /判断环形队列为空/ int get_ring_buff_emptystate(struct ring_buff * p_ring_buff) { /如果写位置和读的位置相等，就说明这个环形队列为空/ if(p_ring_buff->W == p_ring_buff->R) { return (1); } else { return (0); } } /插入数据/ int ring_buff_insert(struct ring_buff * p_ring_buff,int data) { if(p_ring_buff == NULL) {   printf(“p null “);   return (-1); } if(get_ring_buff_fullstate(p_ring_buff) == 1) { printf(“buff is full “); return (-2); } p_ring_buff->array[p_ring_buff->W%LEN] = data; p_ring_buff->W ++; //printf(“inset:%d %d “,data,p_ring_buff->W); return (0); } /读取环形队列数据/ int ring_buff_get(struct ring_buff * p_ring_buff) { int data = 0;
讯享网 if(p_ring_buff == NULL) {   printf(“p null “);   return (-1); } if(get_ring_buff_emptystate(p_ring_buff) == 1) { printf(“buff is empty “); return (-2); } data = p_ring_buff->array[p_ring_buff->R%LEN]; p_ring_buff->R++; return data; } /销毁/ int ring_buff_destory(struct ring_buff * p_ring_buff) { if(p_ring_buff == NULL) {   printf(“p null “);   return (-1); } free(p_ring_buff); return (0); } int main() { int i = 0; /定义一个环形缓冲区/ ring pt_ring_buff = fifo_init(); /向环形缓冲区中写入数据/ for(i = 0;i<10;i++) { ring_buff_insert(pt_ring_buff,i); } /从环形缓冲区中读出数据/ for(i = 0;i<10;i++) { printf(”%d “,ring_buff_get(pt_ring_buff)); } /销毁一个环形缓冲区/ ring_buff_destory(pt_ring_buff); return (1); }

 </p>

讯享网<img src="https://file1.elecfans.com//web2/M00/9F/A1/wKgZomToPbuAFVewAAAPK8XswoA352.png" alt="201ab4b4-34ba-11ee-9e74-dacad0.png" /></p>

换一个写法，这个写法是各种大神级别的：</p>

讯享网 </p>

 /* 实现的最简单的ringbuff 有更多提升空间，可以留言说明 */ #include “stdio.h” #include “stdlib.h” #define LEN 64 /环形队列结构体/ typedef struct ring_buff{ int array[LEN]; int W; int R; }*ring; /环形队列初始化/ struct ring_buff * fifo_init(void) { struct ring_buff * p = NULL; p = (struct ring_buff *)malloc(sizeof(struct ring_buff)); if(p == NULL) {   printf(“fifo_init malloc error “);   return NULL; } p->W = 0; p->R = 0; return p; } /判断环形队列是否已经满了/ int get_ring_buff_fullstate(struct ring_buff * p_ring_buff) { /如果写位置减去读位置等于队列长度，就说明这个环形队列已经满/ if((p_ring_buff->W - p_ring_buff->R) == LEN) { return (1); } else { return (0); } } /判断环形队列为空/ int get_ring_buff_emptystate(struct ring_buff * p_ring_buff) { /如果写位置和读的位置相等，就说明这个环形队列为空/ if(p_ring_buff->W == p_ring_buff->R) { return (1); } else { return (0); } } /插入数据/ int ring_buff_insert(struct ring_buff * p_ring_buff,int data) { if(p_ring_buff == NULL) {   printf(“p null “);   return (-1); } if(get_ring_buff_fullstate(p_ring_buff) == 1) { printf(“buff is full “); return (-2); } //p_ring_buff->array[p_ring_buff->W%LEN] = data; p_ring_buff->array[p_ring_buff->W&(LEN -1)] = data; p_ring_buff->W ++; //printf(“inset:%d %d “,data,p_ring_buff->W); return (0); } /读取环形队列数据/ int ring_buff_get(struct ring_buff * p_ring_buff) { int data = 0; if(p_ring_buff == NULL) {   printf(“p null “);   return (-1); } if(get_ring_buff_emptystate(p_ring_buff) == 1) { printf(“buff is empty “); return (-2); } //data = p_ring_buff->array[p_ring_buff->R%LEN]; data = p_ring_buff->array[p_ring_buff->R&(LEN -1)]; p_ring_buff->R++; return data; } /销毁/ int ring_buff_destory(struct ring_buff * p_ring_buff) { if(p_ring_buff == NULL) {   printf(“p null “);   return (-1); } free(p_ring_buff); return (0); } int main() { int i = 0; /定义一个环形缓冲区/ ring pt_ring_buff = fifo_init(); /向环形缓冲区中写入数据/ for(i = 0;i<10;i++) { ring_buff_insert(pt_ring_buff,i); } /从环形缓冲区中读出数据/ for(i = 0;i<10;i++) { printf(”%d “,ring_buff_get(pt_ring_buff)); } /销毁一个环形缓冲区/ ring_buff_destory(pt_ring_buff); return (1); }

讯享网 </p>

<strong>四、总结</strong></p>

讯享网环形队列的使用场景非常多，安卓的音频数据读写，很多都用到环形队列，我们在开发过程中使用的环形队列肯定比我上面的那个例子要复杂的多，我这里演示的是比较简单的功能，<strong>但麻雀虽小，五脏俱全</strong>，希望这个麻雀让你们了解这个数据结构，在实际项目中大展身手。<br />  </p>

　　审核编辑：汤梓红</div>

讯享网 </div>

2025年环形队列是一种什么结构（环形队列是一种什么结构类型）

相关推荐