本篇文章给大家带来的内容是关于Java循环队列的介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
为了解决数组队列带来的问题,本篇给大家介绍一下循环队列。
思路分析图解
啰嗦一下,由于笔者不太会弄贴出来的图片带有动画效果,比如元素的移动或者删除(毕竟这样看大家比较直观),笔者在这里只能通过静态图片的方式,帮助大家理解实现原理,希望大家不要见怪,如果有朋友知道如何搞的话,欢迎在评论区慧言。
在这里,我们声明了一个容量大小为8的数组,并标出了索引0-7,然后使用front
和tail
分别来表示队列的,队首和队尾;在下图中,front
和tail
的位置一开始都指向是了索引0的位置,这意味着当front == tai
的时候 <font color = 'red'>
队列为空</font>
大家务必牢记这一点,以便区分后面介绍队列快满时的临界条件
为了大家更好地理解下面的内容,在这里,我简单做几点说明
front
:表示队列队首,始终指向队列中的第一个元素(当队列空时,front指向索引为0的位置)
tail
:表示队列队尾,始终指向队列中的最后一个元素的下一个位置
元素入队,维护tail
的位置,进行tail++
操作
元素出队,维护front
的位置,进行front++
操作上面所说的,元素进行入队和出队操作,都简单的进行++操作,来维护tail
和front
的位置,其实是不严谨的,正确的维护tail的位置应该是(tail + 1) % capacity,同理front的位置应该是(front + 1) % capacity,这也是为什么叫做循环队列的原因,大家先在这里知道下,暂时不理解也没关系,后面相信大家会知晓。
下面我们看一下,现在如果有一个元素a入队,现在的示意图:
我们现在看到了元素a入队,我们的tail指向的位置发生了变化,进行了++操作,而front的位置,没有发生改变,仍旧指向索引为0的位置,还记得笔者上面所说的,front的位置,始终指向队列中的第一个元素,tail的位置,始终指向队列中的最后一个元素的下一个位置
现在,我们再来几个元素b、c、d、e进行入队操作,看一下此时的示意图:
想必大家都能知晓示意图是这样,好像没什么太多的变化(还请大家别着急,笔者这也是方便大家理解到底是什么循环队列,还请大家原谅我O(∩_∩)O哈!)
看完了元素的入队的操作情况,那现在我们看一下,元素的出队操作是什么样的?
元素a
出队,示意图如下:
现在元素a已经出队,front的位置指向了索引为1的位置,现在数组中所有的元素不再需要往前挪动一个位置
这一点和我们的数组队列(我们的数组队列需要元素出队,后面的元素都要往前挪动一个位置)完全不同,我们只需要改变一下front的指向就可以了,由之前的O(n)操作,变成了O(1)的操作
我们再次进行元素b出队,示意图如下:
到这里,可能有的小伙伴会问,为什么叫做,循环队列?那么现在我们尝试一下,我们让元素f、g分别进行入队操作,此时的示意图如下:
大家目测看下来还是没什么变化,如果此时,我们再让一个元素h元素进行入队操作,那么问题来了我们的tail的位置该如何指向呢?示意图如下:
根据我们之前说的,元素入队:维护tail的位置,进行tail++操作,而此时我们的tail已经指向了索引为7的位置,如果我们此时对tail进行++操作,显然不可能(数组越界)
细心的小伙伴,会发现此时我们的队列并没有满,还剩两个位置(这是因为我们元素出队后,当前的空间,没有被后面的元素挤掉),大家可以把我们的数组想象成一个环状,那么索引7之后的位置就是索引0
如何才能从索引7的位置计算到索引0的位置,之前我们一直说进行tail++操作,笔者也在开头指出了,这是不严谨的,应该的是(tail + 1) % capacity这样就变成了(7 + 1) % 8等于 0
所以此时如果让元素h入队,那么我们的tail就指向了索引为0的位置,示意图如下:
假设现在又有新的元素k入队了,那么tail的位置等于(tail + 1) % capacity 也就是(0 + 1)% 8 等于1就指向了索引为1的位置
那么问题来了,我们的循环队列还能不能在进行元素入队呢?我们来分析一下,从图中显示,我们还有一个索引为0的空的空间位置,也就是此时tail指向的位置
按照之前的逻辑,假设现在能放入一个新元素,我们的tail进行(tail +1) % capacity计算结果为2(如果元素成功入队,此时队列已经满了),此时我们会发现表示队首的front也指向了索引为2的位置
如果新元素成功入队的话,我们的tail也等于2,那么此时就成了 tail == front ,一开始我们提到过,当队列为空的tail == front,现在呢,如果队列为满时tail也等于front,那么我们就无法区分,队列为满时和队列为空时收的情况了
所以,在循环队列中,我们总是浪费一个空间,来区分队列为满时和队列为空时的情况,也就是当 ( tail + 1 ) % capacity == front的时候,表示队列已经满了,当front == tail的时候,表示队列为空。
了解了循环队列的实现原理之后,下面我们用代码实现一下。
代码实现
接口定义 :Queue
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
接口实现:LoopQueue
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
|
测试类:LoopQueueTest
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 |
|
完整版代码GitHub仓库地址:Java版数据结构-队列(循环队列)
本篇文章到这里就已经全部结束了,更多其他精彩内容可以关注PHP中文网的Java视频教程栏目!
以上是Java循环队列的介绍(代码示例)的详细内容。更多信息请关注PHP中文网其他相关文章!