Java循环队列的案例分析

  

Java循环队列的案例分析?这个问题可能是我们日常学习或工作经常见到的。希望通过这个问题能让你收获颇深。下面是小编给大家带来的参考内容,让我们一起来看看吧!

思路分析图解

啰嗦一下,由于笔者不太会弄贴出来的图片带有动画效果,比如元素的移动或者删除(毕竟这样看大家比较直观),笔者在这里只能通过静态图片的方式,帮助大家理解实现原理,希望大家不要见怪,如果有朋友知道如何搞的话,欢迎在评论区慧言。

在这里,我们声明了一个容量大小为8的数组,并标出了索引0-7,然后使用fronttail分别来表示队列的,队首和队尾;在下图中,fronttail的位置一开始都指向是了索引0的位置,这意味着当front==tai的时候 队列为空 大家务必牢记这一点,以便区分后面介绍队列快满时的临界条件

Java循环队列的案例分析

为了大家更好地理解下面的内容,在这里,我简单做几点说明

front:表示队列队首,始终指向队列中的第一个元素(当队列空时,front指向索引为0的位置)

tail:表示队列队尾,始终指向队列中的最后一个元素的下一个位置

元素入队,维护tail的位置,进行tail++操作

元素出队,维护front的位置,进行front++操作上面所说的,元素进行入队和出队操作,都简单的进行++操作,来维护tailfront的位置,其实是不严谨的,正确的维护tail的位置应该是(tail + 1) % capacity,同理front的位置应该是(front + 1) % capacity,这也是为什么叫做循环队列的原因,大家先在这里知道下,暂时不理解也没关系,后面相信大家会知晓。

下面我们看一下,现在如果有一个元素a入队,现在的示意图:

Java循环队列的案例分析

我们现在看到了元素a入队,我们的tail指向的位置发生了变化,进行了++操作,而front的位置,没有发生改变,仍旧指向索引为0的位置,还记得笔者上面所说的,front的位置,始终指向队列中的第一个元素,tail的位置,始终指向队列中的最后一个元素的下一个位置

现在,我们再来几个元素b、c、d、e进行入队操作,看一下此时的示意图:

Java循环队列的案例分析

想必大家都能知晓示意图是这样,好像没什么太多的变化(还请大家别着急,笔者这也是方便大家理解到底是什么循环队列,还请大家原谅我O(∩_∩)O哈!)

看完了元素的入队的操作情况,那现在我们看一下,元素的出队操作是什么样的?

元素a出队,示意图如下:

Java循环队列的案例分析

现在元素a已经出队,front的位置指向了索引为1的位置,现在数组中所有的元素不再需要往前挪动一个位置

这一点和我们的数组队列(我们的数组队列需要元素出队,后面的元素都要往前挪动一个位置)完全不同,我们只需要改变一下front的指向就可以了,由之前的O(n)操作,变成了O(1)的操作

我们再次进行元素b出队,示意图如下:

Java循环队列的案例分析

到这里,可能有的小伙伴会问,为什么叫做,循环队列?那么现在我们尝试一下,我们让元素f、g分别进行入队操作,此时的示意图如下:

Java循环队列的案例分析

大家目测看下来还是没什么变化,如果此时,我们再让一个元素h元素进行入队操作,那么问题来了我们的tail的位置该如何指向呢?示意图如下:

Java循环队列的案例分析

根据我们之前说的,元素入队:维护tail的位置,进行tail++操作,而此时我们的tail已经指向了索引为7的位置,如果我们此时对tail进行++操作,显然不可能(数组越界)

Java循环队列的案例分析