Java模拟数组的环形队列

简介: Java模拟数组的环形队列

简介

队列是有序的,可以通过线性数据结构来实现(数组或链表)。

而环形队列是在数组队列的基础之上可以让数组的存储容量反复使用,但是牵扯到一些算法会使他有那么一丢丢复杂,不过没关系,接下来我们就逐步击破,最后提供数组环形队列的源码哦

数组队列中的属性

/**
 * 第一个元素,有些地方叫做队列头
 */
private int first;
/**
 * 最后一个元素,有些地方叫做队列尾
 */
private int last;
/**
 * 队列的最大大小
 */
private int maxSize;
/**
 * 队列
 */
private Object[] queue;
  • 第一个元素(队列头),在这主要是指第一个有效元素所在的数组下标,默认为0
  • 最后一个元素(队列尾),在这里指的是最后一个有效元素的下标位置,默认为0
  • 队列最大大小,也就是队列数组大小,队列的最大容量
  • 队列(queue),也就是存储队列元素的容器

构造方法

public ArrayCircleQueue(int maxSize) {
    // 最大大小的赋值
    this.maxSize = maxSize;
    // 为队列设置最大大小
    queue = new Object[maxSize];
    // 队列的初始头部和尾部都为0
    this.first = 0;
    this.last = 0;
}

传进来一个max,用于初始化队列大小,比较简单,不再讲解

判断队列是否被装满的方法

public boolean isFull() {
    // 判断是否被装满的算法是 (this.last + 1) % this.maxSize == this.first
    return (this.last + 1) % this.maxSize == this.first;
}

这个方法的思路就是 last 位于 first 的前一个位置,大概意思就是 last + 1 == first,但是还有一种情况就是 first = 0 但是 last = maxSize - 1,所以要与 maxSize 取模。

判断队列是否为空

public boolean isEmpty() {
    /* 判断方式是首部是否等于尾部 并且还有最重要的一点就是当前最后一个位置上的元素为空 */
    return this.first == this.last && null == this.queue[last];
}

主要就是判断 first 和 last 是不是相等,最后判断当前位置上的元素是否为空。

判断不为空的方法

public boolean isNotEmpty() {
    return !this.isEmpty();
}

懂得都懂,不再解释这个方法

队列大小

public int size() {
    if (this.isEmpty()) return 0; // 为空则返回0
    /* =====================================================================
        求出队列的大小,正常情况下是 this.last - this.first + 1 但是还有 this.last 比
        this.first 小的时候,那么以上公式不可用,需要用下面这套公式:
                (this.last + 1 + this.maxSize - this.first) % this.maxSize
       ===================================================================== */
    return (this.last + 1 + this.maxSize - this.first) % this.maxSize;
}

看注释即可

向队列中添加数据

public boolean append(T e) {
    /* =====================================================================
        首先我们要判断队列是否被装满,如果被装满则返回false告诉用户添加失败
        即代表当前元素已满
       ===================================================================== */
    if (this.isFull()) return false; // 告诉用户队列已满
    /* =====================================================================
        首先我们需要判断队列是否为空,应为为空的时候队列头部和队列尾部值相等,所以如果其
        相等,那么插入位置就是尾部(this.last)所在的位置,如果不为空,尾部位置指向的就是
        最有一个有值的元素,所以要将尾部(this.last)位置后移一位,然后插入到尾部位置
       ===================================================================== */
    if (this.isNotEmpty()) {
        // 如果后移后大于数组最大下标(this.maxSize + 1),则插入位置和最后位置都为
        if (++this.last >= this.maxSize) {
            this.last = 0;
        }
    }
    // 插入数据
    this.queue[this.last] = e;
    return true; // 只要元素没被占满,一切情况都代表添加成功
}

出列一个数据

public T pop() {
    /* =====================================================================
        两种情况,第一种是队列为空,第二种是队列不为空。
        1. 第一种比较好操作,这种情况下不用做任何操作,直接返回空。
        2. 第二种情况下要做的事就是将对象返回,并将数组这个下标的值清空,清空的原因是
        为了避免 GC 垃圾回收器无法回收该对象而导致的有可能的内存溢出,并且还要将该对象
        强转为范类型然后返回
       ===================================================================== */
    if (this.isEmpty()) return null; // 为空的情况
    // 不为空的情况下的处理逻辑
    T result = (T) this.queue[this.first];
    // 取消引用
    this.queue[this.first] = null;
    // 如果此时队列不为空则后移
    if (this.isNotEmpty()) {
        /* =====================================================================
         后移算法:如果后移后数组会越界(则 this.first == this.maxSize),那么
         this.first = 0 这样可以有效避免数组越界
        ===================================================================== */
        if (++this.first >= this.maxSize) this.first = 0;
    }
    return result;
}

