【C语言】【LeetCode】循环队列

（一）题目描述

（二）数据结构的选择

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

正文开始：

（一）题目描述

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

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

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

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

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

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

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

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

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

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

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

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

所有的值都在 0 至 1000 的范围内；

操作数将在 1 至 1000 的范围内；

请不要使用内置的队列库。

（题目来源leetcode）

（二）数据结构的选择

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

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

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

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

在循环队列的题目要求中，指定了队列的数据个数为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);

}

完~

未经作者同意禁止转载

原文链接：https://blog.csdn.net/2301_79465388/article/details/136609318

【C语言】【LeetCode】循环队列

（一）题目描述

（二）数据结构的选择

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

相关推荐