前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏队列是针对线性表进行了封装和限制核心操作有三个入队列出队列获取队首元素队列的特点是“先进先出”队列的底层实现有两种链表和数组这篇博客会分别模拟这两种底层实现同时搭配算法题的练习来学习队列这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1队列简介队列跟栈是比较类似的只不过栈是一端进一端出所以先进的最后才能出而队列有两端队尾进队首出队列是先进先出在实际开发中队列的使用是远远多于栈的因为队列中的元素进出有“先来后到”的顺序有些耗时比较长的操作没办法一口气处理完需要按照顺序一个一个处理为了保证处理的顺序不乱就可以把数据放到队列中队列在标准库中的实现就是QueueQueue是一个接口是没办法直接创建实例的只能创建其他类来实现接口如下图add方法和offer方法就是入队列一般使用offer因为听起来比较吉利队首元素入队列方法在传入元素类型不匹配时会抛出异常元素出队列就是remove和poll方法并且返回该元素element和peek是取出队首元素当队列为空时remove和element方法会抛出异常poll方法和peek方法会返回null一般使用的是不抛出异常的版本就是使用poll和peek创建接口时实现类可以是LinkedList那为什么用LinkedList就可以了呢按ctrl键点入LinkedList看一下LinkedList实现了Deque接口Deque是双端队列两头都能进两头都能出而Deque接口又继承了Queue接口所以LinkedList就相当于是实现了Queue接口ArrayList是没有实现Queue接口的不能作为Queue的实现类但是队列是完全可以基于数组来实现的下面博客会聊到创建一个队列用offer在里面添加元素当列表为空时使用poll会返回null使用remove则会直接报错importjava.util.LinkedList;importjava.util.Queue;publicclassTest{publicstaticvoidmain(String[]args){QueueIntegerqueuenewLinkedList();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.remove());}在这里插入代码片}判定栈是否为空就可以使用empty()或者isempty()方法但是队列是没有这些方法的一般是用peek取出队首元素如果返回值为null就说明队列为空if(queue.peek()null){}2队列模拟实现基于链表我们模拟实现一个自己的队列MyQueue基于单链表来实现存储的元素类型为String首先搞一个Node类表示节点publicclassNode{publicStringval;publicNodenext;publicNode(Stringval){this.valval;this.nextnull;}}用链表模拟实现队列元素入队列就进行尾插元素出队列就进行头删读取队首元素就返回头节点val即可offer方法就是先判断下head是否为null如果不为null就直接在tail后插入新节点publicvoidoffer(Stringval){NodenewNodenewNode(val);if(headnull){headnewNode;tailnewNode;return;}tail.nextnewNode;tailnewNode;}再重写下toString方法利用字符串拼接写好后就可以在main方法中测试offer方法了OverridepublicStringtoString(){StringBuilderstringBuildernewStringBuilder();stringBuilder.append([);Nodecurhead;while(cur!null){stringBuilder.append(cur.val);if(cur.next!null){stringBuilder.append(,);}curcur.next;}stringBuilder.append(]);returnstringBuilder.toString();}publicclassTest{publicstaticvoidmain(String[]args){MyQueuemyQueuenewMyQueue();myQueue.offer(aaa);myQueue.offer(bbb);myQueue.offer(ccc);System.out.println(myQueue);}}poll方法就是删除头部元素并返回元素值head为null时就返回nullhead不为null时就head head.next即可如果删除后head等于null了要把tail也改为nullpublicStringpoll(){if(headnull){returnnull;}Stringvalhead.val;headhead.next;if(headnull){tailnull;}returnval;}peek方法就只需要判断下head是不是null再返回head.val即可publicStringpeek(){if(headnull){returnnull;}returnhead.val;}还可以再扩展下写个isEmpty()和size()方法publicbooleanisEmpty(){returnheadnull;}publicintsize(){intsize0;for(Nodecurhead;head!null;headhead.next){size;}returnsize;}3数组队列原理日常开发中创建队列更多还是基于数组来实现因为数组中元素出入的效率就比较高虽然ArrayList不能是实现类但是我们可以用ArrayDeque作为实现类QueueIntegerqueuenewArrayDeque();这个ArrayDeque也可以作为双端队列的实现类双端队列有addLastaddFirstremoveLastremoveFirst方法DequeIntegerdequenewArrayDeque();那队列是如何用数组来实现的呢我们画图来分析下原理首先创建出一个空的数组创建两个引用head和tail当head等于tail时队列为空当元素入队列时元素存到tail指向的位置tail再往后移动一位那元素出队列时应该如何解决呢如果把数组后面的元素都往前移动一格那时间复杂度就是O(N)这样效率是很低的那能不能元素出队列时把head往后移动一位并不真正的删除元素只是把之前head指向的这块元素标记为无效按照这种思想那tail到达数组末尾的时候就并不意味着队列已经满了前面可能又有一大片的空白区域就可以让tail拐到前面继续存储数据数组队列当作环形来看会更好理解一些铁汁们可以自己画图模拟下初始时head和tail都在下标0处元素入队列时tail往后顺时针移动元素出队列时head顺时针移动如下图两个元素出队列数组中的元素实际上是没有删除的只是标记为无效了后续元素入队列直接把这块这之前的值给覆盖掉图中为了美观就把元素删除了接着一直往队列里面加入元素当head和tail重合时就说明队列已经满了当队列为空时head和tail也是重合的所以靠head和tail重合是无法判断出队列满了那想要判断有两个办法直接浪费一个格子当head走到tail前面一个格子的位置时就说明队列已经满了还有一种更简单直接的做法就是引入一个size变量表示队列中元素的个数如果size为0队列就为空如果size等于arr.length那数组就为满数组这种方案相比链表有三大优点使用数组时的效率要高于链表数组中元素入队列和出队列就是简单的head和tail而链表再修改应用的指向时还涉及到一个间接寻址操作需要先读取到引用的值得到地址再根据地址来访问内存空间使用数组对于队列中元素个数的上限是可控的对于链表来说可以一直往里面插入元素如果代码出现了bug可能不会报错就是一直插入直到把内存耗尽结果就可能会造成整个程序的瘫痪而对于数组版本如果不去自动扩容的话出现类似的问题就能在入队列时及时报错把问题影响范围缩小数组版本的空间利用率更高因为链表版本还要保存next引用4队列模拟实现基于数组接下来我们就基于数组来模拟实现队列存储元素类型为String首先创建个数组以及head、tail、size这些属性构造方法无参的默认数组长度为1000有参的可以自己指定数组长度publicclassMyQueueByArray{privateString[]arrnull;privateinthead0;privateinttail0;privateintsize0;publicMyQueueByArray(){arrnewString[1000];}publicMyQueueByArray(intcapacity){arrnewString[capacity];}}offer方法首先判断下队列是否已经满了也就是比较size是否等于length队列满了可以选择扩容这样就没有控制元素上限的作用了也可以选择直接抛出异常publicvoidoffer(Stringval){if(sizearr.length){return;}arr[tail]val;tail;if(tailarr.length){tail0;}size;}poll方法首先判断下队列是否为空如果为空就返回null不为空就返回arr[head]size- -head如果head等于arr.length就让head等于0移动到数组头部publicStringpoll(){if(size0){returnnull;}Stringvalarr[head];head;size--;if(headarr.length){head0;}returnval;}重写toString方法创建一个拼接字符串让cur从head的位置开始往后移动每次都把cur的元素添加到拼接字符串中直到拼接字符串中添加了size个元素当cur等于arr.length时就让cur等于0回到数组开头OverridepublicStringtoString(){StringBuilderstringBuildernewStringBuilder();stringBuilder.append([);intcurhead;for(inti0;isize;i){stringBuilder.append(arr[cur]);cur;if(curarr.length){cur0;}if(isize-1){stringBuilder.append(,);}}stringBuilder.append(]);returnstringBuilder.toString();}peek方法就是当队列不为空时就直接返回arr[head]publicStringpeek(){if(size0){returnnull;}returnarr[head];}这里聊个题外话在前面的offer方法中我们写的是先让tail接着判断tail是否等于arr.length如果等于arr.length了再让tail 0但是铁汁们可能看到过直接求余数的写法这个写法还是挺流行的tail;if(tailarr.length){tail0;}tail(tail1)%arr.length;tail 1的意思就是tail再对arr.length进行取模运算当tail 1等于arr.length的时候取模后结果会等于0其他情况取模后结果还是tail 1这个写法可能看起来比较牛一行代码就搞定了但是这样写真的比第一种写法好吗评价写法好不好看两个方面1对于开发效率的影响是否可读性好是否容易理解是否好维护 2对于运行效率的影响也就是程序的执行效率这个写法从可读性上看是不如第一种写法的不考虑编译器优化的话第一种写法的执行效率也更高第一种写法在大部分情况下cpu进行一次赋值操作进行一次比较操作即可(tail等于arr.length时才会进行两次赋值操作) 而第二种写法每次都会有赋值操作和取模操作而取模指令的效率是低于比较指令的编译器在执行第二种写法时不会真的去进行取模运算还是会优化成第一种写法5用队列实现栈力扣链接这个题目没啥实用价值就是纯考察我们的代码能力要求使用两个队列来模拟一个栈的功能队列的特点是先进先出栈的特点是先进后出可以这样搞A和B两个队列入栈时把元素加到A队列中元素需要出栈时就把队列A中的元素逐个取出来加到队列B中队列A中剩最后一个元素时直接删除即可接着交换下队列A和队列B的指向后面进行入栈操作还是把元素加到队列A中去再额外写个swap方法先创建个tmp引用把引用A保存下来接着再进行交换classMyStack{privateQueueIntegerAnewArrayDeque();privateQueueIntegerBnewArrayDeque();publicMyStack(){}publicvoidpush(intx){A.offer(x);}publicintpop(){while(A.size()1){intnA.poll();B.offer(n);}intresultA.poll();swap();returnresult;}publicinttop(){while(A.size()1){intnA.poll();B.offer(n);}intresultA.poll();B.offer(result);swap();returnresult;}publicbooleanempty(){returnA.isEmpty();}publicvoidswap(){QueueIntegertmpA;AB;Btmp;}}6用栈实现队列力扣链接用两个栈来模拟实现队列也是让元素再两个栈之间来回导两个栈A和B入队列时把元素添加到A栈中需要删除元素时再把元素从栈中导到B中这时候B的队首元素就是要删除或者要取出的元素但是这个题目如果再交换A和B的引用就不行了因为在A中先入队列的元素是在栈底而在B中先入队列的元素却是在栈底如果交换引用顺序就乱掉了因此还要再把B中的元素再导入到A中确保原来的顺序不变后面入队列就还是加到A中规则就是先入的在栈底后入的在栈顶classMyQueue{privateStackIntegerAnewStack();privateStackIntegerBnewStack();publicMyQueue(){}publicvoidpush(intx){A.push(x);}publicintpop(){while(A.size()1){B.push(A.pop());}intresultA.pop();while(B.size()0){A.push(B.pop());}returnresult;}publicintpeek(){while(A.size()0){B.push(A.pop());}intresultB.peek();while(B.size()0){A.push(B.pop());}returnresult;}publicbooleanempty(){returnA.isEmpty();}}结语队列在数据结构中相对来说是比较简单的因为只有三个操作用数组和链表模拟实现下自己的队列就能很好的掌握队列的用法下篇数据结构博客会解析二叉树二叉树的知识点相对来说就比较繁杂大量题目依赖递归也涉及到一些算法思想预计会用5篇博客来解析二叉树欢迎铁汁们来观看后续的二叉树博客以上就是今天的所有内容啦完结撒花
队列的使用，基于数组和基于链表的模拟实现，题目练习
前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏队列是针对线性表进行了封装和限制核心操作有三个入队列出队列获取队首元素队列的特点是“先进先出”队列的底层实现有两种链表和数组这篇博客会分别模拟这两种底层实现同时搭配算法题的练习来学习队列这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1队列简介队列跟栈是比较类似的只不过栈是一端进一端出所以先进的最后才能出而队列有两端队尾进队首出队列是先进先出在实际开发中队列的使用是远远多于栈的因为队列中的元素进出有“先来后到”的顺序有些耗时比较长的操作没办法一口气处理完需要按照顺序一个一个处理为了保证处理的顺序不乱就可以把数据放到队列中队列在标准库中的实现就是QueueQueue是一个接口是没办法直接创建实例的只能创建其他类来实现接口如下图add方法和offer方法就是入队列一般使用offer因为听起来比较吉利队首元素入队列方法在传入元素类型不匹配时会抛出异常元素出队列就是remove和poll方法并且返回该元素element和peek是取出队首元素当队列为空时remove和element方法会抛出异常poll方法和peek方法会返回null一般使用的是不抛出异常的版本就是使用poll和peek创建接口时实现类可以是LinkedList那为什么用LinkedList就可以了呢按ctrl键点入LinkedList看一下LinkedList实现了Deque接口Deque是双端队列两头都能进两头都能出而Deque接口又继承了Queue接口所以LinkedList就相当于是实现了Queue接口ArrayList是没有实现Queue接口的不能作为Queue的实现类但是队列是完全可以基于数组来实现的下面博客会聊到创建一个队列用offer在里面添加元素当列表为空时使用poll会返回null使用remove则会直接报错importjava.util.LinkedList;importjava.util.Queue;publicclassTest{publicstaticvoidmain(String[]args){QueueIntegerqueuenewLinkedList();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.remove());}在这里插入代码片}判定栈是否为空就可以使用empty()或者isempty()方法但是队列是没有这些方法的一般是用peek取出队首元素如果返回值为null就说明队列为空if(queue.peek()null){}2队列模拟实现基于链表我们模拟实现一个自己的队列MyQueue基于单链表来实现存储的元素类型为String首先搞一个Node类表示节点publicclassNode{publicStringval;publicNodenext;publicNode(Stringval){this.valval;this.nextnull;}}用链表模拟实现队列元素入队列就进行尾插元素出队列就进行头删读取队首元素就返回头节点val即可offer方法就是先判断下head是否为null如果不为null就直接在tail后插入新节点publicvoidoffer(Stringval){NodenewNodenewNode(val);if(headnull){headnewNode;tailnewNode;return;}tail.nextnewNode;tailnewNode;}再重写下toString方法利用字符串拼接写好后就可以在main方法中测试offer方法了OverridepublicStringtoString(){StringBuilderstringBuildernewStringBuilder();stringBuilder.append([);Nodecurhead;while(cur!null){stringBuilder.append(cur.val);if(cur.next!null){stringBuilder.append(,);}curcur.next;}stringBuilder.append(]);returnstringBuilder.toString();}publicclassTest{publicstaticvoidmain(String[]args){MyQueuemyQueuenewMyQueue();myQueue.offer(aaa);myQueue.offer(bbb);myQueue.offer(ccc);System.out.println(myQueue);}}poll方法就是删除头部元素并返回元素值head为null时就返回nullhead不为null时就head head.next即可如果删除后head等于null了要把tail也改为nullpublicStringpoll(){if(headnull){returnnull;}Stringvalhead.val;headhead.next;if(headnull){tailnull;}returnval;}peek方法就只需要判断下head是不是null再返回head.val即可publicStringpeek(){if(headnull){returnnull;}returnhead.val;}还可以再扩展下写个isEmpty()和size()方法publicbooleanisEmpty(){returnheadnull;}publicintsize(){intsize0;for(Nodecurhead;head!null;headhead.next){size;}returnsize;}3数组队列原理日常开发中创建队列更多还是基于数组来实现因为数组中元素出入的效率就比较高虽然ArrayList不能是实现类但是我们可以用ArrayDeque作为实现类QueueIntegerqueuenewArrayDeque();这个ArrayDeque也可以作为双端队列的实现类双端队列有addLastaddFirstremoveLastremoveFirst方法DequeIntegerdequenewArrayDeque();那队列是如何用数组来实现的呢我们画图来分析下原理首先创建出一个空的数组创建两个引用head和tail当head等于tail时队列为空当元素入队列时元素存到tail指向的位置tail再往后移动一位那元素出队列时应该如何解决呢如果把数组后面的元素都往前移动一格那时间复杂度就是O(N)这样效率是很低的那能不能元素出队列时把head往后移动一位并不真正的删除元素只是把之前head指向的这块元素标记为无效按照这种思想那tail到达数组末尾的时候就并不意味着队列已经满了前面可能又有一大片的空白区域就可以让tail拐到前面继续存储数据数组队列当作环形来看会更好理解一些铁汁们可以自己画图模拟下初始时head和tail都在下标0处元素入队列时tail往后顺时针移动元素出队列时head顺时针移动如下图两个元素出队列数组中的元素实际上是没有删除的只是标记为无效了后续元素入队列直接把这块这之前的值给覆盖掉图中为了美观就把元素删除了接着一直往队列里面加入元素当head和tail重合时就说明队列已经满了当队列为空时head和tail也是重合的所以靠head和tail重合是无法判断出队列满了那想要判断有两个办法直接浪费一个格子当head走到tail前面一个格子的位置时就说明队列已经满了还有一种更简单直接的做法就是引入一个size变量表示队列中元素的个数如果size为0队列就为空如果size等于arr.length那数组就为满数组这种方案相比链表有三大优点使用数组时的效率要高于链表数组中元素入队列和出队列就是简单的head和tail而链表再修改应用的指向时还涉及到一个间接寻址操作需要先读取到引用的值得到地址再根据地址来访问内存空间使用数组对于队列中元素个数的上限是可控的对于链表来说可以一直往里面插入元素如果代码出现了bug可能不会报错就是一直插入直到把内存耗尽结果就可能会造成整个程序的瘫痪而对于数组版本如果不去自动扩容的话出现类似的问题就能在入队列时及时报错把问题影响范围缩小数组版本的空间利用率更高因为链表版本还要保存next引用4队列模拟实现基于数组接下来我们就基于数组来模拟实现队列存储元素类型为String首先创建个数组以及head、tail、size这些属性构造方法无参的默认数组长度为1000有参的可以自己指定数组长度publicclassMyQueueByArray{privateString[]arrnull;privateinthead0;privateinttail0;privateintsize0;publicMyQueueByArray(){arrnewString[1000];}publicMyQueueByArray(intcapacity){arrnewString[capacity];}}offer方法首先判断下队列是否已经满了也就是比较size是否等于length队列满了可以选择扩容这样就没有控制元素上限的作用了也可以选择直接抛出异常publicvoidoffer(Stringval){if(sizearr.length){return;}arr[tail]val;tail;if(tailarr.length){tail0;}size;}poll方法首先判断下队列是否为空如果为空就返回null不为空就返回arr[head]size- -head如果head等于arr.length就让head等于0移动到数组头部publicStringpoll(){if(size0){returnnull;}Stringvalarr[head];head;size--;if(headarr.length){head0;}returnval;}重写toString方法创建一个拼接字符串让cur从head的位置开始往后移动每次都把cur的元素添加到拼接字符串中直到拼接字符串中添加了size个元素当cur等于arr.length时就让cur等于0回到数组开头OverridepublicStringtoString(){StringBuilderstringBuildernewStringBuilder();stringBuilder.append([);intcurhead;for(inti0;isize;i){stringBuilder.append(arr[cur]);cur;if(curarr.length){cur0;}if(isize-1){stringBuilder.append(,);}}stringBuilder.append(]);returnstringBuilder.toString();}peek方法就是当队列不为空时就直接返回arr[head]publicStringpeek(){if(size0){returnnull;}returnarr[head];}这里聊个题外话在前面的offer方法中我们写的是先让tail接着判断tail是否等于arr.length如果等于arr.length了再让tail 0但是铁汁们可能看到过直接求余数的写法这个写法还是挺流行的tail;if(tailarr.length){tail0;}tail(tail1)%arr.length;tail 1的意思就是tail再对arr.length进行取模运算当tail 1等于arr.length的时候取模后结果会等于0其他情况取模后结果还是tail 1这个写法可能看起来比较牛一行代码就搞定了但是这样写真的比第一种写法好吗评价写法好不好看两个方面1对于开发效率的影响是否可读性好是否容易理解是否好维护 2对于运行效率的影响也就是程序的执行效率这个写法从可读性上看是不如第一种写法的不考虑编译器优化的话第一种写法的执行效率也更高第一种写法在大部分情况下cpu进行一次赋值操作进行一次比较操作即可(tail等于arr.length时才会进行两次赋值操作) 而第二种写法每次都会有赋值操作和取模操作而取模指令的效率是低于比较指令的编译器在执行第二种写法时不会真的去进行取模运算还是会优化成第一种写法5用队列实现栈力扣链接这个题目没啥实用价值就是纯考察我们的代码能力要求使用两个队列来模拟一个栈的功能队列的特点是先进先出栈的特点是先进后出可以这样搞A和B两个队列入栈时把元素加到A队列中元素需要出栈时就把队列A中的元素逐个取出来加到队列B中队列A中剩最后一个元素时直接删除即可接着交换下队列A和队列B的指向后面进行入栈操作还是把元素加到队列A中去再额外写个swap方法先创建个tmp引用把引用A保存下来接着再进行交换classMyStack{privateQueueIntegerAnewArrayDeque();privateQueueIntegerBnewArrayDeque();publicMyStack(){}publicvoidpush(intx){A.offer(x);}publicintpop(){while(A.size()1){intnA.poll();B.offer(n);}intresultA.poll();swap();returnresult;}publicinttop(){while(A.size()1){intnA.poll();B.offer(n);}intresultA.poll();B.offer(result);swap();returnresult;}publicbooleanempty(){returnA.isEmpty();}publicvoidswap(){QueueIntegertmpA;AB;Btmp;}}6用栈实现队列力扣链接用两个栈来模拟实现队列也是让元素再两个栈之间来回导两个栈A和B入队列时把元素添加到A栈中需要删除元素时再把元素从栈中导到B中这时候B的队首元素就是要删除或者要取出的元素但是这个题目如果再交换A和B的引用就不行了因为在A中先入队列的元素是在栈底而在B中先入队列的元素却是在栈底如果交换引用顺序就乱掉了因此还要再把B中的元素再导入到A中确保原来的顺序不变后面入队列就还是加到A中规则就是先入的在栈底后入的在栈顶classMyQueue{privateStackIntegerAnewStack();privateStackIntegerBnewStack();publicMyQueue(){}publicvoidpush(intx){A.push(x);}publicintpop(){while(A.size()1){B.push(A.pop());}intresultA.pop();while(B.size()0){A.push(B.pop());}returnresult;}publicintpeek(){while(A.size()0){B.push(A.pop());}intresultB.peek();while(B.size()0){A.push(B.pop());}returnresult;}publicbooleanempty(){returnA.isEmpty();}}结语队列在数据结构中相对来说是比较简单的因为只有三个操作用数组和链表模拟实现下自己的队列就能很好的掌握队列的用法下篇数据结构博客会解析二叉树二叉树的知识点相对来说就比较繁杂大量题目依赖递归也涉及到一些算法思想预计会用5篇博客来解析二叉树欢迎铁汁们来观看后续的二叉树博客以上就是今天的所有内容啦完结撒花