遍历这个数组环形队列

public void foreach(Consumer<T> f) {
    // 为空的话就不需要遍历了
    if (this.isEmpty()) return;
    // for 循环阈值,计算方式是 起始值 + 循环次数(队列的大小)
    int forThreshold = this.first + this.size();
    // 循环遍历
    for (int i = this.first; i < forThreshold; i++) {
        // 因为可能的数组越界(在this.last 比 this.first 小的时候),所以要取模
        f.accept((T) this.queue[i % this.maxSize]);
    }
}

上面的代码看注释应该就没问题了,如果还有问题可以留言询问

完整的类代码

package code.xiaohh.queue.circle;
import java.io.Serializable;
import java.util.function.Consumer;
/**
 * <p>
 * 数组环形队列
 * </p>
 *
 * @author XiaoHH
 * @version 1.0
 * @date 2021-05-07 星期五 20:19:38
 * @file ArrayCircleQueue.java
 */
public class ArrayCircleQueue<T> implements Serializable {
    /**
     * 第一个元素
     */
    private int first;
    /**
     * 最后一个元素
     */
    private int last;
    /**
     * 队列的最大大小
     */
    private int maxSize;
    /**
     * 队列
     */
    private Object[] queue;
    /**
     * 某些反序列化框架需要无参构造
     */
    private ArrayCircleQueue() {
    }
    /**
     * 唯一的构造函数,需要设定队列最大大小
     *
     * @param maxSize 最大大小
     */
    public ArrayCircleQueue(int maxSize) {
        // 最大大小的赋值
        this.maxSize = maxSize;
        // 为队列设置最大大小
        queue = new Object[maxSize];
        // 队列的初始头部和尾部都为0
        this.first = 0;
        this.last = 0;
    }
    /**
     * 添加一个对象到队列中
     *
     * @param e 需要添加到队列中的对象
     * @return 是否成功,不成功是因为队列已满
     */
    public boolean append(T e) {
        /* =====================================================================
            首先我们要判断队列是否被装满,如果被装满则返回false告诉用户添加失败
            即代表当前元素已满
           ===================================================================== */
        if (this.isFull()) return false; // 告诉用户队列已满
        /* =====================================================================
            首先我们需要判断队列是否为空,应为为空的时候队列头部和队列尾部值相等,所以如果其
            相等,那么插入位置就是尾部(this.last)所在的位置,如果不为空,尾部位置指向的就是
            最有一个有值的元素,所以要将尾部(this.last)位置后移一位,然后插入到尾部位置
           ===================================================================== */
        if (this.isNotEmpty()) {
            // 如果后移后大于数组最大下标(this.maxSize + 1),则插入位置和最后位置都为
            if (++this.last >= this.maxSize) {
                this.last = 0;
            }
        }
        // 插入数据
        this.queue[this.last] = e;
        return true; // 只要元素没被占满,一切情况都代表添加成功
    }
    /**
     * 出列一个对象,出列的这个对象是头部对象,并且这个对象会被队列所删除
     *
     * @return 被出列的这个对象
     */
    public T pop() {
        /* =====================================================================
            两种情况,第一种是队列为空,第二种是队列不为空。
            1. 第一种比较好操作,这种情况下不用做任何操作,直接返回空。
            2. 第二种情况下要做的事就是将对象返回,并将数组这个下标的值清空,清空的原因是
            为了避免 GC 垃圾回收器无法回收该对象而导致的有可能的内存溢出,并且还要将该对象
            强转为范类型然后返回
           ===================================================================== */
        if (this.isEmpty()) return null; // 为空的情况
        // 不为空的情况下的处理逻辑
        T result = (T) this.queue[this.first];
        // 取消引用
        this.queue[this.first] = null;
        // 如果此时队列不为空则后移
        if (this.isNotEmpty()) {
            /* =====================================================================
             后移算法:如果后移后数组会越界(则 this.first == this.maxSize),那么
             this.first = 0 这样可以有效避免数组越界
            ===================================================================== */
            if (++this.first >= this.maxSize) this.first = 0;
        }
        return result;
    }
    /**
     * 判断队列是否为空
     *
     * @return 判断结果
     */
    public boolean isEmpty() {
        /* 判断方式是首部是否等于尾部 并且还有最重要的一点就是当前最后一个位置上的元素为空 */
        return this.first == this.last && null == this.queue[last];
    }
    /**
     * 判断队列是否不为空
     *
     * @return 判断结果
     */
    public boolean isNotEmpty() {
        return !this.isEmpty();
    }
    /**
     * 判断队列是否已被填满
     *
     * @return 判断结果
     */
    public boolean isFull() {
        // 判断是否被装满的算法是 (this.last + 1) % this.maxSize == this.first
        return (this.last + 1) % this.maxSize == this.first;
    }
    /**
     * @return 队列的大小
     */
    public int size() {
        if (this.isEmpty()) return 0; // 为空则返回0
        /* =====================================================================
            求出队列的大小,正常情况下是 this.last - this.first + 1 但是还有 this.last 比
            this.first 小的时候,那么以上公式不可用,需要用下面这套公式:
                    (this.last + this.maxSize - this.first) % this.maxSize
           ===================================================================== */
        return (this.last + 1 + this.maxSize - this.first) % this.maxSize;
    }
    /**
     * 遍历环形队列
     *
     * @param f 遍历传进来的消费者方法
     */
    public void foreach(Consumer<T> f) {
        // 为空的话就不需要遍历了
        if (this.isEmpty()) return;
        // for 循环阈值,计算方式是 起始值 + 循环次数(队列的大小)
        int forThreshold = this.first + this.size();
        // 循环遍历
        for (int i = this.first; i < forThreshold; i++) {
            // 因为可能的数组越界(在this.last 比 this.first 小的时候),所以要取模
            f.accept((T) this.queue[i % this.maxSize]);
        }
    }
}

