数据结构学习笔记 1-2队列概述及LeetCode真题图解(Java)

云惠网小编 2022年1月16日23:17:44
评论
3006字阅读10分1秒
摘要

喜欢该类型文章可以给博主点个关注,博主会持续输出此类型的文章,知识点很全面,再加上LeetCode的真题练习,每一个LeetCode题解我都写了注释,比较适合新手入门数据结构与算法,后续也会更新进阶的文章。1-2 线程池与任务队列(Task-Queue)队列基础知识排队就是简单的一个队列。最基础的操作:入队 出队,从尾进(push),从头出(pop),先进先出。队列基于数组的实现方式:head为队列头,tail为队列尾。队列的出队怎么实现呢?如图:我们发现head从指向0变为指向.

广告也精彩

根据题解注释来看代码。

LeetCode题解:代码实现

所以我们可以在线程池中创建一个任务队列,放不下的话咱们就排个队,新来的任务我们都放进队列里面,这个队列在线程池里充当缓冲区一样的角色。

这题用了三层封装,首先最底层用链表封装一个队列,然后创建两个队列来封装这个前中后队列。

基础数组实现一个循环队列。

image-20220110210235157

image-20220110211538469

排队就是简单的一个队列。

最基础的操作:入队 出队,从尾进(push),从头出(pop),先进先出。

image-20220110211656967

但是这个线程池还是会有一些问题的,我们四个线程分别都在执行任务,那这时候又来了一个任务,我们没有多余的线程了,这时候看起来我们只能将它拒之门外,但这样明显是很不友好的。

LeetCode题解:代码实现

队列的两种实现方式:数组,链表

队列大概分为这几种:普通队列,双端队列,循环队列,循环双端队列,前中后队列。

队列在工程中的应用大部分都是作为一个缓冲层。

队列在后续章节的搜索会用到,它是广搜bfs的一个辅助工具。

队列的实现很简单,但越简单也越重要,它是很多高级数据结构底层的实现。

LeetCode641.设计循环双端队列

CPU的超线程技术就是采用的队列,想象一下我们买cpu的时候,有双核、四核、八核,我们每一个核心是根据队列来处理任务的,我们的操作系统把相应的计算任务塞到cpu里面去,cpu从第一个任务开始处理,处理完了将任务返回,这个cpu管道的外在表现就是一个队列。

LeetCode真题

队列基于数组的实现方式:

image-20220111174640289

image-20220111173928289

队列的插入删除对应着入队出队

小trick

尽量使用offer()方法添加元素,使用poll()方法移除元素,add()remove()方法在失败的时候会抛出异常。

队列的出队怎么实现呢?如图:

LeetCode题解:代码实现

难度:mid

本题的队列不仅仅可以从前后插入,在中间也可以插入。

经典面试题—队列的封装与使用

假如我现在想创建一个线程,创建好了之后我们又想再创建三个,然后又想把刚创建好的两个线程删掉,大家想象一下,如果我们的进程遇到了这样的一个场景,我们需要频繁的申请和销毁线程,线程处理完一个事件立刻就销毁了,但是没过一会这个线程就又有了一个任务,所以又要创建一个线程再处理,这也是我们多线程非常常见的一个问题,这个问题影响我们整个系统的性能,为什么呢?因为我们线程的创建是非常重量级的一个行为,它不像我们 int 一个变量特别特别的快,它是一个很花时间,很慢的一个操作,它带来了很大的上下文切换,我们应该尽量的避免多线程大量的申请和销毁,那我们该怎样避免呢?我们可以将我们的线程池化,如图:

image-20220110202846847

1-2 线程池与任务队列(Task-Queue)


数组中我们想要删除1,我们把1拿掉之后,2,3,4,5各往前挪一下,这样是非常麻烦的,但队列就可以很巧妙的解决这个问题,我们没有必要真正把1这个内容删掉,只需要让我们的head + 1就可以了。

image-20220110210630304


以上这三题考验的都是我们的编码能力。

LeetCodet题解:代码实现

以上都是基于数组实现的队列,如果是基于链表实现队列的话,它还会有循环队列这个东西了吗?我们就不需要这个循环了,只要内存够用,tail可以无限的往下移动,head之前不要的元素直接将它free掉,链表实现队列有优点,数组实现队列也有优点,可以看我上一篇的文章,链表和数组的结构性能对比,所以选型要根据我们的实际需求来选。

