什么是環(huán)形隊列？

環(huán)形緩沖區(qū)是一個非常典型的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)符合生產(chǎn)者，消費者模型，可以理解它是一個水坑，生產(chǎn)者不斷的往里面灌水，消費者就不斷的從里面取出水。

那就可能會有人問，既然需要灌水，又需要取出水，為什么還需要開辟一個緩沖區(qū)內(nèi)存空間呢？直接把生產(chǎn)者水管的尾部接到消費者水管的頭部不就好了，這樣可以省空間啊。

答案是不行的，生產(chǎn)者生產(chǎn)水的速度是不知道的，消費者消費水的速度也是不知道的，如果你強制接在一起，因為生產(chǎn)和消費的速度不同，就非常可能存在水管爆炸的情況，你說這樣危險不危險？

在音頻系統(tǒng)框架下，alsa就是使用環(huán)形隊列的，在生產(chǎn)者和消費者速度不匹配的時候，就會出現(xiàn)xrun的問題。

環(huán)形隊列的特點

1、數(shù)組構(gòu)造環(huán)形緩沖區(qū)

假設(shè)我們用數(shù)組來構(gòu)造一個環(huán)形緩存區(qū)，如下圖

我們需要幾個東西來形容這個環(huán)形緩沖區(qū)，一個的讀位置，一個是寫位置，一個是環(huán)形緩沖區(qū)的長度

從圖片看，我們知道，這個環(huán)形緩沖區(qū)的讀寫位置是指向數(shù)組的首地址的，環(huán)形緩沖區(qū)的長度是 5 。

那如何判斷環(huán)形緩沖區(qū)為空呢？

如果 R == W 就是讀寫位置相同，則這個環(huán)形緩沖區(qū)為空

那如何判斷環(huán)形緩沖區(qū)滿了呢？

如果 （W - R ）= Len ，則這個環(huán)形緩沖區(qū)已經(jīng)滿了。

2、向環(huán)形緩沖區(qū)寫入 3個數(shù)據(jù)

寫入 3 個數(shù)據(jù)后，W 的值等于 3 了，R 還是等于 0。

3個企鵝已經(jīng)排列

3、從環(huán)形緩沖區(qū)讀取2個數(shù)據(jù)

讀出兩個數(shù)據(jù)后，R = 2 了，這個時候，W還是等于 3，畢竟沒有再寫過數(shù)據(jù)了。

4、再寫入3個數(shù)據(jù)

如果 W 》 LEN 后，怎么找到最開始的位置的呢？這個就需要進行運算了，W%LEN 的位置就是放入數(shù)據(jù)的位置 ，6%5 = 1。

5、再寫入1個數(shù)據(jù)

這個時候環(huán)形隊列已經(jīng)滿了，要是想再寫入數(shù)據(jù)的話，就不行了，（W - R） = 5 == LEN

代碼實現(xiàn)

/* 實現(xiàn)的最簡單的ringbuff 有更多提升空間，可以留言說明 */

#include “stdio.h”

#include “stdlib.h”

#define LEN 10

/*環(huán)形隊列結(jié)構(gòu)體*/

typedef struct ring_buff{

int array［LEN］;

int W;

int R;

}*ring;

/*環(huán)形隊列初始化*/

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;

}

/*判斷環(huán)形隊列是否已經(jīng)滿了*/

int get_ring_buff_fullstate（struct ring_buff * p_ring_buff）

{

/*如果寫位置減去讀位置等于隊列長度，就說明這個環(huán)形隊列已經(jīng)滿*/

if（（p_ring_buff-》W - p_ring_buff-》R） == LEN）

{

return （1）;

}

else

{

return （0）;

}

}

/*判斷環(huán)形隊列為空*/

int get_ring_buff_emptystate（struct ring_buff * p_ring_buff）

{

/*如果寫位置和讀的位置相等，就說明這個環(huán)形隊列為空*/

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

”）;

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）;

}

/*讀取環(huán)形隊列數(shù)據(jù)*/

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;

/*定義一個環(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））;

}

/*銷毀一個環(huán)形緩沖區(qū)*/

ring_buff_destory（pt_ring_buff）;

return （1）;

}

換一個寫法，這個寫法是各種大神級別的

/* 實現(xiàn)的最簡單的ringbuff 有更多提升空間，可以留言說明 */

#include “stdio.h”

#include “stdlib.h”

#define LEN 64

/*環(huán)形隊列結(jié)構(gòu)體*/

typedef struct ring_buff{

int array［LEN］;

int W;

int R;

}*ring;

/*環(huán)形隊列初始化*/

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;

}

/*判斷環(huán)形隊列是否已經(jīng)滿了*/

int get_ring_buff_fullstate（struct ring_buff * p_ring_buff）

{

/*如果寫位置減去讀位置等于隊列長度，就說明這個環(huán)形隊列已經(jīng)滿*/

if（（p_ring_buff-》W - p_ring_buff-》R） == LEN）

{

return （1）;

}

else

{

return （0）;

}

}

/*判斷環(huán)形隊列為空*/

int get_ring_buff_emptystate（struct ring_buff * p_ring_buff）

{

/*如果寫位置和讀的位置相等，就說明這個環(huán)形隊列為空*/

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

”）;

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）;

}

/*讀取環(huán)形隊列數(shù)據(jù)*/

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;

/*定義一個環(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））;

}

/*銷毀一個環(huán)形緩沖區(qū)*/

ring_buff_destory（pt_ring_buff）;

return （1）;

}

總結(jié)

環(huán)形隊列的使用場景非常多，安卓的音頻數(shù)據(jù)讀寫，很多都用到環(huán)形隊列，我們在開發(fā)過程中使用的環(huán)形隊列肯定比我上面的那個例子要復(fù)雜的多，我這里演示的是比較簡單的功能，但是麻雀雖小，五臟俱全，希望這個麻雀讓你們了解這個數(shù)據(jù)結(jié)構(gòu)。在實際項目中大展身手。

原文標題：C語言實現(xiàn)環(huán)形隊列的原理和方法

文章出處：【微信公眾號：strongerHuang】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責任編輯：haq