设计循环队列——oj题622

.

个人主页：晓风飞

专栏：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 相等，则队列为空
}

当 front 和 back 相等时，队列为空。

判断队列是否已满：

// 检查队列是否已满
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-设计循环队列

代码007普通

打赏 收藏 海报 链接