题目描述
题目来源：Leetcode622.设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
1.MyCircularQueue(k): 构造器，设置队列长度为 k 。
2.Front: 从队首获取元素。如果队列为空，返回 -1 。
3.Rear: 获取队尾元素。如果队列为空，返回 -1 。
4.enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
5.deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
6.isEmpty(): 检查循环队列是否为空。
7.isFull(): 检查循环队列是否已满。
解题思路：
在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。
注意：环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满。
我们如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：
可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：
1.当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。
2.当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。
这样就使得该数组在逻辑上是“环形”的了。
代码解决：
typedef struct { int* a;//数组模拟环形队列 int k;//队列可存储的有效数据总数 int front;//队头 int tail;//队尾的后一个位置 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列 obj->a = (int*)malloc(sizeof(int)*(k+1));//开辟队列空间 //初始时，队头和队尾均为0 obj->front = 0; obj->tail = 0; obj->k = k;//设置队列可存储的有效数据个数 return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail;//当front和tail指向同一位置时，队列为空 } bool myCircularQueueIsFull(MyCircularQueue* obj) { int tailNext = obj->tail+1; if(tailNext == obj->k+1)//当指针指到队列末尾时，指针返回队列开头，使队列循环 { tailNext = 0; } return tailNext == obj->front;//当tail+1指向的位置与front相同时，队列满 } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj))//队列已满，不能再插入数据 { return false; } else//插入数据 { obj->a[obj->tail] = value; obj->tail++; if(obj->tail == obj->k+1)//使队列循环 obj->tail = 0; return true; } } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//当队列为空时，无法再删除数据 { return false; } else//删除数据 { obj->front++; if(obj->front == obj->k+1)//使队列循环 obj->front = 0; return true; } } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据可返回 { return -1; } else { return obj->a[obj->front];//返回队头指向的数据 } } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据返回 { return -1; } else//返回tail-1指向位置的数据 { int tailPrev = obj->tail-1; if(tailPrev == -1)//使队列循环 tailPrev = obj->k; return obj->a[tailPrev]; } } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a);//先释放动态开辟的数组 free(obj);//再释放动态开辟的结构体 }
结果与总结：
通过所有示例，问题得到解决。
