循环队列的结构
循环队列是队列的一种特殊结构，它的长度是固定的k，同样是先进先出，理论结构是首尾相连的环形循环结构。其理论结构大致如下：
具体结构描述可以参考LeetCode: 622. 设计循环队列的题目要求，大致如下：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
循环队列的实现
循环队列的实现方式同样有两种–数组，链表
-
数组循环队列：
数组实现方式顾名思义就是动态开辟一个长度为k的数组，那要怎么达到循环呢？我们可以定义两个数一个指向队列头元素（int front），一个指向队列尾元素的下一个（int back），（此处指向队尾下一个是为了方便队列空和满的判断），这样当back走到最后一个时，我们只需要将他重新置成0便又到了队列第一个元素，如此设计理论上就达到了循环结构。
新的问题又来了：当front == back时要怎么区分队列是空还是满？两种解决方案：
- 增加一个
size记录有效数据的节点数，size == 0队列就是空，size == k队列就是满。- 多开辟一个空间
k+1，front == back便是空，(back+1)%(k+1) == front就是满（即在理论结构中back指向的下一个位置是front，下文会讲解）。
-
链表循环队列：
链表实现的循环队列更有点循环的味（即将尾指针的next指向头，形成真正的循环），但实现起来不如数组方便。链表实现循环队列同样要定义两个指针，一个指向循环队列的头元素（phead）,一个指向循环队列尾元素的下一个（ptail）。判断循环队列空和满的方法和数组相似，只不过判断条件从判断值相同改为判断址相同，第二种方法判满改为phead == ptail->next。
但用链表设计循环队列也会有新的困难：1.获取循环队列尾元素不方便，还要遍历队列寻找；2. 定义结构体时，还要多定义一个装链表节点的结构体，这也增加了代码的难度。
所以不论是用数组还是用链表实现循环队列，都有各自的好处和问题，下面实现循环队列我所介绍的方法是数组实现法，判满和判空用的是多定义一个节点法。
依据上述方法，可以定义如下结构体变量：
typedef struct
{
int* a;//数组
int front;//队列头
int back;//队列尾下一个位置
int k;//循环队列可存储数据长度
} MyCircularQueue;
循环队列的创建
注意此处所给的函数返回值类型为MyCircularQueue，正是上述结构体类型。故须先动态开辟一个结构体类型大小，并将front和back初始化为0，然后再利用结构体指针来开辟长度为k+1的数组，最后返回结构体指针。
这样动态开辟而不直接定义结构体变量（MyCircularQueue ps），是因为这是在函数中，出了函数的作用域此结构体变量就会销毁，所以需要malloc将结构体动态开辟在堆区。
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* ps = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
ps->a = (int*)malloc(sizeof(int)*(k+1));
ps->back = ps->front = 0;
ps->k = k;
return ps;
}
循环队列为空判断
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->back;
}
循环队列为满判断
循环队列为满大致可以分为以上两种情况。
-
情况1：
当队列尾back来到最后一个时，此时如果back + 1的话就会超过k + 1的范围，而我们的目的是想知道在循环队列中back + 1后的位置（即下标为0的位置），所以此时我们只要将(obj->back + 1)%(obj->k + 1)，此式的值便为0； -
情况2：
back + 1的范围在k + 1内，此时判断back + 1即可，若(obj->back + 1)%(obj->k + 1)也不会影响值。
如此将两式合并，便得到了简化的效果。
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->back+1)%(obj->k+1) == obj->front;
}
入队
题目描述：enQueue(value):向循环队列插入一个元素。如果成功插入则返回真。
既如此那么先判断循环队列是否已满，若满则返回false，否则入队新值，并将obj->back值更新（obj->back %= obj->k+1;）
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->back] = value;
obj->back++;
obj->back %= obj->k+1;
return true;
}
出队
题目描述：deQueue():从循环队列中删除一个元素。如果成功删除则返回真。
与入循环队列相似。
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front %= obj->k+1;
return true;
}
返回循环队列首元素
题目描述：Front:从队首获取元素。如果队列为空，返回 -1 。
先判断循环队列不为空，若为空返回-1，不为空返回下标为obj->front的值。
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
返回循环队列尾元素
题目描述：Rear:获取队尾元素。如果队列为空，返回 -1 。
同样要先判断循环队列是否为空，为空返回-1。此处计算obj->back上一个的下标的方法中，obj->back-1后还要加obj->k+1是为了防止obj->back指向下标为0的情况，再% (obj->k+1)是为了防止超出下标范围的情况，与判断队满相似。文章来源：https://www.toymoban.com/news/detail-766128.html
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->back-1+obj->k+1) % (obj->k+1)];
}
释放循环队列
依次释放即可，先释放最内层的数组，然后释放最外层的结构体。文章来源地址https://www.toymoban.com/news/detail-766128.html
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}
到了这里，关于【数据结构和算法】--队列的特殊结构-循环队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
