【LeetCode刷题日志】622.设计循环队列

2023-11-21 15:04

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

  • 🎈个人主页:库库的里昂
  •  🎐C/C++领域新星创作者
  •  🎉欢迎 👍点赞✍评论⭐收藏
  • ✨收录专栏:LeetCode 刷题日志
  • 🤝希望作者的文章能对你有所帮助,有不足的地方请在评论区留言指正,大家一起学习交流!🤗

目录

1.题目描述

2.解题思路+代码实现

方法一:数组

思路及算法:

代码实现:

方法二:链表

思路及算法:

代码实现:


1.题目描述

OJ链接 【leetcode 题号: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 的范围内;
  • 请不要使用内置的队列库。

2.解题思路+代码实现

方法一:数组
思路及算法:

关于循环队列的概念可以参考:「循环队列」,我们可以通过一个数组进行模拟,通过操作数组的索引构建一个虚拟的首尾相连的环。在循环队列结构中,设置一个队尾 rear\textit{rear}rear 与队首 front\textit{front}front,且大小固定,结构如下图所示:

1

在循环队列中,当队列为空,可知front=rear;而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,假设队列使用的数组有capacity个存储空间,则此时规定循环队列最多只能有capacity−1个队列元素,当循环队列中只剩下一个空存储单元时,则表示队列已满。根据以上可知,队列判空的条件是front=rear,而队列判满的条件是 front=(rear+1) %capacity。 对于一个固定大小的数组,只要知道队尾rear与队首front,即可计算出队列当前的长度:

                                             (rear−front+capacity) % capacity

循环队列的属性如下:

  • elements:一个固定大小的数组,用于保存循环队列的元素。
  • capacity:循环队列的容量,即队列中最多可以容纳的元素数量。
  • front:队列首元素对应的数组的索引。
  • rear:队列尾元素对应的索引的下一个索引。

循环队列的接口方法如下:

  • MyCircularQueue(int k): 初始化队列,同时base数组的空间初始化大小为k+1。front,rear全部初始化为0。
  • enQueue(int value):在队列的尾部插入一个元素,并同时将队尾的索引rear更新为(rear+1)%capacity。
  • deQueue():从队首取出一个元素,并同时将队首的索引front更新为 (front+1) %capacity。
  • Front():返回队首的元素,需要检测队列是否为空。
  • Rear():返回队尾的元素,需要检测队列是否为空。
  • isEmpty():检测队列是否为空,根据之前的定义只需判断rear是否等于front。
  • isFull():检测队列是否已满,根据之前的定义只需判断front是否等于 (rear+1) % capacity。
代码实现:
typedef struct {int front;int rear;int capacity;int *elements;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));obj->capacity = k + 1;obj->rear = obj->front = 0;obj->elements = (int *)malloc(sizeof(int) * obj->capacity);return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if ((obj->rear + 1) % obj->capacity == obj->front) {return false;}obj->elements[obj->rear] = value;obj->rear = (obj->rear + 1) % obj->capacity;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->rear == obj->front) {return false;}obj->front = (obj->front + 1) % obj->capacity;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj->rear == obj->front) {return -1;}return obj->elements[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->rear == obj->front) {return -1;}return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % obj->capacity == obj->front;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->elements);free(obj);
}

复杂度分析

  • 时间复杂度:初始化和每项操作的时间复杂度均为 O(1)。
  • 空间复杂度:O(k),其中k为给定的队列元素数目。
方法二:链表
思路及算法:

我们同样可以用链表实现队列,用链表实现队列则较为简单,因为链表可以在O(1)时间复杂度完成插入与删除。入队列时,将新的元素插入到链表的尾部;出队列时,将链表的头节点返回,并将头节点指向下一个节点。

循环队列的属性如下:

  • head:链表的头节点,队列的头节点。
  • tail:链表的尾节点,队列的尾节点。
  • capacity:队列的容量,即队列可以存储的最大元素数量。
  • size:队列当前的元素的数量。
代码实现:
typedef struct {struct ListNode *head;struct ListNode *tail;int capacity;int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));obj->capacity = k;obj->size = 0;obj->head = obj->tail = NULL;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (obj->size >= obj->capacity) {return false;}struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));node->val = value;node->next = NULL;if (!obj->head) {obj->head = obj->tail = node;} else {obj->tail->next = node;obj->tail = node;}obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->size == 0) {return false;}struct ListNode *node = obj->head;obj->head = obj->head->next;  obj->size--;free(node);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj->size == 0) {return -1;}return obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->size == 0) {return -1;}return obj->tail->val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {for (struct ListNode *curr = obj->head; curr;) {struct ListNode *node = curr;curr = curr->next;free(node);}free(obj);
}

复杂度分析

  • 时间复杂度:初始化和每项操作的时间复杂度均为 O(1)。
  • 空间复杂度:O(k),其中k为给定的队列元素数目。

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



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

相关文章

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》:本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Qt spdlog日志模块的使用详解

《Qtspdlog日志模块的使用详解》在Qt应用程序开发中,良好的日志系统至关重要,本文将介绍如何使用spdlog1.5.0创建满足以下要求的日志系统,感兴趣的朋友一起看看吧... 目录版本摘要例子logmanager.cpp文件main.cpp文件版本spdlog版本:1.5.0采用1.5.0版本主要