C語(yǔ)言環(huán)形隊(duì)列的原理和特點(diǎn)
什么是環(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ì)有人問(wèn)，既然需要灌水，又需要取出水，為什么還需要開(kāi)辟一個(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，你說(shuō)這樣危險(xiǎn)不危險(xiǎn)？
在音頻系統(tǒng)框架下，alsa就是使用環(huán)形隊(duì)列的，在生產(chǎn)者和消費(fèi)者速度不匹配的時(shí)候，就會(huì)出現(xiàn)xrun的問(wèn)題。
環(huán)形隊(duì)列的特點(diǎn)
1、數(shù)組構(gòu)造環(huán)形緩沖區(qū)
假設(shè)我們用數(shù)組來(lái)構(gòu)造一個(gè)環(huán)形緩存區(qū)，如下圖
我們需要幾個(gè)東西來(lái)形容這個(gè)環(huán)形緩沖區(qū)，一個(gè)的讀位置，一個(gè)是寫(xiě)位置，一個(gè)是環(huán)形緩沖區(qū)的長(zhǎng)度
從圖片看，我們知道，這個(gè)環(huán)形緩沖區(qū)的讀寫(xiě)位置是指向數(shù)組的首地址的，環(huán)形緩沖區(qū)的長(zhǎng)度是 5 。
那如何判斷環(huán)形緩沖區(qū)為空呢？
如果 R == W 就是讀寫(xiě)位置相同，則這個(gè)環(huán)形緩沖區(qū)為空
那如何判斷環(huán)形緩沖區(qū)滿(mǎn)了呢？
如果 （W - R ）= Len ，則這個(gè)環(huán)形緩沖區(qū)已經(jīng)滿(mǎn)了。
2、向環(huán)形緩沖區(qū)寫(xiě)入 3個(gè)數(shù)據(jù)
寫(xiě)入 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，畢竟沒(méi)有再寫(xiě)過(guò)數(shù)據(jù)了。
4、再寫(xiě)入3個(gè)數(shù)據(jù)
如果 W 》 LEN 后，怎么找到最開(kāi)始的位置的呢？這個(gè)就需要進(jìn)行運(yùn)算了，W%LEN 的位置就是放入數(shù)據(jù)的位置 ，6%5 = 1。
5、再寫(xiě)入1個(gè)數(shù)據(jù)
這個(gè)時(shí)候環(huán)形隊(duì)列已經(jīng)滿(mǎn)了，要是想再寫(xiě)入數(shù)據(jù)的話(huà)，就不行了，（W - R） = 5 == LEN
代碼實(shí)現(xiàn)
/* 實(shí)現(xiàn)的最簡(jiǎn)單的ringbuff 有更多提升空間，可以留言說(shuō)明 */
#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
”）;
return NULL;
}
p-》W = 0;
p-》R = 0;
return p;
}
/*判斷環(huán)形隊(duì)列是否已經(jīng)滿(mǎn)了*/
int get_ring_buff_fullstate（struct ring_buff * p_ring_buff）
{
/*如果寫(xiě)位置減去讀位置等于隊(duì)列長(zhǎng)度，就說(shuō)明這個(gè)環(huán)形隊(duì)列已經(jīng)滿(mǎn)*/
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）
{
/*如果寫(xiě)位置和讀的位置相等，就說(shuō)明這個(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
”）;
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)形隊(duì)列數(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;
}
/*銷(xiāo)毀*/
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;
/*定義一個(gè)環(huán)形緩沖區(qū)*/
ring pt_ring_buff = fifo_init（）;
/*向環(huán)形緩沖區(qū)中寫(xiě)入數(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））;
}
/*銷(xiāo)毀一個(gè)環(huán)形緩沖區(qū)*/
ring_buff_destory（pt_ring_buff）;
return （1）;
}
換一個(gè)寫(xiě)法，這個(gè)寫(xiě)法是各種大神級(jí)別的
/* 實(shí)現(xiàn)的最簡(jiǎn)單的ringbuff 有更多提升空間，可以留言說(shuō)明 */
#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
”）;
return NULL;
}
p-》W = 0;
p-》R = 0;
return p;
}
/*判斷環(huán)形隊(duì)列是否已經(jīng)滿(mǎn)了*/
int get_ring_buff_fullstate（struct ring_buff * p_ring_buff）
{
/*如果寫(xiě)位置減去讀位置等于隊(duì)列長(zhǎng)度，就說(shuō)明這個(gè)環(huán)形隊(duì)列已經(jīng)滿(mǎn)*/
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）
{
/*如果寫(xiě)位置和讀的位置相等，就說(shuō)明這個(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
”）;
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)形隊(duì)列數(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;
}
/*銷(xiāo)毀*/
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;
/*定義一個(gè)環(huán)形緩沖區(qū)*/
ring pt_ring_buff = fifo_init（）;
/*向環(huán)形緩沖區(qū)中寫(xiě)入數(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））;
}
/*銷(xiāo)毀一個(gè)環(huán)形緩沖區(qū)*/
ring_buff_destory（pt_ring_buff）;
return （1）;
}
總結(jié)
環(huán)形隊(duì)列的使用場(chǎng)景非常多，安卓的音頻數(shù)據(jù)讀寫(xiě)，很多都用到環(huán)形隊(duì)列，我們?cè)陂_(kāi)發(fā)過(guò)程中使用的環(huán)形隊(duì)列肯定比我上面的那個(gè)例子要復(fù)雜的多，我這里演示的是比較簡(jiǎn)單的功能，但是麻雀雖小，五臟俱全，希望這個(gè)麻雀讓你們了解這個(gè)數(shù)據(jù)結(jié)構(gòu)。在實(shí)際項(xiàng)目中大展身手。
原文標(biāo)題：C語(yǔ)言實(shí)現(xiàn)環(huán)形隊(duì)列的原理和方法
文章出處：【微信公眾號(hào)：strongerHuang】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
責(zé)任編輯：haq
-
數(shù)據(jù)
+關(guān)注
關(guān)注
8文章
7315瀏覽量
93988 -
C語(yǔ)言
+關(guān)注
關(guān)注
183文章
7642瀏覽量
144625
原文標(biāo)題：C語(yǔ)言實(shí)現(xiàn)環(huán)形隊(duì)列的原理和方法
文章出處：【微信號(hào)：strongerHuang，微信公眾號(hào)：strongerHuang】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
為什么單片機(jī)還在用C語(yǔ)言編程？
C語(yǔ)言特性
C語(yǔ)言和單片機(jī)C語(yǔ)言有什么差異
基于環(huán)形隊(duì)列的UART收發(fā)回顯實(shí)驗(yàn)
RabbitMQ消息隊(duì)列解決方案
主流的 MCU 開(kāi)發(fā)語(yǔ)言為什么是 C 而不是 C++？
NVME控制器之隊(duì)列管理模塊
深入理解C語(yǔ)言：C語(yǔ)言循環(huán)控制
工商網(wǎng)監(jiān)
評(píng)論