LeetCode——622设计循环队列

2024-06-15 08:49:18 浏览数 (2)

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。

https://leetcode.cn/problems/design-circular-queue/

1.题目

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

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

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

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

示例：

代码语言：javascript复制
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 的范围内；
  • 请不要使用内置的队列库。

2.解析

我们设计循环队列的关键是要有效地利用数组空间，并且能够处理队列满和队列空的情况。下面是一种使用数组实现循环队列的解法，其中back=k 1的含义是为了区分队列满和队列空的情况。

  • 首先，我们需要定义一个固定大小的数组a来存储队列元素，以及两个指针front和back来标记队列的头部和尾部。
  • 初始化时，将front和back都设置为0，表示队列为空。
  • 判断队列是否为空（isEmpty）：
    • 判断front是否等于back，如果相等，则表示队列为空，返回true;否则，返回false。
  • 判断队列是否已满（isFull）：
    • 判断（back 1）%k是否等于front，如果相等，则表示队列已满，返回true;否则，返回false。
  • 入队操作（enqueue）：
    • 首先，判断队列是否已满，即（back 1）%k是否等于front。如果相等，则表示队列已满，无法继续入队。
    • 如果队列未满，则将元素放入back指向的位置，并将back指针向后移动一位，即back=（back 1）%k。
  • 出队操作（dequeue）：
    • 首先，判断队列是否为空，即front是否等于back。如果相等，则表示队列为空，无法进行出队操作。
    • 如果队列不为空，则将front指向的元素出队，并将front指针向后移动一位，即front=（front 1）%k。
  • 获取队头元素（getFront）：
    • 首先，判断队列是否为空，即front是否等于back。如果相等，则表示队列为空，无法获取队头元素。
    • 如果队列不为空，则返回front指向的元素。

3.代码总结

1.构造器函数，用于创建一个指定长度的循环队列。

首先，通过malloc函数动态分配了一个MyCircularQueue结构体的内存空间，并将其地址赋给指针变量obj。

然后，通过malloc函数再次动态分配了一个整型数组的内存空间，并将其地址赋给指针变量obj->a。这个数组的长度为k 1，多分配了一个空间用于判断队列是否满的条件。

接着，将队列的头指针front和尾指针back都初始化为0。

最后，将k的值赋给队列的长度k。

最终，返回指向创建的循环队列的指针obj。

代码语言：javascript复制
MyCircularQueue* myCircularQueueCreate(int k)//构造器，设置队列长度为 k 
 {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k 1));
    obj->front=0;
    obj->back=0;
    obj->k=k;
    return obj;
}

2. 检查循环队列是否为空

函数的返回值是一个bool类型的值，表示循环队列是否为空。

如果循环队列为空，则返回true，否则返回false。

函数的实现是通过比较循环队列的front和back的值来判断循环队列是否为空。

如果它们相等，说明队列中没有元素，即队列为空，返回true；否则返回false。

代码语言：javascript复制
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//检查循环队列是否为空。
 {
    return obj->front==obj->back;
}

3. 检查循环队列是否已满

函数的返回值是一个bool类型的值，表示循环队列是否已满。如果循环队列已满，则返回true，否则返回false。

函数的实现是通过计算(back 1)%(k 1)与front的值是否相等来判断循环队列是否已满。

如果它们相等，说明队列已满，返回true；否则返回false。

这里使用了取模运算来实现循环队列的特性。由于循环队列的尾部和头部相连，所以需要将back的下一个位置计算为(back 1)%(k 1)，其中k为队列长度。如果这个值与front相等，说明队列已满。

代码语言：javascript复制
bool myCircularQueueIsFull(MyCircularQueue* obj)//检查循环队列是否已满。
 {
    return (obj->back 1)%(obj->k 1)==obj->front;
}

4. 向循环队列插入一个元素

函数的返回值是一个bool类型的值，表示插入操作是否成功。

如果插入成功，则返回true；否则返回false。

函数的实现首先通过调用myCircularQueueIsFull函数来检查循环队列是否已满。

如果队列已满，则表示无法插入新元素，直接返回false。

如果队列未满，则将value值插入到队列的obj->back位置，并且将obj->back的值加1。为了保证obj->back在[0, k]的范围内，需要使用取模运算进行处理，即obj->back%=(obj->k 1)。这样可以使back的值在超出队列长度时重新回到队列起始位置。

