设计循环队列——oj题622

2024-01-09 06:21:07

在这里插入图片描述在这里插入图片描述

.

个人主页:晓风飞
专栏:LeetCode刷题|数据结构|Linux
路漫漫其修远兮,吾将上下而求索



要做题目的点击这里–>队列oj题——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 的范围内;
请不要使用内置的队列库。
在这里插入图片描述

结构体定义

首先,我们定义一个名为 MyCircularQueue 的结构体来表示循环队列:

typedef struct {
    int *a;     // 队列中的元素数组
    int k;      // 队列的最大容量
    int front;  // 指向队列头部元素的指针
    int back;   // 指向队列尾部的下一个位置的指针
} MyCircularQueue;

在这个结构体中,a 是一个整型数组,用来存储队列中的元素。k 表示队列的最大容量,front 和 back 分别表示队列头部和尾部的指针。

队列的创建

队列的创建涉及到内存的分配和初始化:

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int *)malloc(sizeof(int)*(k+1));
    obj->front = obj->back = 0;
    obj->k = k;
    return obj;
}

这里,我们为队列结构体和队列数组分配内存。注意,我们为数组分配 k+1 的空间,因为在循环队列中,我们总是保留一个位置不使用,以区分队列为空和队列为满的状态。

基本操作

判断队列是否为空:

// 检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->back; // 如果 front 和 back 相等,则队列为空
}

frontback 相等时,队列为空。

判断队列是否已满:

// 检查队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back + 1) % (obj->k + 1) == obj->front; 
    // 如果 back 的下一个位置是 front,则队列已满
}

如果 back 的下一个位置是 front,则队列已满。

入队操作:

// 向队列中添加元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) // 如果队列已满,则无法添加元素
        return false;

    obj->a[obj->back] = value; // 在 back 的位置插入元素
    obj->back = (obj->back + 1) % (obj->k + 1); // 更新 back 的位置

在入队时,我们首先检查队列是否已满。如果不满,将元素放在 back 指向的位置,并更新 back 指针。

出队操作:

// 从队列中删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) // 如果队列为空,则无法删除元素
        return false;

    obj->front = (obj->front + 1) % (obj->k + 1); // 更新 front 的位置
    return true;
}

出队时,我们检查队列是否为空。如果不为空,则移动 front 指针。

获取队首和队尾元素:

// 获取队列头部的元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1
        return -1;
    return obj->a[obj->front]; // 返回队列头部的元素
}

// 获取队列尾部的元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1
        return -1;
    return obj->a[(obj->back - 1 + obj->k + 1) % (obj->k + 1)]; // 返回队列尾部的元素
}

这两个函数用于获取队首和队尾的元素。注意在获取队尾元素时,我们使用了模运算来正确处理环形结构。

内存释放

最后,当队列不再需要时,我们应该释放其占用的内存:

// 释放队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a); // 释放数组内存
    free(obj);    // 释放队列结构体内存
}

难点解释

难点1

在这里插入图片描述
这里我优化了代码,没有优化前是这样的:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) // 如果队列已满,则无法添加元素
        return false;

    obj->a[obj->back] = value; // 在 back 的位置插入元素
    obj->back++; // 更新 back 的位置
    obj->back %=(obj->k+1);//确保值在循环队列的有效范围内
    return true;
}

难点2

在这里插入图片描述

1.循环队列的容量:在这个循环队列的实现中,队列的实际容量是 k + 1,但为了区分空队列和满队列的状态,我们总是保留一个元素的空间不使用。所以,队列中最多可以存储 k 个元素。

2.队列尾部指针 (obj->back):这个指针指向队列中下一个元素将要存放的位置。当一个新元素被加入队列时,它被放置在 obj->back 指向的位置,然后 obj->back 会向前移动一个位置。

3.队列头部指针 (obj->front):这个指针指向队列中当前的第一个元素。当一个元素被移出队列时,obj->front 会向前移动一个位置。

4.判断队列是否已满:
(obj->back + 1) % (obj->k + 1) 计算出 obj->back 向前移动一个位置后的值,并使用模运算确保这个值在循环队列的有效范围内(即从 0 到 k)。


难点3

在这里插入图片描述

下面是这个表达式的详细解释:

1.obj->back: 指向队列中下一个插入元素的位置。

2.obj->back - 1: 因为 obj->back 指向的是下一个空位,所以队尾元素实际上是在 obj->back - 1 的位置。

3.由于队列是循环的,当 obj->back 为 0 时,obj->back - 1 会变成一个负数。为了正确地处理这种情况,我们加上 obj->k + 1,这保证了我们总是在一个正数的范围内操作。

4.(obj->back - 1 + obj->k + 1) % (obj->k + 1): 这个模运算确保了即使加上了 obj->k + 1,结果仍然是在队列大小的合法范围内。因此,这个表达式能够正确地处理循环队列的尾部元素访问,无论 obj->back 是在队列的开始位置还是任何其他位置

可以来我的github参观参观,看完整代码
路径点击这里–>oj622-设计循环队列

文章来源:https://blog.csdn.net/2203_75397752/article/details/135419162
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。