溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
