循环队列的实现

我们知道队列的实现可以用单链表和数组，但是循环链表也可以使用这两种方式。

首先我们来看看单链表：

首先使用单链表，我们需要考虑循环队列的一些特点。

单链表实现循环队列我们要考虑几个核心问题：

首先我们要区别 解决 空 和 满 的问题。多加一个空间，或者加一个size变量来记录。

当front==rail时，为空。

当rail->next == front时为满

其次，我们需要解决如何 能取出队尾的数据。对于单链表，因为我们rail指向队尾的后一个，所以不好取出队尾数据

数组来实现 循环链表：

同样当front==rail时，为空

当 front == （rail+1）%（k+1）时为满

数组解决循环链表，我们要考虑到：当不断出队和入队时如何循环起来？

可以使用if语句来判断，也可以给让rail超出数组大小后，直接回到数组开头。

当rail在第一个位置时，如何找到队尾元素呢？

我们可以使用if，也可以(rail+k)%(k+1)来取到前一个元素。

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>typedef struct {int* a;int front;int rail;int k;
}MyQueue;MyQueue* MyQueueCreat(int k)
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));obj->a = (int*)malloc(sizeof(int) * (k + 1));obj->front = obj->rail = 0;obj->k = k;
}
bool isMyQueueEmtp(MyQueue* obj)
{assert(obj);if (obj->front == obj->rail)return true;return false;
}
bool isMyQueueFull(MyQueue* obj)
{assert(obj);return (obj->rail + 1) % (obj->k + 1) == obj->front;
}
bool MyQueueEn(MyQueue* obj, int value)
{assert(obj);if (isMyQueueFull(obj))return -1;obj->a[obj->rail++] = value;obj->rail %= obj->k + 1;
}
bool MyQueueOut(MyQueue* obj)
{assert(obj);obj->front++;obj->front %= obj->k + 1;}int MyQueueFront(MyQueue* obj)
{assert(obj);return obj->a[obj->front];
}
int MyQueueRail(MyQueue* obj)
{asert(obj);if (isMyQueueEmtp(obj))return - 1;return obj->a[obj->rail + obj->k % obj->k + 1];
}void MyQueueFree(MyQueue* obj)
{assert(obj);free(obj->a);free(obj);
}

好的，今天的复习就到这里