C語言數(shù)據(jù)結(jié)構(gòu)算法基礎之循環(huán)隊列示例
說明
循環(huán)隊列是一種先進先出的,首尾相連的隊列。
大致的結(jié)構(gòu)如下圖:
用數(shù)組來抽象的表示一下的話,如下圖:
循環(huán)隊列有兩個指針指向數(shù)據(jù),上圖中的start和end就是那兩個指針,它們指向相同的位置,表示的是空,即隊列是空的。
隨著數(shù)據(jù)的放入,隊列一般有下面的兩種形式:
需要注意第二種形式,從圖上看end在start的前面了,但是因為循環(huán)關(guān)系,前后并不重要。
另外需要考慮的是隊列滿的情況:
但這種情況存在一個問題,即空隊列和滿隊列沒有辦法區(qū)分了,end和start都指向了相同的位置。
為了解決這個問題,一個方法是空出一個位置不放數(shù)據(jù),當end再加一個數(shù)據(jù)就等于start的時候就認為隊列是滿的:
這時實際的數(shù)據(jù)長度就會比分配的少1。
下面是隊列中空和滿的判斷:
1. 隊列為空時:end == start
2. 隊列為滿時:(end + 1) % size == start
這里的size是指分配的空間大小,而不是隊列長度,隊列的實際長度為(end - start + size) % size,最大長度是size-1
這也是因為要考慮循環(huán)的關(guān)系,所以要加上%size這個操作。
示例代碼
1. 首先定義結(jié)構(gòu)體:
//定義循環(huán)隊列 typedef struct _LoopQueue { int data[8]; //存放數(shù)據(jù) int start; //頭指針 int end; //尾指針 } LoopQueue;
2. 定義各種算法:
#define TRUE 1 #define FALSE 0 #define SIZE 8 //初始化隊列 int init(LoopQueue *lq) { lq->start = 0; lq->end = 0; return TRUE; } //判斷隊列是否為空 int isEmpty(LoopQueue *lq) { if (lq->start == lq->end) { return TRUE; } return FALSE; } //判斷隊列是否為滿 int isFull(LoopQueue *lq) { if ((lq->end + 1) % SIZE == lq->start) { return TRUE; } return FALSE; } //獲取隊列的長度 int getLength(LoopQueue *lq) { return (lq->end - lq->start + SIZE) % SIZE; } //插入數(shù)據(jù) int pushQueue(LoopQueue *lq, int data) { if(isFull(lq)) { printf("Queue is full.\n"); return FALSE; } lq->data[lq->end] = data; lq->end = (lq->end + 1) % SIZE; return TRUE; } //彈出數(shù)據(jù) int popQueue(LoopQueue *lq, int *data) { if (isEmpty(lq)) { printf("Queue is empty.\n"); return FALSE; } *data = lq->data[lq->start]; lq->start = (lq->start + 1) % SIZE; return TRUE; } //顯示隊列中的數(shù)據(jù) void printQueue(LoopQueue *lq) { int index; int count; count = getLength(lq); if (0 == count) { printf("No data.\n"); return; } for (index = 0; index < count; index++) { printf("%d ", lq->data[index]); } printf("\n"); return; }
3. 測試:
int main() { int index; int num; //隊列測試代碼 LoopQueue *lq = (LoopQueue *)malloc(sizeof(LoopQueue)); init(lq); printQueue(lq); for (index = 0; index < SIZE; index ++) { //注意這里要放8個數(shù)據(jù),但是實際上只能放7個,所以最后一個會報錯 pushQueue(lq, index); } printQueue(lq); for (index = 0; index < SIZE; index ++) { //同上,會打印一個錯誤 if (popQueue(lq, &num)) { printf("%d\n", num); } } printQueue(lq); return 0; }
4. 最后的結(jié)果:
以上就是C語言數(shù)據(jù)結(jié)構(gòu)算法基礎之循環(huán)隊列的詳細內(nèi)容,更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)算法循環(huán)隊列的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C++數(shù)據(jù)結(jié)構(gòu)紅黑樹全面分析
今天的這一篇博客,我要跟大家介紹二叉搜索樹中的另一顆樹——紅黑樹,它主要是通過控制顏色來控制自身的平衡,但它的平衡沒有AVL樹的平衡那么嚴格2022-02-02C++?STL標準庫std::vector擴容時進行深復制原因詳解
我們知道,std::vector之所以可以動態(tài)擴容,同時還可以保持順序存儲,主要取決于其擴容復制的機制。當容量滿時,會重新劃分一片更大的內(nèi)存區(qū)域,然后將所有的元素拷貝過去2022-08-08Qt?加載?libjpeg?庫出現(xiàn)“長跳轉(zhuǎn)已經(jīng)運行”錯誤問題解決
這篇文章主要介紹了Qt?加載?libjpeg?庫出現(xiàn)“長跳轉(zhuǎn)已經(jīng)運行”錯誤,本文給大家分享完美解決方案,需要的朋友可以參考下2023-04-04