数据结构学习之——数组队列和循环队列的实现与效率的测试
队列Queue:
是一种线性的数据结构,底层可以有很多种实现方式,比如说数组,还有链表之类的,它限制了我们数据的插入和删除,只能从队尾插入(入队),队首删除(出队),先进先出,类似于一根管道,钻狗洞那样。队列的实现:
定义一个接口1、这里我们先用数组来实现数组队列
底层使用一个Java自带的ArrayList
2、分别实现我们自己Queue接口中的方法
基本的方法基本上数组队列的实现没什么难度
我们来分析一下数组队列的时间复杂度通过上图我们可以看出,因为底层使用的是动态数组ArrayList,入队enqueue,我们只用往数组的最后一个位置添加就可以了O(1),如果容量不够就扩容O(n)(但是这种添加很多次才会有),所以这里均摊时间复杂度是O(1),但是,出队dequeue,由于是让数组的第一个元素出去,数组的后面的元素会往前挪,所以时间复杂度为O(n)
那么问题来了,我们其实没有必要每次出队dequeque,都让数组后面的元素往前挪的,因为我们只需要使用指针front来表示哪个是队首,哪个是队尾tail就可以了,也就是说,我们出队dequeue之后空出来的元素位置,留着下次进队enqueue来占用
实际上,有了指针指明,它还是一个队列
这个就是循环队列
虽然表面看着像一个数组样子,但底层由于有了两个指针front队首,tail队尾就像一个环一样的,绕了一圈又一圈
因为我们可以看到上面图中front==tail的时候,队首指针和队尾指针指向同一个位置,这时候队列为空,
当我们的队列的队首指针到达数组的最后一个位置时,我们需要让它指向数组的起始位置,
如上图所示,
当h元素入队的时候,tail队尾的指针这时候指向了索引为0的位置
当i元素入队的时候,tail队首的指针这时候应该指向索引为1的位置,实际上这时候数组已经满了,我们需要扩容来解决问题了我们也可以看出来,当tail+1front表示队列满,fronttail表示队列为空,capacity中,浪费一个空间,用来说明这一点
实际上,tail+1 = front是不准确的,应该是**(tail+1)%(数组的长度)**,因为我们让队尾指针tail从队尾指向了数组的起始的地方,就是通过+1取模的操作
下面我们来实现
依旧是队列Queue接口实现类循环队列
这里比较复杂的是进队enqueue操作
我们通过前面的图片和分析可以看出来,(tail+1)%data.length==front,说明队列的底层数组已经满了,需要扩容了
这里比较难理解的就是取模运算,为什么我们需要取模呢?就是因为如果队尾tail,如果指向了数组的最后一个位置的话,再加一已经是越界了,这肯定是有问题的,那么如何让它指向我们数组前面,出队dequeue之后,队首前面空出的位置呢?
使用取模运算,取当前数组长度
扩容也一样,创建一个数组,把老数组里面的元素挨个复制进去新数组中,这里需要注意的地方是
新数组的第一个位置的元素的值是,老数组的队首元素的值
接着是出队操作dequeue
我们让队首front的元素值为null,让队首的指针向后移动一位,但是这里为了防止越界,我们不能直接fornt++,而是也得取模
我们为了不浪费过多的空间,当我们的size元素个数为capacity容量的四分之一时,并且容量可以分为两半时,进行缩容。
由于循环队列,每次操作元素的时候,只有在入队enqueue的时候,容量不够才会扩容,移动元素,一般的入队,出队是不会的所以入队enqueue,出队dequeue的均摊时间复杂度为O(1)
总结:
虽然数组队列的实现逻辑没有循环队列那么麻烦,但是出队dequeue的复杂度太高了,这显然是不好的,循环队列虽然复杂一些,但是大大的使均摊复杂度变为了O(1)
测试数据:可以看到耗时的差距有多大,为什么时间复杂度分析如此的重要