C語言,環(huán)形隊(duì)列
時(shí)間:2021-08-19 15:23:48
手機(jī)看文章
掃描二維碼
隨時(shí)隨地手機(jī)看文章
[導(dǎo)讀]什么是環(huán)形隊(duì)列?環(huán)形緩沖區(qū)是一個(gè)非常典型的數(shù)據(jù)結(jié)構(gòu),這種數(shù)據(jù)結(jié)構(gòu)符合生產(chǎn)者,消費(fèi)者模型,可以理解它是一個(gè)水坑,生產(chǎn)者不斷的往里面灌水,消費(fèi)者就不斷的從里面取出水。那就可能會(huì)有人問,既然需要灌水,又需要取出水,為什么還需要開辟一個(gè)緩沖區(qū)內(nèi)存空間呢?直接把生產(chǎn)者水管的尾部接到消費(fèi)者水...
什么是環(huán)形隊(duì)列?
環(huán)形緩沖區(qū)是一個(gè)非常典型的數(shù)據(jù)結(jié)構(gòu),這種數(shù)據(jù)結(jié)構(gòu)符合生產(chǎn)者,消費(fèi)者模型,可以理解它是一個(gè)水坑,生產(chǎn)者不斷的往里面灌水,消費(fèi)者就不斷的從里面取出水。那就可能會(huì)有人問,既然需要灌水,又需要取出水,為什么還需要開辟一個(gè)緩沖區(qū)內(nèi)存空間呢?直接把生產(chǎn)者水管的尾部接到消費(fèi)者水管的頭部不就好了,這樣可以省空間啊。
答案是不行的,生產(chǎn)者生產(chǎn)水的速度是不知道的,消費(fèi)者消費(fèi)水的速度也是不知道的,如果你強(qiáng)制接在一起,因?yàn)樯a(chǎn)和消費(fèi)的速度不同,就非??赡艽嬖谒鼙ǖ那闆r,你說這樣危險(xiǎn)不危險(xiǎn)?
在音頻系統(tǒng)框架下,alsa就是使用環(huán)形隊(duì)列的,在生產(chǎn)者和消費(fèi)者速度不匹配的時(shí)候,就會(huì)出現(xiàn)xrun的問題。
環(huán)形隊(duì)列的特點(diǎn)
1、數(shù)組構(gòu)造環(huán)形緩沖區(qū)
假設(shè)我們用數(shù)組來構(gòu)造一個(gè)環(huán)形緩存區(qū),如下圖我們需要幾個(gè)東西來形容這個(gè)環(huán)形緩沖區(qū),一個(gè)的讀位置,一個(gè)是寫位置,一個(gè)是環(huán)形緩沖區(qū)的長度從圖片看,我們知道,這個(gè)環(huán)形緩沖區(qū)的讀寫位置是指向數(shù)組的首地址的,環(huán)形緩沖區(qū)的長度是 5 。
那如何判斷環(huán)形緩沖區(qū)為空呢?如果 R == W ?就是讀寫位置相同,則這個(gè)環(huán)形緩沖區(qū)為空那如何判斷環(huán)形緩沖區(qū)滿了呢?如果 (W - R )= Len ,則這個(gè)環(huán)形緩沖區(qū)已經(jīng)滿了。
2、向環(huán)形緩沖區(qū)寫入 3個(gè)數(shù)據(jù)
寫入 3 個(gè)數(shù)據(jù)后,W 的值等于 3 了,R 還是等于 0。3個(gè)企鵝已經(jīng)排列3、從環(huán)形緩沖區(qū)讀取2個(gè)數(shù)據(jù)
讀出兩個(gè)數(shù)據(jù)后,R = 2 了,這個(gè)時(shí)候,W還是等于 3,畢竟沒有再寫過數(shù)據(jù)了。4、再寫入3個(gè)數(shù)據(jù)
如果 W > LEN 后,怎么找到最開始的位置的呢?這個(gè)就需要進(jìn)行運(yùn)算了,W%LEN 的位置就是放入數(shù)據(jù)的位置 ,6%5 = 1。5、再寫入1個(gè)數(shù)據(jù)
這個(gè)時(shí)候環(huán)形隊(duì)列已經(jīng)滿了,要是想再寫入數(shù)據(jù)的話,就不行了,(W - R) = 5 == LEN代碼實(shí)現(xiàn)
/* 實(shí)現(xiàn)的最簡單的ringbuff 有更多提升空間,可以留言說明 */
#include "stdio.h"
#include "stdlib.h"
#define LEN 10
/*環(huán)形隊(duì)列結(jié)構(gòu)體*/
typedef struct ring_buff{
int array[LEN];
int W;
int R;
}*ring;
/*環(huán)形隊(duì)列初始化*/
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;
}
/*判斷環(huán)形隊(duì)列是否已經(jīng)滿了*/
int get_ring_buff_fullstate(struct ring_buff * p_ring_buff)
{
/*如果寫位置減去讀位置等于隊(duì)列長度,就說明這個(gè)環(huán)形隊(duì)列已經(jīng)滿*/
if((p_ring_buff->W - p_ring_buff->R) == LEN)
{
return (1);
}
else
{
return (0);
}
}
/*判斷環(huán)形隊(duì)列為空*/
int get_ring_buff_emptystate(struct ring_buff * p_ring_buff)
{
/*如果寫位置和讀的位置相等,就說明這個(gè)環(huán)形隊(duì)列為空*/
if(p_ring_buff->W == p_ring_buff->R)
{
return (1);
}
else
{
return (0);
}
}
/*插入數(shù)據(jù)*/
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);
}
/*讀取環(huán)形隊(duì)列數(shù)據(jù)*/
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;
/*定義一個(gè)環(huán)形緩沖區(qū)*/
ring pt_ring_buff = fifo_init();
/*向環(huán)形緩沖區(qū)中寫入數(shù)據(jù)*/
for(i = 0;i<10;i )
{
ring_buff_insert(pt_ring_buff,i);
}
/*從環(huán)形緩沖區(qū)中讀出數(shù)據(jù)*/
for(i = 0;i<10;i )
{
printf("%d ",ring_buff_get(pt_ring_buff));
}
/*銷毀一個(gè)環(huán)形緩沖區(qū)*/
ring_buff_destory(pt_ring_buff);
return (1);
}
換一個(gè)寫法,這個(gè)寫法是各種大神級(jí)別的
/* 實(shí)現(xiàn)的最簡單的ringbuff 有更多提升空間,可以留言說明 */
#include "stdio.h"
#include "stdlib.h"
#define LEN 64
/*環(huán)形隊(duì)列結(jié)構(gòu)體*/
typedef struct ring_buff{
int array[LEN];
int W;
int R;
}*ring;
/*環(huán)形隊(duì)列初始化*/
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;
}
/*判斷環(huán)形隊(duì)列是否已經(jīng)滿了*/
int get_ring_buff_fullstate(struct ring_buff * p_ring_buff)
{
/*如果寫位置減去讀位置等于隊(duì)列長度,就說明這個(gè)環(huán)形隊(duì)列已經(jīng)滿*/
if((p_ring_buff->W - p_ring_buff->R) == LEN)
{
return (1);
}
else
{
return (0);
}
}
/*判斷環(huán)形隊(duì)列為空*/
int get_ring_buff_emptystate(struct ring_buff * p_ring_buff)
{
/*如果寫位置和讀的位置相等,就說明這個(gè)環(huán)形隊(duì)列為空*/
if(p_ring_buff->W == p_ring_buff->R)
{
return (1);
}
else
{
return (0);
}
}
/*插入數(shù)據(jù)*/
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