【LeetCode&数据结构】设计循环队列

用户11831438

发布于 2025-12-30 12:32:39

840

一、循环队列

什么是循环队列？

一个循环队列需满足一下条件： 1、队头删数据，队尾入数据 2、给定固定的空间，使用过程中不可以扩容 3、环形队列满了，不能继续插入数据（即插入数据失败）

举个例子：

比如说一家餐厅只有6个桌子，一次性只能招待6桌客人，如果某一天6桌全坐满了，现在又有来了一桌，如果这桌客人还想继续用餐，只能等其中的一桌客人离开，才能用餐。

ok，总结一下

假设现在有6个空间，只能放6个数据，如果想继续插数据，只能删除数据；只有有空的空间，才能够插入数据，空或者没满可以插入数据

二、环形队列的结构

在队列的学习中，我们使用数组来实现队列，那环形队列还是用数组来实现的吗？

环形队列可以使用数组来实现，也可以使用循环链表来实现。那我们该选哪一个呢？

使用数组，初始化和结构相对简单！！！

三、实现循环队列

当rear越界时，我们需要将rear返回0开始，rear=rear%k，此时rear==front

我们发现，队列为空和队列满了的条件竟然是一样的，那我们该如何区分环形队列是空还是满呢？要求在环形队列中不额外增加计数器成员来保存队列中有效数据个数。

ok，我们接着看：

通过上图，我们就知道队列满时的条件为：（rear+1）%（k+1）== front

既然我们已经知道了队列满时的条件，那这里有个问题：队列已经满了，那么我们该如何继续插入数据呢？

3.1 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

3.1.1 题目描述

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

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

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

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

我们需要自己写出上图中的所有代码！！！

3.1.2 循环队列结构

通过上面的分析，我们知道循环队列使用数组来实现的，并且有两个指针，一个front为头，一个rear为尾，那这些成员足够了吗？

通过对题目给出的代码来看，我们还应该设置一个成员用来记录数据容量k

代码

//队列结构
typedef struct {
    int* arr;//存储数据的数组
    int front;//指向头
    int rear;//指向尾
    int capacity;//数据容量大小
} MyCircularQueue;

3.1.2 循环队列的创建

需要我们自己向空间申请一个队列结构，并返回地址。

代码

//申请队列结构空间
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->arr=(int*)malloc(sizeof(int)*(k+1));
    pq->front=0;
    pq->rear=0;
    pq->capacity=k;
    return pq;
}

现在我们已经有了一个循环队列，那我们是不是就可以直接往这里面进行插入和删除数据的操作？ 当然不可以，在进行插入之前，我们首先要判断队列是否满，如果满，我们不能进行插入的操作；如果队列为空，我们不能进行删除数据的操作。

3.1.3 判断队列是否为空

我们发现当队列为空时，front==rear！！！

如果相等，返回true；不相等，返回false

3.1.4 判断队列是否满

我们发现，队列满时，（rear+1）%（k+1）==front！！！

3.1.5 入数据

如果队列没有满，我们在rear处入数据，入一个数据，rear++。

那有没有可能rear越界了呢？

ok，我们可以写出代码

//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //判断队列是否满了
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->arr[obj->rear++]=value;
    //防止rear出界
    obj->rear%=(obj->capacity+1);
    return true;
}

3.1.6 出数据

如果队列不为空，直接front++就可以了。

那front会不会出界呢？如果会出界，那么该怎么办？

代码

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    ++obj->front;
    //front也会出界
    obj->front%=(obj->capacity+1);
    return true;
}

3.1.7 从队首获取元素

当队列不为空时，才能从队首获取元素；如果队列为空，不能从队首获取元素。

代码

//从队首获取元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arr[obj->front];
}

3.1.8 获取队尾元素

代码

//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //找rear位置的前一个位置
    int prev=obj->rear-1;
    if(obj->rear==0)
    {
        prev=obj->capacity;
    }
    return obj->arr[prev];
}

3.1.9 销毁

销毁的操作就是看哪些空间是我们自己主动向操作系统申请的，自己主动申请的需要销毁！！！

代码

//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    if(obj->arr)
    {
        free(obj->arr);
    }
    free(obj);
    obj=NULL;
}

3.2 完整代码

//队列结构
typedef struct {
    int* arr;//存储数据的数组
    int front;//指向头
    int rear;//指向尾
    int capacity;//数据容量大小
} MyCircularQueue;
//申请队列结构空间
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->arr=(int*)malloc(sizeof(int)*(k+1));
    pq->front=0;
    pq->rear=0;
    pq->capacity=k;
    return pq;
}
//检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}
//检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->front==(obj->rear+1)%(obj->capacity+1);
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //判断队列是否满了
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->arr[obj->rear++]=value;
    //防止rear出界
    obj->rear%=(obj->capacity+1);
    return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    ++obj->front;
    //front也会出界
    obj->front%=(obj->capacity+1);
    return true;
}
//从队首获取元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arr[obj->front];
}
//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //找rear位置的前一个位置
    int prev=obj->rear-1;
    if(obj->rear==0)
    {
        prev=obj->capacity;
    }
    return obj->arr[prev];
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    if(obj->arr)
    {
        free(obj->arr);
    }
    free(obj);
    obj=NULL;
}

运行一下