数组实现循环队列（增设队列大小size）

一、前言

利用数组实现循环队列，重点要解决的问题有三个：

1.如何实现循环？

由于数组大小k是确定的，要实现队列循环就需要让数组下标循环，利用两个下标front、back分别指向首元素和尾元素的下一个位置。front = (front+1) % k，back = (back+1) % k，即可完成下标的循环。

2.如何判断队列为空？

初始化时，front和back都为0，此时为空。因此我们确定判空条件为 front = back时循环队列为空。

3.如何判断队列为满？

我们发现，当队列满时，由于back指向队尾元素的下一个，因此队列满时，front = back ，与队列空时相矛盾。如何解决呢？

两种解决方法：

一是：循环队列结构中新增队列大小 size ，当size=0且front = back时，队列为空；当size≠0且front = back时，队列为满。

二是：新增一个空间，不存储数据，front = (front+1) % (k+1)，back = (back+1) % (k+1)，当 (back+1) % (k+1) = front时，队列为满。

本文仅讲解方法一，方法二详解：数组实现循环队列（新增一个空间）-CSDN博客

二、循环队列的结构定义

循环队列的结构中包含数组、头指针、尾指针、队列容量、队列大小（队列大小用于区分队列空与满的情况）

//方法一

typedef int MCQDataType;

//循环队列结构定义

typedef struct {

MCQDataType *a;

int front;//头指针，指向队头元素

int back;//尾指针，指向队尾元素的下一个位置

int size;//队列大小

int k;//队列容量

} MyCircularQueue;

三、循环队列的创建及其初始化

为循环队列动态申请一个内存空间，再将头指针、尾指针、队列大小都初始化为0，队列容量为k

//方法一

//循环队列创建及其初始化

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判断队列是否满，不满再将数据入队，同时尾指针要 加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判断队列是否空，不空再将数据出队，同时头指针要 加1模k （front = (front+1) % k）

//方法一

//出队

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

if(obj->size==0)//队列为空

{

return false;

}

obj->front=(obj->front+1)%obj->k;

obj->size--;

return true;

}

六、取队头元素

先通过size判断队列是否为空，不空直接返回队头元素即可

//方法一

//取队头元素

int myCircularQueueFront(MyCircularQueue* obj) {

if(obj->size==0)//队列为空

{

return -1;

}

return obj->a[obj->front];

}

七、取队尾元素

先通过size判断队尾是否为空。由于尾指针指向的是队尾元素的下一个位置，所以需要返回back-1位置的元素。由此需要判断尾指针是否指向0位置，如果指向0位置则不能back-1，否则越界，需要返回数组的最后一个位置元素，即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];

}

}

八、循环队列判空

通过size判空即可

//方法一

//循环队列判空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

return obj->size==0;

}

九、循环队列判满

通过size判满即可

//方法一

//循环队列判满

bool myCircularQueueIsFull(MyCircularQueue* obj) {

return obj->size==obj->k;

}

十、循环队列销毁

动态申请的内存空间需要动态销毁

//方法一

//循环队列销毁

void myCircularQueueFree(MyCircularQueue* obj) {

free(obj->a);

free(obj);

}