如何创建循环队列？——一份简单易懂的数据结构指南

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

通常队列是用链表来实现，不过在这里循环队列既可以使用数组实现，也可以用链表实现。

数组设计循环队列的好处：

1.找队尾元素方便，链表实现需要记住前面的节点，需要找尾。

2.循环实现方便，只要让最后一个元素下标模上数组的大小，就可以回到数组首元素位置。而链表如果只有使用循环双向链表才可以达到方便的效果。

• 数组实现循环队列的思想

数组需要多开辟一个空间，以达到循环效果。

front用来追踪队头元素

rear用来追踪队尾元素

一开始front和rear都指向数组开头位置，当有元素插入进来时，rear跟着往后走。插入一个元素，rear走一步，插入两个元素，rear走两步，插入三个元素，rear走三步。当队列中满了无法插入时，就不能再走了。

队尾元素的位置就是rear-1.

现在front的位置就是队头的位置，当有元素被删除时，front就往后走，删除一个元素，front就完后走，删除一个元素就往后走(注意这是队列，删除数据是从队头删除)，直到队列中元素都删除光了，就不能走了。

所以队头元素的位置就是front的位置。

那如何实现循环的呢？

因为我们给数组多开了一个空间，当队列满了时候无法插入了，删除队头元素后，队头空间就留出来了，这时只要往多开辟的空间里插入元素，rear再往后走，不过rear是回到最开始的位置，也就是队头位置了。

这时多开辟的位置就起到了暂时存储数据的作用。当队列满了就不能插入了。

而什么情况算满了呢？当rear+1=front就说明队列已经满了，上图就是队列已满的情况，可能有人会说

这样不符合呀，这不是也满了嘛，对呀这是队列已经满了，不过这里的rear+1后就是回到数组首元素的位置上了呀，所以是符合情况的。

①.MyCircularQueue(k)设置队列长度为 k 。

typedef struct {
  int* a;
  int front;
  int rear;
  int k;
} MyCircularQueue;//首先定义一个队列，这个队列由数组a，下标front，rear还有数组大小k构成
//为什么要给k呢？因为不给k数组的大小的话，后面需要取模就不好取模了=
MyCircularQueue* myCircularQueueCreate(int k)//定义一个指向队列的指针  
{
   //队列的空间需要动态开辟，还有队列里面的数组空间也需要动态开辟，所以需要开辟两个空间，最后释放也需要释放两个空间。
   
  MyCircularQueue* queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  queue->a = (int*)malloc(sizeof(int) * (k + 1));//数组需要多开辟一个空间
  queue->front = queue->rear = 0;//一开始都指向0
  queue->k = k;//数组大小
  return queue;
} 

②.isEmpty(): 检查循环队列是否为空。

如何判断队列是否为空呢？

当一开始队列中没有元素时，rear和front都指向0表明队列为空，但是不一定都必须在0这个位置，只要当rear和front都相等时，就说明队列是空的。

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
  return obj->front == obj->rear;
}

③.isFull(): 检查循环队列是否已满。

本质上就是rear+1=front就表示队列已经满了，

不过这样的情况可能不满足，我们分析rear如果加1那肯定不会等于front的呀。

这样队列也是满的不过队列比较特殊，我们需要当rear+1后再模上数组总长度也就是k+1.

我们知道当一个数模上一个比它大的数时，是没有影响的，所以只有当rear+1时等于数总长度，模完等于0又回到首元素的位置去，其他位置上rear模上k+1是没有影响的。

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
  return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

④.enQueue(value): 向循环队列插入一个元素。

向循环队列插入一个元素。如果成功插入则返回真。

向循环队列中插入一个元素时，rear就要跟着往后走。

并且要注意的是，每次rear走完后都需要取模一下，当最后一个位置又元素插入时，rear就需要回到数组首元素的位置，那如何回去呢？就是根据取模就可以让rear返回去，每次rear++完，让rear模上数组总长度也就是k+1，如果，最后一位置插入元素了，那么rear++完就变成0.

还要注意的是，在插入之前我们需要考虑，队列是否已经满了，当队列满了时候，就无法插入进去了。

所以代码如下：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
  if (myCircularQueueIsFull(obj))//在插入之前判断是否队列满了
  {
    return false;
  }
  else
  {
    obj->a[obj->rear++] = value;
    obj->rear %= obj->k + 1;//每次插入，rear往后走完，都需要进行取模，防止走出数组范围
  }
}

⑤.deQueue(): 从循环队列中删除一个元素。

从循环队列中删除一个元素。如果成功删除则返回真。

在删除元素之前需要考虑队列是否为空，如果为空，那就不能再删了。

因为front就是队头元素的位置，当删除一个元素时，front就往后走，删除一个元素就往走，这里注意front每往后走一步都需要取模，道理一样，防止front走过头，当front在数组最后一个位置时，再删除元素呢，front就要变成0了。

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
  if (myCircularQueueIsEmpty(obj))
  {
    return false;
  }
  else
  {
    ++obj->front;
    obj->front %= obj->k + 1;
  }
  
}

⑥.Front: 从队首获取元素 。

获取队头数据，很简单，因为front的位置就是队头的数据，但要注意的是当队列为空时，那就没有数据可获取了，需要讨论下。

int myCircularQueueFront(MyCircularQueue* obj)
{
  if (myCircularQueueIsEmpty(obj))
  {
    return -1;//如果为空，则返回-1；
  }
  else
  {
    return obj->a[obj->front];
  }
}

⑦.Rear: 获取队尾元素。

与获取队头数据一样，在获取之前需要判断一下队列是否为空获取队尾数据，也简单，队尾数据的位置不就是rear-1嘛。

不过这里有个特例，当数组最后一个元素插入进来，rear的值就需要更新成0了，那这时再获取队尾数据位置，还是rear-1吗？

当然不是了，rear-1不就是-1了嘛。

所以我们这里可以分两种情况讨论，定义一个变量x,当rear==k+1时，就将x=k,当rear！=k+1时，那x=rear-1； x位置就是队尾数据。

int myCircularQueueRear(MyCircularQueue* obj)
{
  if (myCircularQueueIsEmpty(obj))
  {
    return -1;
  }
  else
  {
    int x = obj->rear == obj->k + 1 ? obj->k : obj->rear - 1;
    return obj->a[x];
  }

}

这里还有第二种解决方法，rear-1加上k+1再模上k+1

原理是什么呢？

一个数模上一个比它大的数是不变的，rear-1+k+1就可以回到原来的位置，这个是针对上图情况，再模上k+1，就是针对所有情况了。

int myCircularQueueRear(MyCircularQueue* obj)
{
  if (myCircularQueueIsEmpty(obj))
  {
    return -1;
  }
  else
  {
    return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
  }

}

⑧.myCircularQueueFree 销毁循环队列

因为一开始动态开辟了两个空间，一个队列空间，一个数组空间，所以需要释放两个空间

void myCircularQueueFree(MyCircularQueue* obj)
{
  free(obj->a);
  free(obj);
}