如何实现一个支持动态扩展的循环队列
零循环队列性质概述
前面，我们利用动态数组快速的实现了队列这种基础的数据结构。但是，由于底层是动态数组存储，每次出队操作(删除数组的第1个元素)导致后面所有的元素都需要向前移动一个位置，进而导致出队操作的均摊时间复杂度是O(n)。显然，这不是我们想要的。如果能实现一个出队操作的时间复杂度也是O(1)的就更好了。
于是，为了解决上述问题，人们研究出了一种循环队列。将底层数组的首尾相连，形如一个转盘一样，引入两个指针，分别指向队首和队尾，队列初始时，它们都指向0。随着入队操作，即元素的不断插入，队尾指针不停前进，出队操作时，队首元素删除，然后队首指针不停前进。
当然，如果队列长度是固定的话，假定是5，初始时，head和tail都指向0，插入元素’a’,’b’,’c’,’d’之后，tail=4随着元素的不断插入tail逐渐逼近数组总长度5。如果此时再入队操作，插入元素’e’的话，则队列就满了。但是，如果此时出队操作dequeue()，则数组空出一个位置，对于循环队列，我们可以让队尾指针继续向前走，重新指向数组下标为0的位置，又可以插入一个新元素了。这就是循环队列，头、尾指针都可以绕环不停的前移。
循环队列，我们规定浪费一个存储空间。即对于长度为5的指针，我们最多可以插入4个元素。
对于普通队列，队尾指针永远>=队首指针，而循环队列的队尾指针有可能<=队首指针。
队列判空：普通队列，队首指针=队尾指针；循环队列，依然是，队首指针=队尾指针；
队列满：队首指针=0，队尾指针=数组容量；循环队列，(队尾指针+1)%数组长度=队首指针；
一循环队列代码实现
public class CircularQueue<E> implements Queue<E>{
//底层不再使用动态数组，我们自己实现一个数组
private E[] array;
//head,tail分别表示指向队列头、尾指针，size表示当前队列中实际存放多少个元素
private int head,tail,size;
public CircularQueue(int capacity){
//由于浪费一个存储空间，所以开放给用户的接口参数+1个空间才是数组的初始化大小
array=(E[]) new Object[capacity+1];
head=0;
tail=0;
size=0;
}
public CircularQueue(){
this(10);
}
//查看队列最多可以存放多少个元素
public int getCapacity(){
//这里为什么是array.length()-1 ？？？？
// return array.length()-1;
return array.length-1;
}
@Override
public void enqueue(E e){
//如果队列满，则扩容，再添加
if((tail+1)%array.length==head){
resize(2*array.length);
}
array[tail]=e;
tail=(tail+1)%array.length;
size++;
}
@Override
public E dequeue(){
//如果队列空，则抛出异常
if(head==tail){
throw new RuntimeException("Queue is empty,canot dequeue");
}
E temp=array[head];
head=(head+1)%array.length;
size--;
//底层数组缩容
if(size==array.length/4 && array.length/2 !=0){
resize(array.length/2);
}
return temp;
}
private void resize(int newCapacity){
//初始化一个长度为newCapacity+1的数组
E[] newArray=(E[])new Object[newCapacity+1];
//然后将原数组的数据copy到这个新数组
//原数组从head--->tail，不管队列是否已经循环。每次下标(i+1)%array.length()，+1，新数组下标要从0开始，因此，其下标从i-head开始，相当于是出现了head个偏移量
for(int i=head;i!=tail;i=(i+1)%array.length){
newArray[i-head]=array[i];
}
//复制之后，将指向原数组的引用指向新数组的引用；
array=newArray;
//队列头指针指向0，
head=0;
//队尾指针指向size位置处
tail=size;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return head==tail;
}
@Override
public E getFront(){
if(head==tail){
throw new RuntimeException("Queue is empty,canot get front.");
}
return array[head];
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Queue,size: %d, capacity: %d\n", size,getCapacity()));
stringBuilder.append("head[");
for(int i=head;i!=tail;i=(i+1)%array.length){
stringBuilder.append(array[i]);
if((i+1)%array.length != tail){
stringBuilder.append(" , ");
}
}
stringBuilder.append("]tail");
return stringBuilder.toString();
}
public static void main(String[] args) {
CircularQueue<Integer> circularQueue = new CircularQueue<>();
for (int i = 0; i < 10; i++) {
circularQueue.enqueue(i);
System.out.println(circularQueue);
if (i % 3 == 2) {
System.out.println(circularQueue.dequeue());
System.out.println(circularQueue);
}
}
}
}
//结果：
Queue,size: 1, capacity: 10
head[0]tail
Queue,size: 2, capacity: 10
head[0 , 1]tail
Queue,size: 3, capacity: 10
head[0 , 1 , 2]tail
0
Queue,size: 2, capacity: 5
head[1 , 2]tail
Queue,size: 3, capacity: 5
head[1 , 2 , 3]tail
Queue,size: 4, capacity: 5
head[1 , 2 , 3 , 4]tail
Queue,size: 5, capacity: 5
head[1 , 2 , 3 , 4 , 5]tail
1
Queue,size: 4, capacity: 5
head[2 , 3 , 4 , 5]tail
Queue,size: 5, capacity: 5
head[2 , 3 , 4 , 5 , 6]tail
Queue,size: 6, capacity: 12
head[2 , 3 , 4 , 5 , 6 , 7]tail
Queue,size: 7, capacity: 12
head[2 , 3 , 4 , 5 , 6 , 7 , 8]tail
2
Queue,size: 6, capacity: 12
head[3 , 4 , 5 , 6 , 7 , 8]tail
Queue,size: 7, capacity: 12
head[3 , 4 , 5 , 6 , 7 , 8 , 9]tail小结：对于循环队列的实现，有几个难点和注意点
a 底层的数组长度应该是用户传来实例化队列长度参数+1；因为，循环队列浪费一个存储空间；
b 循环队列判空条件：head ==tail;队满条件：(tail+1) % array.length == head;
c 循环队列底层数组遍历、copy元素条件,for(int i=head;i != tail;i=(i+1)%array.length;){ newArray[i-head] = array[i];}
二 循环队列VS普通队列性能对比
public class QueueTest {
private static long test(Queue queue, int count) {
long beginTime=System.currentTimeMillis();
for (int i = 0; i < count; i++) {
queue.enqueue(i);
}
for (int i = 0; i < count; i++) {
queue.dequeue();
}
long endTime = System.currentTimeMillis();
return (endTime-beginTime);
}
public static void main(String[] args) {
int count=100000;
long t1 = test(new ArrayQueue(), count);
long t2 = test(new CircularQueue(), count);
System.out.println("ArrayQueue:" + t1);
System.out.println("CircularQueue:" + t2);
}
}
//结果
ArrayQueue:4407
CircularQueue:14普通队列，分别入队、出队100000次，耗时4407毫秒；
循环队列，分别入队、出队100000次，耗时14毫秒；
主要的性能差异就在出队dequeue()操作上，普通队列，底层采用动态数组实现，借用数组的removeFirst()方法来实现出队操作，但是该方法会造成元素的大迁移，进而时间复杂度是O(n2)。而我们实现的循环队列就不存在这个问题，dequeue()操作，我们只需将队列的头指针head后移一个位置即可，不存在元素大迁移，复杂度是O(1)。
一条评论
Pingback: