您的位置 首页 技术

java实现循环队列

循环队列的优点 普通队列出队操作开销大:在出队操作时,索引为0后面的所有元素,都需要往前移动一位,元素越多,消耗的时间也越多,时间复杂度为O(N)。 循环队列的逻辑: 1、当元素较…

循环队列的优点

普通队列出队操作开销大:在出队操作时,索引为0后面的所有元素,都需要往前移动一位,元素越多,消耗的时间也越多,时间复杂度为O(N)。

循环队列的逻辑:

1、当元素较少时(tail位置在front后面),循环队列与普通队列出队操作一样,入队的元素将会放在tail的位置上,随后执行tail++操作;出队时front位置上的元素将会置null,随后执行front++操作;此时仍能保持着tail位置在front后面的状态,如下图所示:

6.jpg

2、当元素继续添加,最后一个元素将放到索引为7的位置,此时tail位置将会移动到队首前面索引为0的位置上,此时tail在数组的索引为变为:(tail+ 1 )% capacity如下图所示:

348c6d5fe9956124864a9d0fbb1fe58.png

3、当元素继续添加时,元素将会在tail位置上添加,tail继续往后移动,如下图所示:

c7a2b183ecf37fafb85ce9778056f02.png

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实现循环队列的详细内容,更多请关注24课堂在线网其它相关文章!

本文来自网络,不代表24小时课堂在线立场,转载请注明出处:https://www.24ketang.cn/21390.html

为您推荐

返回顶部