四、设计循环队列
1、题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
2、题目分析
循环队列，本质还是实现一个队列，实现这个队列的基本几个接口，只不过这个队列是有限长度的，并且这个队列是循环的。
这个循环在我们的理解大概是个环状，这里要怎么实现呢？用数组还是链表来实现呢？乍一看，这个循环队列和我们循环链表的概念很相似，是否链表就优于数组呢？别着急，我们再来细品一下：
我们先图解看一下使用链表和数组的图解：
结合这个图解，博主把每个接口需要的功能先大致分析一下：
1、Front(队首) 和Rear(队尾)这两个接口比较简单，就是直接使用两个指针指向队首和队尾，然后返回就可以了。队首两种方式都可以，队尾的话如果是数组，直接找下标就能找到队尾的下标然后返回，（不过这一点还有一点细节需要注意，如果没发现还是会出错，博主后面还会说）但是链表，因为链表的尾指针指向的位置是没有填数据的，也就是队尾的next，所以需要遍历找到尾指针的上一个位置，比较麻烦。
2、enQueue(value): 向循环队列插入一个元素，这个函数也比较简单，就是尾插，我们设有一个尾指针，插入然后++就可以了。数组唯一需要注意的就是
3、deQueue(value)：从循环队列删除一个元素，队列先入先出的功能，就是头删，头指针++。
4、isEmpty(): 检查循环队列是否为空。isFull():判断循环队列是否满了，这两个问题比较有趣
分析一下我们就会发现，判空和判满无法区分，怎么解决呢？
我们创造性的提出了一种方式，类似于链表中增加一个哨兵位，我们多加一个位置，但是不填数据。比如：
我们发现，当我们加了一个位置的时候，这时候为空和为满的情况是不相同的，这时候是可以区分开两种情况的，说明增加一个位置确实是可行的，而且这个位置是不断变化的。
上面的图是数组的情况，这里需要处理的细节就是back如何和front建立联系，以及当back在尾的时候怎么回到头，这一点也和博主上面说的插入的数组需要考虑的情况相符合。这些都是数组需要考虑的。我们再来设想链表的话，似乎就不需要考虑这些问题，只需要back的next指针是否为front即可。
3、代码编译
博主用数组和链表都实现了一遍，都可以，各有利弊吧。
①数组的方式：
//数组去写 typedef struct { int*a; int front; int back; int capacity; } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj); bool myCircularQueueIsEmpty(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); int* tmp=(int*)malloc(sizeof(int)*(k+1)); if(tmp==NULL) { perror("malloc fail"); return NULL; } else { obj->a=tmp; obj->front=obj->back=0; obj->capacity=k+1; } return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //插入元素 if(!myCircularQueueIsFull(obj)) { //如果没满 obj->a[obj->back]=value; obj->back++; obj->back%=obj->capacity;//主要是要考虑到到了最后一个位置 return true; } else { return false; } } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(!myCircularQueueIsEmpty(obj)) { //没空才能删 obj->a[obj->front]=0;//虽然没啥意义 obj->front++; obj->front%=obj->capacity; return true; } else { return false; } } int myCircularQueueFront(MyCircularQueue* obj) { if(!myCircularQueueIsEmpty(obj)) return obj->a[obj->front]; else return -1; } int myCircularQueueRear(MyCircularQueue* obj) { if(!myCircularQueueIsEmpty(obj)) return obj->a[(obj->back-1+obj->capacity)%obj->capacity];//要考虑到back在第一个的情况 else return -1; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->back; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1)%obj->capacity==obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); obj->front=obj->back=0; obj->capacity=0; free(obj); obj=NULL; }
理解了上面的图解，用数组的方式来实现代码还是比较简单的，不过需要注意颇多的细节，
博主认为这些地方都是不易想到，需要注意的，而且可以说是点睛之笔。
1、第一个%主要是，当最后一个位置被填之后，如何回到队首，这个%可以说十分巧妙，直接回到队首。
2、第二个front也是同理，删到队尾的时候怎么回到队首。
3、而第三个找队尾元素，这样设计的原因是要考虑到，如果back在队首，那么队尾肯定是最后一个位置的元素，怎么找到呢？这种方式可以说很好的解决了这个问题。
4、而第四个则是为了解决判满的问题，当满的时候。back的下一个位置就是front，这样设计是为了解决back在最后一个位置，而front在第一个位置的情况。
这样操作不仅解决特殊情况，而且具有普适性，十分实用，但也不易被想到。
②链表的方式
typedef struct MCQueue { int data; struct MCQueue* next; } MCQueue; typedef struct { MCQueue* front; MCQueue* back; }MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); MCQueue* BuyNewnode() { MCQueue* newnode=(MCQueue*)malloc(sizeof(MCQueue)); if(newnode==NULL) { perror("malloc fail"); exit(-1); } else { newnode->next=NULL; } return newnode; } MyCircularQueue* myCircularQueueCreate(int k) { //初始化 MCQueue* CQueue=NULL; MCQueue* tail=NULL; int N=k+1;//多加一个位置 //构建链表 while(N--) { MCQueue* newnode=BuyNewnode(); if(CQueue==NULL) { CQueue=newnode; //方便找尾 tail=CQueue; } else { //头插的一种方式 newnode->next=CQueue; CQueue=newnode; } tail->next=CQueue; //链接起来 } MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->front=CQueue; obj->back=CQueue; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(!myCircularQueueIsFull(obj)) { obj->back->data=value; //指向下一个 obj->back=obj->back->next; return true; } else return false; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { //删的前提是没空 if(!myCircularQueueIsEmpty(obj)) { obj->front=obj->front->next; return true; } else return false; } int myCircularQueueFront(MyCircularQueue* obj) { if(!myCircularQueueIsEmpty(obj)) { return obj->front->data; } else { return -1; } } int myCircularQueueRear(MyCircularQueue* obj) { //这个比较麻烦，需要找到back的前一个 if(!myCircularQueueIsEmpty(obj)) { MCQueue* cur=obj->front; while(cur->next!=obj->back) { cur=cur->next; } //找到前一个 return cur->data; } else return -1; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->back; } bool myCircularQueueIsFull(MyCircularQueue* obj) { //如何判满？ return obj->back->next==obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { MCQueue* cur=obj->front->next; while(cur!=obj->front) { MCQueue* next=cur->next; free(cur); cur=next; } free(cur); free(obj); }
从逻辑上来讲，链表更符合循环链表的逻辑，不过用链表比较怪怪的，但是构建就比较麻烦，需要一个一个链表去开创，还要去链接起来，更古怪的是这些链表什么数据也不放，不太合习惯，而且用链表来实现比较恶心的有两点：
1、链表的初始化和链接，以及开创之后，因为这是一个环形链表，而且没有下标，那么哪个是头，哪个是尾需要你自己去定义。
2、在找尾的时候，需要再次遍历一下，时间复杂度是0(N)。
优点就是：
不需要去特殊处理数组需要处理的那些情况，初始化之后写起来很顺。
好了，本期的oj分享就到这里了，希望大家可以养成良好的编程习惯，多画图分析，争取一次过，而不是修修补补。