最后返回true表示插入成功。

代码语言：javascript复制
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//向循环队列插入一个元素。如果成功插入则返回真。
 {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;
    obj->back  ;
    obj->back%=(obj->k 1);//将 obj->back 除以 (obj->k 1) 的余数，然后将结果赋值给 obj->back。
    return true;
}

5. 循环队列中删除一个元素

函数的返回值是一个bool类型的值，表示删除操作是否成功。

如果删除成功，则返回true；否则返回false。

函数的实现首先通过调用myCircularQueueIsEmpty函数来检查循环队列是否为空。

如果队列为空，则表示无法执行删除操作，直接返回false。

如果队列不为空，就执行删除操作。

即将obj->front的值加1，然后使用取模运算来确保obj->front在[0, k]的范围内。

最后返回true表示删除成功。

代码语言：javascript复制
bool myCircularQueueDeQueue(MyCircularQueue* obj)//从循环队列中删除一个元素。如果成功删除则返回真。
 {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front  ;
    obj->front%=(obj->k 1);
    return true;

}

6.循环队列中获取队首元素

函数的返回值是一个int类型的值，表示队首元素。如果队列为空，则返回-1。

函数的实现首先通过调用myCircularQueueIsEmpty函数来检查循环队列是否为空。如果队列为空，则返回-1。

如果队列不为空，则直接返回obj->a[obj->front]，即队首元素的值。

代码语言：javascript复制
int myCircularQueueFront(MyCircularQueue* obj)//从队首获取元素。如果队列为空，返回 -1 。
 {
     if(myCircularQueueIsEmpty(obj))
     {
        return -1;
     }
     return obj->a[obj->front];
}

7.获取循环队列的队尾元素

  1. 首先判断队列是否为空，通过调用函数myCircularQueueIsEmpty(obj)来判断。如果队列为空，则返回-1。
  2. 如果队列不为空，使用取模运算(obj->back obj->k)%(obj->k 1)来计算队尾元素的下标。这里obj->back表示队尾元素的下标，obj->k表示队列的容量减1。这样做是为了实现循环队列的封装。
  3. 返回队尾元素obj->a[(obj->back obj->k)%(obj->k 1)]，即对应下标位置上的元素值。
代码语言：javascript复制
int myCircularQueueRear(MyCircularQueue* obj)//: 获取队尾元素。如果队列为空，返回 -1 。
 {
     if(myCircularQueueIsEmpty(obj))
     {
        return -1;
     }
     return obj->a[(obj->back obj->k)%(obj->k 1)];
}

8.释放循环队列的内存空间

首先，通过调用free(obj->a)来释放存储队列元素的数组的内存空间。obj->a指向数组的起始地址，free(obj->a)将释放该内存空间。

然后，通过调用free(obj)来释放存储循环队列结构体的内存空间。obj指向循环队列结构体的起始地址，free(obj)将释放该内存空间。

通过这两个free()函数的调用，可以确保循环队列所占用的所有内存空间都被释放，防止内存泄漏。

代码语言：javascript复制
void myCircularQueueFree(MyCircularQueue* obj)
 {
    free(obj->a);
    free(obj);
}

9.总的代码

代码语言：javascript复制
typedef struct 
{
    int *a;
    int front;
    int back;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k)//构造器，设置队列长度为 k 
 {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k 1));
    obj->front=0;
    obj->back=0;
    obj->k=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)//检查循环队列是否为空。
 {
    return obj->front==obj->back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)//检查循环队列是否已满。
 {
    return (obj->back 1)%(obj->k 1)==obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//向循环队列插入一个元素。如果成功插入则返回真。
 {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;
    obj->back  ;
    obj->back%=(obj->k 1);//将 obj->back 除以 (obj->k 1) 的余数，然后将结果赋值给 obj->back。
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)//从循环队列中删除一个元素。如果成功删除则返回真。
 {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front  ;
    obj->front%=(obj->k 1);
    return true;

}

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

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



void myCircularQueueFree(MyCircularQueue* obj)
 {
    free(obj->a);
    free(obj);
}
函数 设计 指针 leetcode 队列

0 人点赞