学编程 ❀(๑╯◡╰๑)❀ 就上soxunxi.cn!这里有CMS,CSS,NET,PHP,Linux,HTML,JAVA,MySQL,Python等教程.
当前位置: JAVA > java完成轮回行列【JAVA教程】,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
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    /**
     * 轮回行列入队操纵
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //轮回行列元素满的推断前提,假如满了就举行扩容操纵,扩展两倍
        if ((tail+1)%data.length == front)
            resize(2 * getCapacity());
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;

    }

    /**
     * 轮回行列扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[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
    public E dequeue() {
        //起首推断行列是不是为空,假如为空则抛出非常
        if (isEmpty())
            throw new IllegalArgumentException("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);
        return ret;
    }

    /**
     * 检察队首元素
     * @return
     */
    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 推断循行列是不是为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        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");
        return res.toString();
    }
}

相干文章教程引荐:java入门教程

以上就是java完成轮回行列的细致内容,更多请关注ki4网别的相干文章!

「梦想一旦被付诸行动,就会变得神圣,如果觉得我的文章对您有用,请帮助本站成长」

分享到:
赞(0) 打赏

支付宝扫一扫打赏

微信扫一扫打赏

标签:

上一篇:

下一篇:

相关推荐

0 条评论关于"java完成轮回行列【JAVA教程】,java,循环队列"

最新评论

    暂无留言哦~~

博客简介

看古风美女插画Cos小姐姐,素材合集图集打包下载:炫龙网,好看二次元插画应有尽有,唯美小姐姐等你来。

友情链接

他们同样是一群网虫,却不是每天泡在网上游走在淘宝和网游之间、刷着本来就快要透支的信用卡。他们或许没有踏出国门一步,但同学却不局限在一国一校,而是遍及全球!申请交换友链

服务热线:
 

 QQ在线交流

 旺旺在线