本文共 2557 字，大约阅读时间需要 8 分钟。

题目要求

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

你的实现应该支持如下操作：

  MyCircularQueue(k): 构造器，设置队列长度为 k 。

  Front: 从队首获取元素。如果队列为空，返回 -1 。   Rear: 获取队尾元素。如果队列为空，返回 -1 。   enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。   deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。   isEmpty(): 检查循环队列是否为空。   isFull(): 检查循环队列是否已满。

思路

  我们采用数组的方式，最初我们将队列的头和队列的尾指向同一个位置，通过判断相等可以确定队列为空，但是当数据存满时也是队头和队尾相等了，因此，我们需要进行区分，解决方案是在malloc空间的时候，多申请上一个空间，我们将这个空间空出来，如果rear+1和front相等那么就说明环形队列是满的。同时因为我们使用的数组，所以当front的下标、rear的下标大于数组大小的时候需要置回到0，空的位置也可以是下标0的位置。 图解

代码实现

typedef struct {	int* a;	int front;	int rear;	int k;} MyCircularQueue;bool myCircularQueueIsFull(MyCircularQueue* obj);bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {	MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));	//多开一个空间区分空和满的区别	q->a = (int*)malloc(sizeof(int)*(k + 1));	q->front = q->rear = 0;	q->k = k;	return q;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {	if (myCircularQueueIsFull(obj))	{		return false;	}	obj->a[obj->rear] = value;	++obj->rear;	if (obj->rear == obj->k + 1)	{		obj->rear = 0;	}	return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {	if (myCircularQueueIsEmpty(obj))	{		return false;	}	++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;	}	int prev = obj->rear - 1;	if (obj->rear == 0)	{		prev = obj->k;	}	return obj->a[prev];}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {	if (obj->front == obj->rear)	{		return true;	}	else	{		return false;	}}bool myCircularQueueIsFull(MyCircularQueue* obj) {	int next = obj->rear + 1;	if (next == obj->k+1)	{		next = 0;	}	if (next == obj->front)	{		return true;	}	else	{		return false;	}}void myCircularQueueFree(MyCircularQueue* obj) {	free(obj->a);	free(obj);}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);*/