设计循环队列——oj题622

2024-01-06 00:44
文章标签 设计 队列 循环 oj 622

本文主要是介绍设计循环队列——oj题622,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

.

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


文章目录

  • 题目要求:
    • 应该支持如下操作:
    • 示例:
    • 提示:
  • 结构体定义
  • 队列的创建
  • 基本操作
    • 判断队列是否为空:
    • 判断队列是否已满:
    • 入队操作:
    • 出队操作:
    • 获取队首和队尾元素:
    • 内存释放
  • 难点解释
    • 难点1
    • 难点2
    • 难点3


要做题目的点击这里–>队列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)) // 如果队列为空,返回 -1return -1;return obj->a[obj->front]; // 返回队列头部的元素
}// 获取队列尾部的元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1return -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-设计循环队列

这篇关于设计循环队列——oj题622的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/574667

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi