目录

（一）题目描述

（二）数据结构的选择

（三）函数接口的分析实现

正文开始：

（一）题目描述

题目链接：622. 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

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

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3circularQueue.enQueue(1); // 返回 truecircularQueue.enQueue(2); // 返回 truecircularQueue.enQueue(3); // 返回 truecircularQueue.enQueue(4); // 返回 false，队列已满circularQueue.Rear(); // 返回 3circularQueue.isFull(); // 返回 truecircularQueue.deQueue(); // 返回 truecircularQueue.enQueue(4); // 返回 truecircularQueue.Rear(); // 返回 4

提示：

  • 所有的值都在 0至 1000 的范围内；
  • 操作数将在 1 至 1000 的范围内；
  • 请不要使用内置的队列库。

（二）数据结构的选择

在C语言中，实现队列的数据结构可以选择使用数组或链表，具体选择哪种数据结构取决于应用的需求和对性能的要求。

  1. 数组：使用数组实现队列的优势是简单和高效。可以使用一个固定大小的数组来表示队列，并使用两个指针front和rear来分别指示队列的前端和后端。入队操作可以通过将元素添加到rear指针指向的位置来实现，而出队操作可以通过将元素从front指针指向的位置移除来实现。数组的缺点是长度固定，一旦实现的队列满了，就不能再添加元素。

  2. 链表：使用链表实现队列的优势是可以动态地调整队列的大小，没有固定的长度限制。可以使用一个指针来表示链表的头部，并使用另一个指针来表示链表的尾部。入队操作可以通过在链表的尾部添加节点来实现，而出队操作可以通过删除链表的头部节点来实现。链表的缺点是相对于数组来说，操作稍微复杂一些，需要维护指针的指向关系。

综上所述，如果对队列的长度有明确的限制，可以选择使用数组实现队列。如果队列的长度不确定或需要频繁地进行插入和删除操作，可以选择使用链表实现队列。

在循环队列的题目要求中，指定了队列的数据个数为K，因此本次实现队列采用数组的方式实现；通过定义一个结构体来方便对循环队列的维护：

typedef struct {int* a;//动态数组int k;//队列大小int front;//队头指针，指向队头数据int rear;//队尾指针，指向队尾数据的下一个位置} MyCircularQueue;

如果rear指向的是队尾元素，那么数据个数为0和数据个数为1的情况无法区分，仔细想一想，这两种情况都是front和rear指针指向队首（数组下标为0的位置）；

于是，我们可以通过多创建1个位置，让rear指向队尾元素的下一个位置——开辟k+1个位置，满足了存储k个数据的要求，又可以将数据个数为0和数据个数为1的情况区分开。

一般认为：rear +1 == front时，表示队列满了，但是当rear指向队尾时，rear + 1 就跑到队列外面了，为了解决这一问题，我们通过取模实现；

 //obj为实例化的对象 (obj->rear+1)%(obj->k+1)==obj->front

得出结论：F和R的下标相同时，表示队列是空的。

（三）函数接口的分析实现

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

MyCircularQueue* myCircularQueueCreate(int k) {//申请并初始化环形链表MyCircularQueue* que = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));que->a = (int*)malloc(sizeof(int)*(k+1));//多开辟一个空间que->front = 0;//指向队列头部que->rear = 0;//指向队列尾部的下一个元素que->k = k;return que;}

（2）isEmpty(): 检查循环队列是否为空。

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

（3）isFull(): 检查循环队列是否已满。

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

（4）enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//满了，返回假{return false;}//没有满，插入obj->a[obj->rear++] = value;obj->rear %= (obj->k+1);return true;}

（5）deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//空了，返回假{return false;}obj->front++;if(obj->front == obj->k+1)obj->front = 0;return true;//没有空，出数据}

（6）Front: 从队首获取元素。如果队列为空，返回 -1 。

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];}

（7）Rear: 获取队尾元素。如果队列为空，返回 -1 。

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

（8）C语言没有析构函数，需要手动释放循环队列

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

完~

未经作者同意禁止转载