您现在的位置是:首页 > 正文

C语言,环形队列

2024-01-30 23:50:11阅读 0

什么是环形队列?

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

640?wx_fmt=png

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

640?wx_fmt=png

答案是不行的,生产者生产水的速度是不知道的,消费者消费水的速度也是不知道的,如果你强制接在一起,因为生产和消费的速度不同,就非常可能存在水管爆炸的情况,你说这样危险不危险?

640?wx_fmt=png

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

环形队列的特点

1、数组构造环形缓冲区

假设我们用数组来构造一个环形缓存区,如下图

640?wx_fmt=png

我们需要几个东西来形容这个环形缓冲区,一个的读位置,一个是写位置,一个是环形缓冲区的长度

640?wx_fmt=png

从图片看,我们知道,这个环形缓冲区的读写位置是指向数组的首地址的,环形缓冲区的长度是 5 。

那如何判断环形缓冲区为空呢?

如果 R == W  就是读写位置相同,则这个环形缓冲区为空

那如何判断环形缓冲区满了呢?

如果 (W - R )= Len ,则这个环形缓冲区已经满了。

2、向环形缓冲区写入 3个数据

640?wx_fmt=png

写入 3 个数据后,W 的值等于 3 了,R 还是等于 0。

3个企鹅已经排列

3、从环形缓冲区读取2个数据

640?wx_fmt=png

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

4、再写入3个数据

640?wx_fmt=png

如果 W > LEN 后,怎么找到最开始的位置的呢?这个就需要进行运算了,W%LEN 的位置就是放入数据的位置 ,6%5 = 1。

5、再写入1个数据

640?wx_fmt=png

这个时候环形队列已经满了,要是想再写入数据的话,就不行了,(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);
}

640?wx_fmt=png

换一个写法,这个写法是各种大神级别的


/* 实现的最简单的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);
}

总结

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

—————END—————

640?wx_fmt=jpeg
扫码或长按关注
回复「  加群  」进入技术群聊

网站文章

  • 软件测试 理念 价值,软件测试价值观-SMBT新理念

    2、Most bug:最多Bug量变到质变是事物的变化规律,测试也如此,只有Bug的量上去了,产品的质量才能有所改观,如果Bug在数量上上不去,这对测试活动有信心谈何容易,一旦遇到这种情况测试经理们就...

    2024-01-30 23:50:01
  • ESP32开发:Clion配置IDF

    ESP32开发:Clion配置IDF

    可以通过安装包进行安装,如下图:下载链接如下:https://dl.espressif.cn/dl/esp-idf/?idf=4.4安装好后,IDF会添加环境变量IDF_TOOLS_PATH,如果要安...

    2024-01-30 23:49:53
  • idea连接数据库出错

    idea连接数据库出错

    解决Server returns invalid timezone. Go to ‘Advanced’ tab and set ‘serverTimezone’ property manually. serverTimezone 改为CST

    2024-01-30 23:49:24
  • STM32CubeMX+FreeRTOS实验---使用os timer

    STM32CubeMX+FreeRTOS实验---使用os timer

    在STM32CubeMX的FreeRTOS配置中,使能FreeRTOS的Software Timer功能 修改timer的名称及callback名称等 可以看到,在生成工程的main.c文件的main函数中,有以下code /* Create the timer(s) */ /* definition and creation of myTimer01 */ osTime

    2024-01-30 23:49:10
  • NC添加客户端远程监听 agentlib:jdwp=transport=dt_socket,suspend=n,server=y,address=30.12.130.134:8777

    NC添加客户端远程监听 agentlib:jdwp=transport=dt_socket,suspend=n,server=y,address=30.12.130.134:8777

    NC添加客户端远程监听 agentlib:jdwp=transport=dt_socket,suspend=n,server=y,address=30.12.130.134:8777

    2024-01-30 23:48:41
  • kubernetes学习笔记-dashboard

    kubernetes学习笔记-dashboard

    2024-01-30 23:48:32
  • Jmeter性能压测 —— 高并发思路

    Jmeter性能压测 —— 高并发思路

    条件:接口响应时间 性能指标 -- 推导 --只需要1台与服务器相同配置的机器能完成5000/s并发量即可(类似数学中的同理可得,以此类推)

    2024-01-30 23:48:25
  • BSDragView

    BSDragView一个实现了任意位置拖动的view支持左右粘边,上下粘边效果效果gitHub地址:github.com/FreeBaiShun…用法新创建一个自定义的view继承与BSDragView直接使用这个自定义view即可支持任意位置拖动功能//1. 自定义view@interface MyView : BSDragView@end//2. 使用这个v...

    2024-01-30 23:48:19
  • lodash入门

    简介Lodash是一个著名的javascript原生库,不需要引入其他第三方依赖。是一个意在提高开发者效率,提高JS原生方法性能的JS库。简单的说就是,很多方法lodash已经帮你写好了,直接调用就行,不用自己费尽心思去写了,而且可以统一方法的一致性。Lodash使用了一个简单的 _ 符号,就像Jquery的 $ 一样,十分简洁。类似的还有Underscore.js和Lazy.js支持ch...

    2024-01-30 23:47:50
  • 七大统计模型

    七大统计模型

    一、多元回归 1、概述: 在研究变量之间的相互影响关系模型时候,用到这类方法,具体地说:其可以定量地描述某一现象和某些因素之间的函数关系,将各变量的已知值带入回归方程可以求出因变量的估计值,从而可以进行预测等相关研究。  2、分类  分为两类:多元线性回归和非线性线性回归;其中非线性回归可以通过一定的变化转化为线性回归,比如:y=lnx 可以转化为y=u    u=ln...

    2024-01-30 23:47:44