循环队列的顺序存储结构Java

循环队列的顺序存储结构Java循环队列的顺序存储结构在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面的有效元素前移一位。所以,这里就会用到循环队列,显然,这种队列也是顺序存储结构,在这个循环队列中也会去实现接口Queue。首先,我们要想到的是如何将一般的队列改变为循环队列。…

大家好,又见面了,我是你们的朋友全栈君。

循环队列的顺序存储结构

在上次,我们讲到的是,队列的顺序存储结构也是由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账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号