贵州网站制作品牌公司国家建设标准网站

实现循环队列最难的地方就在于如何判空和判满，只要解决了这两点循环队列的设计就没有问题。接下来我们将会使用数组来实现循环队列。

接下来，为了模拟实现一个容量为4的循环队列，我们创建一个容量为4 + 1 的数组。

接下来我们将会对这个数组进行增删

下图是对于这个循环进行插值，其中h代表head，t代表tail。h代表循环列表的第一个元素，t代表循环列表的末尾元素的下一个。0代表空的还未利用的空间。

当t走到末尾时，再加一将会跳转到数组的头部，以此实现逻辑上的循环。

添加元素：

删除元素：

继续添加元素

继续删除元素

继续添加元素：

通过这些图我们可以清晰地看到，当h==t的时候，循环列表为空。当t+1 == h时，循环列表为满。

熟悉了方法后，实现它就不难了。接下来我将会提供代码，我将会写上必要的注释方便理解。

头文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QueueData;
typedef struct MyCircularQueue
{QueueData* a;int k;int head;int tail;
} MyCircularQueue;// 这个函数用于创建一个循环队列。参数 k 表示队列的容量。
// 返回值是一个指向循环队列对象的指针。
MyCircularQueue* myCircularQueueCreate(int k);// 这个函数用于向循环队列中添加一个元素。
// 参数 obj 是指向循环队列对象的指针，value 是要添加的元素的值。
// 如果成功添加元素，则返回 true；如果队列已满，则返回 false。
bool myCircularQueueEnQueue(MyCircularQueue* obj, QueueData value);// 这个函数用于从循环队列中移除一个元素。
// 参数 obj 是指向循环队列对象的指针。
// 如果成功移除元素，则返回 true；
// 如果队列为空，则返回 false。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 这个函数用于获取循环队列的队首元素。
// 参数 obj 是指向循环队列对象的指针。返回队首元素的值。
int myCircularQueueFront(MyCircularQueue* obj);// 这个函数用于获取循环队列的队尾元素。
// 参数 obj 是指向循环队列对象的指针。返回队尾元素的值。
int myCircularQueueRear(MyCircularQueue* obj);// 这个函数用于检查循环队列是否为空。
// 参数 obj 是指向循环队列对象的指针。
// 如果队列为空，则返回 true；否则返回 false。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);// 这个函数用于检查循环队列是否已满。
// 参数 obj 是指向循环队列对象的指针。
// 如果队列已满，则返回 true；否则返回 false。
bool myCircularQueueIsFull(MyCircularQueue* obj);// 这个函数用于释放循环队列对象所占用的内存。
// 参数 obj 是指向循环队列对象的指针。
// 在调用该函数后，指向循环队列对象的指针将不再有效。
void myCircularQueueFree(MyCircularQueue* obj);

函数的实现：

#include "Cycle_Queue.h"MyCircularQueue* myCircularQueueCreate(int k)
{assert(k > 0);MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));QueueData* arr = (QueueData*)malloc(sizeof(QueueData) * (k + 1));if (ret == NULL || arr == NULL){perror("malloc faile");exit(-1);}ret->a = arr;ret->k = k;ret->head = ret->tail = 0;return ret;
}void myCircularQueueFree(MyCircularQueue* obj)
{assert(obj);free(obj->a);obj->a = NULL;obj->k = 0;free(obj);
}int myCircularQueueFront(MyCircularQueue* obj)
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj)
{assert(obj);if (myCircularQueueIsEmpty(obj))return -1;// 值得注意的是tail指向的是队列末尾元素的下一个，所以你需要让他向前走完一圈后再后退一步才能得到末尾元素。// 也即：(obj->tail + obj->k) % (obj->k + 1)，其中% (obj->k + 1)是为了保证tail的值可以再某个区间里，以实现循环队列。return obj->a[(obj->tail + obj->k + 1 - 1) % (obj->k + 1)];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj);return obj->head == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{assert(obj);// 当tail再往前走一步就碰到head了，就说明此时的队列已经满了。return obj->head == (obj->tail + 1) % (obj->k + 1);
}bool myCircularQueueEnQueue(MyCircularQueue* obj, QueueData value)
{assert(obj);if (myCircularQueueIsFull(obj))return false;obj->a[obj->tail] = value;obj->tail = (obj->tail + 1) % (obj->k + 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{assert(obj);if (myCircularQueueIsEmpty(obj))return false;obj->head = (obj->head + 1) % (obj->k + 1);return true;
}