目錄

一、前言

1.如何實現(xiàn)循環(huán)？

2.如何判斷隊列為空？

3.如何判斷隊列為滿？

二、循環(huán)隊列的結(jié)構(gòu)定義

三、循環(huán)隊列的創(chuàng)建及其初始化

四、入隊

五、出隊

六、取隊頭元素

七、取隊尾元素

八、循環(huán)隊列判空

九、循環(huán)隊列判滿

十、循環(huán)隊列銷毀

---

一、前言

利用數(shù)組實現(xiàn)循環(huán)隊列，重點要解決的問題有三個：

1.如何實現(xiàn)循環(huán)？

由于數(shù)組大小k是確定的，要實現(xiàn)隊列循環(huán)就需要讓數(shù)組下標(biāo)循環(huán)，利用兩個下標(biāo)front、back分別指向首元素和尾元素的下一個位置。front = (front+1) % k，back = (back+1) % k，即可完成下標(biāo)的循環(huán)。

2.如何判斷隊列為空？

初始化時，front和back都為0，此時為空。因此我們確定判空條件為 front = back時循環(huán)隊列為空。

3.如何判斷隊列為滿？

我們發(fā)現(xiàn)，當(dāng)隊列滿時，由于back指向隊尾元素的下一個，因此隊列滿時，front = back ，與隊列空時相矛盾。如何解決呢？

兩種解決方法：

一是：循環(huán)隊列結(jié)構(gòu)中新增隊列大小 size ，當(dāng)size=0且front = back時，隊列為空；當(dāng)size≠0且front = back時，隊列為滿。

二是：新增一個空間，不存儲數(shù)據(jù)，front = (front+1) % (k+1)，back = (back+1) % (k+1)，當(dāng) (back+1) % (k+1) = front時，隊列為滿。

本文僅講解方法一，方法二詳解：數(shù)組實現(xiàn)循環(huán)隊列（新增一個空間）-CSDN博客

二、循環(huán)隊列的結(jié)構(gòu)定義

循環(huán)隊列的結(jié)構(gòu)中包含數(shù)組、頭指針、尾指針、隊列容量、隊列大小（隊列大小用于區(qū)分隊列空與滿的情況）

//方法一
typedef int MCQDataType;
//循環(huán)隊列結(jié)構(gòu)定義
typedef struct {MCQDataType *a;int front;//頭指針，指向隊頭元素int back;//尾指針，指向隊尾元素的下一個位置int size;//隊列大小int k;//隊列容量
} MyCircularQueue;

三、循環(huán)隊列的創(chuàng)建及其初始化

為循環(huán)隊列動態(tài)申請一個內(nèi)存空間，再將頭指針、尾指針、隊列大小都初始化為0，隊列容量為k

//方法一
//循環(huán)隊列創(chuàng)建及其初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* mcq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));mcq->a=(MCQDataType*)malloc(sizeof(MCQDataType)*(k));mcq->front=mcq->back=mcq->size=0;mcq->k=k;return mcq;
}

四、入隊

先通過size判斷隊列是否滿，不滿再將數(shù)據(jù)入隊，同時尾指針要? 加1模k （back = (back+1) % k）?

//方法一
//入隊
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(obj->size==obj->k)//隊列已滿{return false;}obj->a[obj->back]=value;obj->back=(obj->back+1)%obj->k;obj->size++;return true;
}

五、出隊

先通過size判斷隊列是否空，不空再將數(shù)據(jù)出隊，同時頭指針要? 加1模k?（front = (front+1) % k）

//方法一
//出隊
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(obj->size==0)//隊列為空{(diào)return false;}obj->front=(obj->front+1)%obj->k;obj->size--;return true;
}

六、取隊頭元素

先通過size判斷隊列是否為空，不空直接返回隊頭元素即可

//方法一
//取隊頭元素
int myCircularQueueFront(MyCircularQueue* obj) {if(obj->size==0)//隊列為空{(diào)return -1;}return obj->a[obj->front];
}

七、取隊尾元素

先通過size判斷隊尾是否為空。由于尾指針指向的是隊尾元素的下一個位置，所以需要返回back-1位置的元素。由此需要判斷尾指針是否指向0位置，如果指向0位置則不能back-1，否則越界，需要返回數(shù)組的最后一個位置元素，即k-1的位置；如果不指向0位置，則返回back-1位置的元素即可。

//方法一
//取隊尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(obj->size==0){return -1;}if(obj->back==0){return obj->a[obj->k-1];}else{return obj->a[obj->back-1];}
}

八、循環(huán)隊列判空

通過size判空即可

//方法一
//循環(huán)隊列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size==0;
}

九、循環(huán)隊列判滿

通過size判滿即可

//方法一
//循環(huán)隊列判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->k;
}

十、循環(huán)隊列銷毀

動態(tài)申請的內(nèi)存空間需要動態(tài)銷毀

//方法一
//循環(huán)隊列銷毀
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}