大家好,又见面了,我是你们的朋友全栈君。
循环队列的顺序存储结构
在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面的有效元素前移一位。
所以,这里就会用到循环队列,显然,这种队列也是顺序存储结构,在这个循环队列中也会去实现接口Queue。
首先,我们要想到的是如何将一般的队列改变为循环队列。
- 和之前一般的队列的顺寻存储结构一样,默认初始数组容量为10(循环队列的数组实际容量为11,这是因为要空出一个数组空间,至于为什么,将在后面进行解释);
- 定义一个头指针front和尾指针rear,用这两个指针去维护循环队列中元素的入队和出队;
- 定义一个size,去统计当前循环队列中的元素的有效个数;
现在,我们先看一下循环队列是如何入队和出队的。
初始时:
入队一个元素:
出队一个元素:
这样,front和rear指针就可以很轻松的去维护循环队列的入队和出队,并且它们的时间复杂度都为O(1),但是要注意特殊情况的存在,比如,当数组的0角标没有元素但7角标也有元素的时候,rear指针就要移动到front的前面,如下图所示:
这个时候很明显,循环队列已经满了,所以我们就会想到,如何判断循环队列什么时候为满,什么时候为空?
其实,利用它的周期性可以很明显的得出结论:
队列为满的时候:(rear+1)%n == front; (n为数组的总长度;如上图:(0+1)%8等于1也就是等于front指向的位置)
如果出现这种情况,如下图示:
因为,我们每次的出队,front指针都会向后面移动一位,而rear指针是不会移动的,如果我们将上图的两个元素全部出队列,会出现这样的情况:
很显然,判断队列为空也为:(rear+1)%n == front;
这样的话就会重复,所以这就是我们之前说,为什么要在创建循环队列数组的时候多创建一个元素空间的原因了。
因此,判断队列为空的条件就为:rear == front;
如下图:
如上图,我们现在入队一个元素:
每次在入队的时候,将rear指针始终指向队尾最后一个元素的空间。
并且每次入队的时候,rear的变化也要注意:rear = (rear+1)%n;
说了这么多,我们就来看一下具体的代码实现。
首先和我们之前一样,先来看看它的顺序存储结构:
package DS01.动态数组;
import java.util.Iterator;
/** * @author 七夏 * @param <E> * @version 1.0 * 循环队列:如果我们默认创建一个为容量为10的的循环队列时,我们须在该循环队列容量的基础上再加1, * 这是为了在判断循环队列是否为空时,起到作用 * * 循环队列为满时的条件:(rear+1)%data.length 等于 front * 循环队列为空时的条件:front == rear * 元素每次进队时,队头front每次更新:front = (front+1)%data.length * 元素每次出队时,队尾rear每次更新:rear = (rear+1)%data.length * 函数 E getRear() 在获取队尾元素时的方法为:data[(rear-1+data.length)%data.length] */
public class ArrayQueueLoop<E> implements Queue<E>{
//设置默认初始容量(后面会加1)
private static final int DEFAULT_CAPACITY = 10;
private E[] data;
private int front;
private int rear;
private int size;
public ArrayQueueLoop(){
this(DEFAULT_CAPACITY);
}
public ArrayQueueLoop(int capacity){
if(capacity <= 0){
throw new IllegalArgumentException("指定容量错误:"+capacity);
}
data = (E[])(new Object[capacity+1]);//加1,让数组多出一个空间
front = 0;
rear = 0;
size = 0;
}
}
现在,看一下入队代码:
@Override
public void enqueue(E e) {
//判断队列是否满
if((rear + 1)%data.length == front){
//扩容
resize(data.length*2-1);
}
data[rear] = e;
//更新rear队尾指针位置
rear = (rear+1)%data.length;
size++;
}
出队:
@Override
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("队列为空");
}
//拿出对头元素
E res = data[front];
//更新front对头指针位置
front = (front+1)%data.length;
size--;
//缩容
if(size <= (data.length-1)/4 && (data.length-1)/2 >= 10){
resize(data.length/2+1);
}
return res;
}
扩容:
private void resize(int newLen) {
E[] newData = (E[])(new Object[newLen]);
int p = front;
int i = 0;
while(true){
newData[i] = data[p];
i++;
p = (p+1)%data.length;
//如果p指针等于rear队尾指针时,结束循环
if(p == rear){
break;
}
}
/* 上述while循环相当于下述for循环 for(int i = 0,p = front;p != rear;i++,p = (p+1)%data.length){ newData[i] = data[p]; } */
front = 0;
rear = size;
data = newData;
}
实现iterator方法:
和之前都大致类似,在这里,我们在内部类中首先定义一个p指针,用来遍历循环队列,在hasNext函数中,只要p指针不等于rear队尾指针,说明该循环队列“尚不为空”(当前指向的元素后面还有元素);next函数中,创建res变量获取当前元素,之后将更新p指针的位置,最终返回res。
@Override
public Iterator<E> iterator() {
return new ArrayQueueLoopIterator();
}
private class ArrayQueueLoopIterator implements Iterator<E>{
int p = front;
@Override
public boolean hasNext() {
return p != rear;
}
@Override
public E next() {
E res = data[p];
//更新p指针的指向位置
p = (p+1)%data.length;
return res;
}
}
其他方法:
在这些方法中,我们要注意toString方法和getRear方法,在getRear方法中,我们直接返回data[(rear-1+data.length)%data.length]。
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0 && front == rear;
}
@Override
public E getFront() {
if(isEmpty()){
throw new IllegalArgumentException("队列为空");
}
return data[front];
}
@Override
public E getRear() {
if(isEmpty()){
throw new IllegalArgumentException("队列为空");
}
return data[(rear-1+data.length)%data.length];
}
@Override
public void clear() {
data = (E[])(new Object[DEFAULT_CAPACITY+1]);
front = 0;
rear = 0;
size = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("ArrayQueue: %d/%d \n",getSize(),data.length-1));
sb.append('[');
if(isEmpty()){
sb.append(']');
}else{
for (int i = front; i != rear; i = (i+1)%data.length) {
sb.append(data[i]);
if((i+1)%data.length == rear){
sb.append(']');
}else{
sb.append(',');
}
}
}
return sb.toString();
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/145910.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...