LeetCode622如何设计成循环队列？

题目 　　设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 　　循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 　　你的实现应该支持如下操作： MyCircularQueue(k)：构造器，设置队列长度为k。 Front：从队首获取元素。如果队列为空，返回1。 Rear：获取队尾元素。如果队列为空，返回-1。 enQueue(value)：向循环队列插入一个元素。如果插入成功则返回真。 deQueue()：从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty()：检查循环队列是否为空。 isFulL()：检查循环队列是否已满。 示例： MyCircularQueue circularQueue = new MyCircu larQueue(3) ;// 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false, 队列已满circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); / / 返回 4 提示： 所有的值都在0至1000的范围内; 操作数将在1至1000的范围内； 请不要使用内置的队列库。 解题 　　首先需要创建一个队列专用的结构体用于申明队列中的队头、队尾、队列大小等基础结构，循环队列的结构示意如下图： 　　首先进行循环队列结构体的布局说明，声明队列的所有基本元素： typedef struct { int* data;//存储队列元素的动态数组指针 int front;//指向队头前一个元素的问题 int rear;//队尾索引 int size;//队列总容量大小 } MyCircularQueue; 　　然后创建循环队列并进行初始化： /* *@param k：实际队列容量（不包括预留的空槽） *@return 返回指向新创建的循环队列结构体的指针 */ MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = malloc(sizeof(MyCircularQueue));//申请结构体堆内存 if(obj == MULL) return NULL; obj->data = malloc(sizeof(int) * (k + 1));//申请指针变量data内存 if(obj->data == NULL) { free(obj); return NULL; } obj->size = k + 1;//队列大小（空槽法） //队列初始化 obj->front = 0; obj->rear = 0; return obj; } 　　在这里需要额外说明一个容易产生疑惑的问题：为什么前面已经定义了 MyCircularQueue 结构体，在 myCircularQueueCreate() 函数中仍然需要再次对结构体申请内存。 　　MycircularQueue的作用是定义循环队列结构体类型，并声明其成员布局。此时只是完成了类型描述，还没有创建具体的循环队列对象，也没有为某个对象分配运行时内存。在mycircularQueueCreate(）函数中，先通过malloc(sizeof(MycircularQueue））在堆上申请一块结构体内存，用于存放data、front、、rear 和size 等成员；随后再通过malloc(sizeof(int）*(k + 1))为data指向的动态数组申请实际元素存储空间。前者是队列控制块，后者是队列数据区，这两部分内存需要分开理解。 　　接着是创建循环队列最基础的功能函数： bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj == NULL) return false; return (obj->rear == obj->front); } bool myCircularQueueIsFull(MyCircularQueue* obj) { if(obj == NULL) return false; return (obj->front == (obj->rear + 1) % obj->size); } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(obj == NULL) return false; if(myCircularQueueIsFull(obj)) return false; obj->rear = (obj->rear + 1) % obj->size; obj->data[obj->rear] = value; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(obj == NULL) return false; if(myCircularQueueIsEmpty(obj)) return false; int temp; obj->front = (obj->front + 1) % obj->size; temp = obj->data[obj->front]; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(obj == NULL) return 0; if(myCircularQueueIsEmpty(obj)) return -1; int temp; temp = (obj->front + 1) % obj->size; return (obj->data[temp]); } int myCircularQueueRear(MyCircularQueue* obj) { if(obj == NULL) return 0; if(myCircularQueueIsEmpty(obj)) return -1; return obj->data[obj->rear]; } void myCircularQueueFree(MyCircularQueue* obj) { if(obj == NULL) return; free(obj->data); free(obj); } 　　这些分别是判空、判满、入队、出队、获取队头/队尾元素和释放结构体内存。