目錄

一、前言

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

2.如何判斷隊(duì)列為空？

3.如何判斷隊(duì)列為滿？

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

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

四、入隊(duì)

五、出隊(duì)

六、取隊(duì)頭元素

七、取隊(duì)尾元素

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

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

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

---

一、前言

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

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

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

2.如何判斷隊(duì)列為空？

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

3.如何判斷隊(duì)列為滿？

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

兩種解決方法：

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

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

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

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

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

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

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

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

//方法一
//循環(huán)隊(duì)列創(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;
}

四、入隊(duì)

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

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

五、出隊(duì)

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

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

六、取隊(duì)頭元素

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

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

七、取隊(duì)尾元素

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

//方法一
//取隊(duì)尾元素
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)隊(duì)列判空

通過size判空即可

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

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

通過size判滿即可

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

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

動(dòng)態(tài)申請(qǐng)的內(nèi)存空間需要?jiǎng)討B(tài)銷毀

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