java实现循环队列
循环队列的优点
普通队列出队操作开销大：在出队操作时，索引为0后面的所有元素，都需要往前移动一位，元素越多，消耗的时间也越多，时间复杂度为O(N)。
循环队列的逻辑：
1、当元素较少时（tail位置在front后面），循环队列与普通队列出队操作一样，入队的元素将会放在tail的位置上，随后执行tail++操作；出队时front位置上的元素将会置null，随后执行front++操作；此时仍能保持着tail位置在front后面的状态，如下图所示：
2、当元素继续添加，最后一个元素将放到索引为7的位置，此时tail位置将会移动到队首前面索引为0的位置上，此时tail在数组的索引为变为：(tail+ 1 )% capacity如下图所示：
3、当元素继续添加时，元素将会在tail位置上添加，tail继续往后移动，如下图所示：
4、继续添加元素，当tail与front还相距一个单位时，即此时数组还有一个空余存储空间，但当前数组已经不能继续实现循环队列的插入操作了，因为循环队列判断队列为空的条件就是front == tail，所以此时需要进行扩容操作；因此此处有意识的浪费了一个空间。
此处可以推出，循环队列元素满的条件为：tail +1 == front(初步得出，后续会完善为(tail + 1) % capacity == front )
5、适当情况下，此若时持续进行出队操作，front的位置也将会从数组最右端跳转到数组最左端开始。此时front在数组的索引为变为：(front + 1 )% capacity
代码实现：（相关视频教程分享：java视频教程）
package dataStructure.chapter3;
/**
* @Author: zjtMeng
* @Date: 2019/12/28 20:13
* @Version 1.0
*/
publicclassLoopQueue<E> implementsQueue<E> {
privateE[] data;
privateint front,tail;
privateint size;
publicLoopQueue(int capacity){
data = (E[]) newObject[capacity+1];
}
publicLoopQueue(){
this(10);
}
publicint getCapacity(){
returndata.length-1;
}
/**
* 循环队列入队操作
* @param e
*/
@Override
publicvoid enqueue(E e) {
//循环队列元素满的判断条件,如果满了就进行扩容操作，扩大两倍
if((tail+1)%data.length == front)
resize(2 * getCapacity());
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
/**
* 循环队列扩容
* @param newCapacity
*/
privatevoid resize(int newCapacity){
E[] newData = (E[]) newObject[newCapacity+1];
//循环队列第一种遍历方式
for(int i = 0 ; i < size ; i++ ){
//newData[]中的元素与data[]中的元素，一方面存在着front的偏移量，另一方面，data[]中的元素，
//可能在有部分处于front前面，因此此处采用对数组长度取余，来判断元素的位置
newData[i] = data[(i+front)%data.length];
}
data = newData;
front =0;
tail = size;
}
@Override
publicE dequeue() {
//首先判断队列是否为空，如果为空则抛出异常
if(isEmpty())
thrownewIllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
//引用地址需要置空，否则JVM不能及时回收空间，从而可能会出现OOM异常
data[front] = null;
front = (front + 1 )% data.length;
size--;
//如果元素数量达到队列容积的1/4，且队列容积/2 不等于0时，进行缩容操作
if(size == getCapacity() / 4 && getCapacity() / 2 != 0 )
resize(getCapacity() / 2);
returnret;
}
/**
* 查看队首元素
* @return
*/
@Override
publicE getFront() {
if(isEmpty())
thrownewIllegalArgumentException("Queue is empty.");
returndata[front];
}
@Override
publicint getSize() {
returnsize;
}
/**
* 判断循队列是否为空
* @return
*/
@Override
publicboolean isEmpty() {
returnfront == tail;
}
@Override
publicString toString(){
StringBuilder res = newStringBuilder();
res.append(String.format("Queue: size = %d, capacity = %d\n",size, getCapacity()));
res.append("front[");
//循环队列遍历的第二种方法
for(int i = front; i != tail; i = (i + 1) % data.length){
res.append(data[i]);
//循环队列未遍历到队尾的标志
if((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
returnres.toString();
}
}
相关文章教程推荐：java入门教程