作业:自行测试

相关文章
|
2月前
|
存储 缓存 算法
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
33 4
|
2月前
|
存储 缓存 算法
提高 Java 数组性能的方法
【10月更文挑战第19天】深入探讨了提高 Java 数组性能的多种方法。通过合理运用这些策略,我们可以在处理数组时获得更好的性能表现,提升程序的运行效率。
40 2
|
2月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
93 2
|
2月前
|
存储 Java
什么是带有示例的 Java 中的交错数组?
什么是带有示例的 Java 中的交错数组?
53 9
|
2月前
|
Java
Java数组动态扩容和动态缩减
Java数组动态扩容和动态缩减
25 3
|
2月前
|
存储 算法 Java
Java一分钟之-数组的创建与遍历
数组作为Java中存储和操作一组相同类型数据的基本结构,其创建和遍历是编程基础中的基础。通过不同的创建方式,可以根据实际需求灵活地初始化数组。而选择合适的遍历方法,则可以提高代码的可读性和效率。掌握这些基本技能,对于深入学习Java乃至其他编程语言的数据结构和算法都是至关重要的。
30 6
|
2月前
|
存储 Java 程序员
【一步一步了解Java系列】:何为数组,何为引用类型
【一步一步了解Java系列】:何为数组,何为引用类型
31 1
|
2月前
|
存储 XML Java
如何在 Java 中将常见文档转换为 PNG 图像数组
如何在 Java 中将常见文档转换为 PNG 图像数组
18 1
|
2月前
|
存储 安全 Java
Java数组(Arrays)详解
Java 中的数组是一种用于存储固定数量同类型数据的高效数据结构,支持连续内存存储和随机访问。数组可以声明并初始化,通过索引访问和修改元素,获取长度,使用循环遍历,支持多维形式,并可通过 `Arrays` 类的方法进行复制和排序。数组具有固定大小和类型安全的特点,但需注意越界等问题。灵活运用数组能显著提升编程效率。
117 9
|
3月前
|
存储 Java 数据处理
Java 数组的高级用法
在 Java 中,数组不仅可以存储同类型的数据,还支持多种高级用法,如多维数组(常用于矩阵)、动态创建数组、克隆数组、使用 `java.util.Arrays` 进行排序和搜索、与集合相互转换、增强 for 循环遍历、匿名数组传递以及利用 `Arrays.equals()` 比较数组内容。这些技巧能提升代码的灵活性和可读性,适用于更复杂的数据处理场景。
42 10