【数据结构】07.循环队列

一、循环队列的定义

定义：队列主要有顺序队列，循环队列，双端队列，优先队列。而当中循环队列是一种线性数据结构。它也被称为“环形缓冲器”。它只允许在一端进行插入操作，即队尾（rear），而在另一端进行删除操作，即队头 (front)，其操作表现基于FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。向队列中插入新的数据元素称为入队，新入队的元素就成为了队列的队尾元素。

特点：

循环队列允许元素在队尾插入，在队头删除，同时遵循先进先出原则。
由于循环队列是基于数组实现的，所以它的访问速度很快，特别是在移动元素时。
如果需要大量添加和删除元素，循环队列比链表更有效率，因为它不需要频繁地移动指针来访问元素。
不支持随机访问元素，因此不能像数组那样直接访问特定位置的元素。

二、循环队列的实现

本篇文章要实现的操作如下：
在这里插入图片描述
本文的思路来自设计循环队列

2.1 循环队列的行为

我们使用顺序表来实现循环队列，在开始时初始化出队列的大小为k。并分别用front指向队头元素，rear指向队尾元素的下一个位置。

typedef struct 
{int* a;int front;int rear;int k;
} MyCircularQueue;

2.2 循环队列的初始化

我们在申请空间时多申请一个空间，用来解决假溢出问题。这样方便我们判断队列何时满了（rear的下一个位置是front就满了）

MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->a=(int*)malloc(sizeof(int)*(k+1));q->front=0;//头q->rear=0;//尾下一个q->k=k;return q;
}

2.3 循环队列的判空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->front==obj->rear;
}

2.4 循环队列的判满

可不要简单的以为循环队列满的条件就是rear + 1 == front，我们要考虑下面两种情况：
情况一：
在这里插入图片描述
情况二：

上面两种情况队列都是满的，显然我们不能简单的用front == rear + 1来判断队列是否已满。

直接下结论：我们可以用表达式(rear + 1) % (k + 1) == front来判断队列是否已满

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{return (obj->rear+1)%(obj->k+1)==obj->front;//当rear指向多出来的位置时通过驱魔
}

2.4 循环队列的入队

在入队的时候我们也要考虑两种情况：
情况一：
在这里插入图片描述
情况二：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);return true;
}

2.5 循环队列的出队

在出队时同样要考虑两种情况：
情况一：
在这里插入图片描述
情况二：

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))return false;obj->front++;(obj->front)%=(obj->k+1);return true;
}

2.6 返回队头元素

由于队头指针指向的就是队头元素，因此直接返回下标位置的元素即可

int myCircularQueueFront(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}

2.7 返回队尾元素

由于队尾指针指向的是队尾元素的下一个位置，因此要考虑两种情况：
情况一：

在这里插入图片描述
情况二：

int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}

2.8 循环队列的销毁

void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->a);free(obj);
}