C语言中怎么实现一个环形队列,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
环形缓冲区是一个非常典型的数据结构,这种数据结构符合生产者,消费者模型,可以理解它是一个水坑,生产者不断的往里面灌水,消费者就不断的从里面取出水。
那就可能会有人问,既然需要灌水,又需要取出水,为什么还需要开辟一个缓冲区内存空间呢?直接把生产者水管的尾部接到消费者水管的头部不就好了,这样可以省空间啊。
答案是不行的,生产者生产水的速度是不知道的,消费者消费水的速度也是不知道的,如果你强制接在一起,因为生产和消费的速度不同,就非常可能存在水管爆炸的情况,你说这样危险不危险?
假设我们用数组来构造一个环形缓存区,如下图
我们需要几个东西来形容这个环形缓冲区,一个的读位置,一个是写位置,一个是环形缓冲区的长度
从图片看,我们知道,这个环形缓冲区的读写位置是指向数组的首地址的,环形缓冲区的长度是 5 。
那如何判断环形缓冲区为空呢?
如果 R == W 就是读写位置相同,则这个环形缓冲区为空
那如何判断环形缓冲区满了呢?
如果 (W - R )= Len ,则这个环形缓冲区已经满了。
写入 3 个数据后,W 的值等于 3 了,R 还是等于 0。
3个企鹅已经排列
读出两个数据后,R = 2 了,这个时候,W还是等于 3,毕竟没有再写过数据了。
如果 W > LEN 后,怎么找到最开始的位置的呢?这个就需要进行运算了,W%LEN 的位置就是放入数据的位置 ,6%5 = 1。
这个时候环形队列已经满了,要是想再写入数据的话,就不行了,(W - R) = 5 == LEN
/* 实现的最简单的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\n");
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\n");
return (-1);
}
if(get_ring_buff_fullstate(p_ring_buff) == 1)
{
printf("buff is full\n");
return (-2);
}
p_ring_buff->array[p_ring_buff->W%LEN] = data;
p_ring_buff->W ++;
//printf("inset:%d %d\n",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\n");
return (-1);
}
if(get_ring_buff_emptystate(p_ring_buff) == 1)
{
printf("buff is empty\n");
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\n");
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);
}
换一个写法,这个写法是各种大神级别的
/* 实现的最简单的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\n");
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\n");
return (-1);
}
if(get_ring_buff_fullstate(p_ring_buff) == 1)
{
printf("buff is full\n");
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\n",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\n");
return (-1);
}
if(get_ring_buff_emptystate(p_ring_buff) == 1)
{
printf("buff is empty\n");
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\n");
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);
}
看完上述内容,你们掌握C语言中怎么实现一个环形队列的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。