（温馨提示：这是博主最最喜欢的歌曲哦，没有之一）
题目：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
● MyCircularQueue(k): 构造器，设置队列长度为 k 。
● Front: 从队首获取元素。如果队列为空，返回 -1 。
● Rear: 获取队尾元素。如果队列为空，返回 -1 。
● enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
● deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
● isEmpty(): 检查循环队列是否为空。
● isFull(): 检查循环队列是否已满。
题解：
思路：
这里循环队列可以是使用链表实现，也可以是使用数组实现，两种方法这里都比队列长度k多开了一块空间，用来界定满和空，当两个指针相同时为NULL，当尾指针的下一个是头指针为满。
两种方法各有其优点和缺点：数组的Create方便一点，链表的麻烦；数组的尾元素和首元素计算和边界界定很麻烦，链表极简单；malloc出来的数组释放方便，链表麻烦，而且还需要一个指针prve记录尾指针的前一个，并在释放前将prve->next置为NULL使得释放容易。
至于选用哪种方式都是OK的，下面的两种方法leecode上都通过了，看各位自己选择。
方法一(数组)：
typedef struct { int *Spade_A; int front; int rear; int kk; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->Spade_A = (int*)malloc(sizeof(int)*(k+1)); obj->front = 0; obj->rear = 0; obj->kk = k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { if(obj->front == (obj->rear + 1) % (obj->kk + 1)) return true; else return false; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; else obj->Spade_A[obj->rear] = value; obj->rear++; obj->rear %= (obj->kk+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; else obj->front++; obj->front %= (obj->kk+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->Spade_A[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->Spade_A[(obj->rear + obj->kk)%(obj->kk+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->Spade_A); obj->front = obj->rear = 0; obj->kk = 0; free(obj); }
方法二(链表)：
typedef struct List { int data; struct List* next; }List; typedef struct { List *head; List *tail; List *prve; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->head = NULL; obj->tail = NULL; obj->prve = NULL; k++; while(k--) { List* newnode = (List*)malloc(sizeof(List)); newnode->next = NULL; if(obj->head == NULL) { obj->head = obj->tail = newnode; } else { obj->tail->next = newnode; obj->tail = newnode; } } obj->tail->next = obj->head; obj->tail = obj->head; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head == obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->tail->next == obj->head; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(!myCircularQueueIsFull(obj)) { obj->prve = obj->tail; obj->tail->data = value; obj->tail = obj->tail->next; return true; } else return false; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } else { obj->head = obj->head->next; return true; } } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->head->data; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->prve->data; } void myCircularQueueFree(MyCircularQueue* obj) { obj->prve->next = NULL; List* cur = obj->tail; while(cur) { List *next = cur->next; free(cur); cur = next; } obj->head = NULL; obj->tail = NULL; obj->prve = NULL; free(obj); }