LeetCode1670.设计前中后队列

跟上题类似,同样基于数组实现,但是队列是双端队列,两头都可以插入和删除元素,直接看题解。

我们发现head从指向0变为指向1了,tail从指向5变为指向4了,也就是说head指哪,哪就是头,tail指哪,哪就是尾。

喜欢该类型文章可以给博主点个关注,博主会持续输出此类型的文章,知识点很全面,再加上LeetCode的真题练习,每一个LeetCode题解我都写了注释,比较适合新手入门数据结构与算法,后续也会更新进阶的文章。

LeetCode622.设计循环队列

image-20220112150614999

image-20220111165638791

LeetCode933.最近的请求次数

这样我们就将10插入进去了,同时形成了循环队列,当我们再插入11和12的时候,此时tailhead指向了同一个位置,当tail = head时,称为我们的队列满了,虽然说我们的队列可以循环利用,但头跟尾指到一起的时候,队列就是满的状态。

我们可以创建两个队列,并用链表来做,在前面我们说了,如果遇到队列中元素频繁的插入和删除,我们用链表是更好实现的。

我们维护两个双向队列,一个队列A,一个队列B,如果想从头插入元素,我们就插入到A中,如果从尾插入元素,我们就插入到B中,那么中间的插入和删除怎么办呢?如果A和B的大小相等,元素都是2个的时候,我们中间的插入和删除操作都放在A的尾部进行,A的尾部就相当于中间位,但我们还要保证A和B大小的平衡性,A和B的大小相等我们取不到中间位置时,虽然说从中间插入到A里面了,但我们之后的插入就一定要插入在B的头部,保证A和B的差值不能超过1。

队列的假溢出

难度:mid

我们想要插入一个元素,直接让tail往后移一位就好了。

前面都是用数组来设计队列,这题我们用链表来封装队列。

image-20220112151431131

image-20220112152112273

创建一个线程池,让它代替我们管理这些线程,如果我想要用这个线程,就从你这里拿,我用完了再把线程给你,放在你这里保管着,不销毁,这样就避免了线程的频繁申请和销毁的过程,在程序当中我们用这样一个技术来管理我们这些”昂贵的东西“。

对循环队列的概念有点模糊请移步上面看基础知识。

队列在工业中最常用的作用就是缓冲

难度:mid

难度:easy

image-20220111172502449

队列的典型应用场景

我们来使用一下java中自带的队列:Queue接口,LinkedList类实现了Queue接口。

head为队列头,tail为队列尾。

队列的入队怎么实现呢?如图

image-20220110202817568

image-20220111174449217

返回在[t - 3000, t]的请求数,根据我画的图来看,[1 - 3000, 1]也就是[0, 1]只有1这个值,所以返回1;[100 - 3000, 100]也就是[0, 100]中有1和100,所以返回2;[3001 - 3000, 3001]也就是[1, 3001]中有1,100,3001,所以返回3;[3002 - 3000, 3002]也就是[2, 3002]中有100,3001,3002,所以返回3;最后的区间中,1这个值过期了,所以他不在区间内,我们发现1是最先请求的,也是最先过期的,这样的模式跟我们的队列很类似,本题:先请求,先过期,队列:先进,先出,所以我们可以用队列来解决这题。
image-20220115155043001

代码很简单,但对比最简单的队列加了一个防止溢出的取余操作,直接看我的题解即可。

当我们想插入一个元素的时候,tail指向了9的后面,但我数组的length = 9,继续插入的话就溢出了,在这个最普通的队列,我们称之为假溢出,为什么叫假溢出?虽然说tail没有办法往后指了,但是前面删除掉的 1,2,3 的位置是可以用的,如果head往后移一位,那前面的位置我们就再也不用它了吗?这其实是一种空间上的浪费,你已经申请它了,用完它就扔掉了,这样是不允许的。前面的位置我们可以循环利用,在数组中它的第0位还是1,第1位还是2,但是在逻辑层面我们认为下标 0,1,2 这三位已经不用了,我们把它看做为空,让tail指向数组下标为0的位置,如图:

队列基础知识

总结


本文转自 https://blog.csdn.net/weixin_53407527/article/details/122500695

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论