首页 > 其他分享 >数组模拟环形队列的思路及代码

数组模拟环形队列的思路及代码

时间：2023-04-08 13:56:20浏览次数：39  
标签：队列 环形 数组 front 数据 rear

JAVA实现数组模拟环形队列的思路及代码

前言

在对Java实现数组模拟队列零了解的情况下，建议先去阅读《JAVA实现数组模拟单向队列的思路及代码》一文，可以辅助理解本文核心思想。

一、环形数组队列

实现：让数组达到复用的效果，即：当我们从数组队列中取出了数据，那取出数据后后这个空间可以再次使用。

二、创建环形数组队列类前思考

单向数组队列实现中，我们设立了如下几个类属性及其含义：

  1. front：用于指向队列头部前一个的位置
  2. rear：用于指向队列尾部，用来指向队列尾部数据的一个指针
  3. maxSize：代表创建的该单向队列数组的最大存储容量
  4. front和rear的初始值都是-1。

那么我们将如何确立环形数组队列类属性的含义才能达到我们的目的呢？

  1. front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
  2. rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定，(即尾索引的下一个为头索引时表示队列满)
  3. 所以我们将front和rear的初始值都设为0
  4. maxSize - 1：代表创建的该环形队列数组的最大存储容量，其中留下一个空间作为约定
  5. 什么是空出一个空间做约定？

看完以上属性的定义，我们来先思考以下几个公式实现环形数组队列的原因：

  • 当队列已满的条件公式：(rear + 1) % maxSize == front
  • 当队列为空的条件公式：rear == front
  • 队列中有效的成员的个数条件公式：(rear + maxSize - front) % maxSize

看完以上公式，我想现在的你恐怕已经开始陷入迷茫当中了，为什么这样定义类属性就可以实现环形数组队列？

请别着急，我们将逐一进行图解分析！

三、环形数组队列类属性的含义图解及代码实现

根据以上属性定义，较单向数组队列来说，仅仅只是队列前后指针标识初始位置发生变化（front = rear = 0）

①环形数组队列类的初始设计

/**
 * ClassName: AnnularArrQueue
 * Package: com.zhao.test
 * Description:
 *
 * @Author XH-zhao
 * @Create 2023/3/25 20:18
 * @Version 1.0
 */
public class AnnularArrQueue {
    private final int[] arrQueue;   // 创建的数组队列的地址引用
    private final int arrMaxSize;   // 代表创建的该环形队列数组的容量，及队列最大容量+一个作为rear指针标识的约定
    private int front;  // 用于指向队列头部的位置
    private int rear;   // 用于指向队列尾部成员的后一个空间（约定）

    /**
     * 环形数组队列构造函数
     *
     * @param arrMaxSize 传入想要构造的队列长度
     */
    public AnnularArrQueue(int arrMaxSize) {
        this.arrMaxSize = arrMaxSize;
        arrQueue = new int[this.arrMaxSize];
        // 将前后标记均指向队列的最前方（0位置）
        front = 0;
        rear = 0;
    }
}

class Test {
    public static void main(String[] args) {
        // 创建一个环形数组队列
        AnnularArrQueue annularArrQueue = new AnnularArrQueue(4);
    }
}

通过以上环形数组队列类的设计，就可创建一个如下的环形数组队列对象。（当然，目前还没有实现环形的作用）

image-20230325211545371

②判断环形数组队列是否为空

当队列为空的条件公式：rear == front

公式图解：

当队列前后指针相等时环形数组队列为空，这一点和单向数组队列没有什么区别。

这一点也很好理解，即从rear=front=0开始，增加第一个队列成员时，rear要向前移一位，此时front指向该队列成员。

image-20230325215616430

当我们拿取Member1后，front向后移动就会再次和rear相等，此时队列为空。

image-20230325225739449

代码实现：

/**
 * 判断环形队列是否为空
 *
 * @return
 */
public boolean isEmpty() {
    return front == rear; // 队列头部指针==队列尾部指针，说明队列为空
}

③预留一个空间作为约定的作用

在判断队列是否为满之前，我们先来理解一下上文所说的预留一个数组空间做约定的含义。

我们可以通过如下我从网上获取的分析图片来理解一下为什么要存在一个数组空间作为约定。

从图中我们可以看出，如果我们不去预留一个空间做约定的话，rear指针继续向前装队列成员，以至于rear指针与front指针相等，但是此刻环形数组却是满的状态，无法通过rear==front来判断环形队列到底是空还是满的状态，所以要牺牲一个数组空间作为约定，让rear在向后移的过程中判断是否将要和front相遇，来确定是否停止添加队列成员。所以也解释了为什么（maxSize - 1）作为该环形队列数组的最大存储容量。

image-20230325232233907

④判断环形数组队列是否为满

当队列已满的条件公式：(rear + 1) % maxSize == front

公式图解：

通过上述说明我们知道，环形队列的实现需要牺牲一个数组空间作为约定。我们知道如果环形队列满了，那么rear指针和front之间的距离就只差一个约定空间就可以实现rear==front，那这样的话我们可以设想如下两种环形数组队列满了的情况。

情况一：rear指针在front指针之后

image-20230326000254234

即为rear绕到了front的后面，在这种情况下，rear + 1 == front 等价于【(rear + 1) % maxSize == front】即能证明环形队列已满。

情况二：rear指针在front指针之前

image-20230325235822624

在这种情况下，我们发现rear + 1 == maxSize ！= front 所以不能以 rear + 1 == front 作为判断环形数组队列已满的条件。

【(rear + 1) % maxSize == front】仍能适用于此情况。

所以通过判断【(rear + 1) % maxSize == front】即可判断环形数组是否已满。

代码实现：

/**
 * 判断环形队列是否已满
 *
 * @return
 */
public boolean isFull() {
    return (rear + 1) % arrMaxSize == front;
}

⑤完善环形队列增添和拿取队列成员的方法

代码实现：

/**
 * 添加队列成员到队列
 *
 * @param member
 */
public void addQueueMember(int member) {
    // 判断队列是否已满
    if (isFull()) {
        System.out.println("队列已满，不能往队列中添加数据。");
        return;
    }
    arrQueue[rear] = member;    // 直接将数据加入
    rear = (rear + 1) % arrMaxSize; // 将rear后移,考虑取模,即当rear到数组末尾时取模归零
}

/**
 * 从队列中拿取队列成员
 *
 * @return
 */
public int getQueueMember() {
    // 判断队列是否为空
    if (isEmpty()) {
        throw new RuntimeException("队列为空，不能从队列获取数据。");
    }
    int value = arrQueue[front];    // 先把front对应的值保留到一个临时变量
    front = (front + 1) % arrMaxSize;   // 将front后移,考虑取模,即当front到数组末尾时取模归零
    return value;   // 将临时保存的变量返回
}

⑥理解环形队列有效成员个数

即环形数组中从front开始到rear结束的成员个数

队列中有效的成员的个数条件公式：(rear + maxSize - front) % maxSize

公式图解：

情况一：rear在front之前

image-20230326004457031

情况二：rear在front之后

image-20230326005806093

代码实现：

/**
 * 求出当前队列有效成员的个数
 *
 * @return
 */
public int validMemberNum() {
    return (rear + arrMaxSize - front) % arrMaxSize;
}

⑦增加获取队列头成员和展示所有队列成员的方法实现

代码实现：

/**
 * 显示队列中所有成员
 */
public void showQueueMemberAll() {
    if (isEmpty()) {
        System.out.println("队列是空的，没有数据。");
    }
    // 从front开始遍历，遍历多少个元素
    for (int i = front; i < front + validMemberNum(); i++) {
        System.out.printf("arr[%d]=%d\n", i % arrMaxSize, arrQueue[i % arrMaxSize]);
    }
}

/**
 * 显示队列的头部成员
 *
 * @return
 */
public int headQueueMember() {
    if (isEmpty()) {
        throw new RuntimeException("队列是空的，没有数据。");
    }
    return arrQueue[front];
}

四、实验测试环形数组队列的代码准确性

①环形队列实现以及测试的整体代码


import java.util.Scanner;

/**
 * ClassName: AnnularArrQueue
 * Package: com.zhao.test
 * Description:
 *
 * @Author XH-zhao
 * @Create 2023/3/25 20:18
 * @Version 1.0
 */
public class AnnularArrQueue {
    private final int[] arrQueue;   // 创建的数组队列的地址引用
    private final int arrMaxSize;   // 代表创建的该环形队列数组的容量，及队列最大容量+一个作为rear指针标识的约定
    private int front;  // 用于指向队列头部的位置
    private int rear;   // 用于指向队列尾部成员的后一个空间（约定）

    /**
     * 环形数组队列构造函数
     *
     * @param arrMaxSize 传入想要构造的队列长度
     */
    public AnnularArrQueue(int arrMaxSize) {
        this.arrMaxSize = arrMaxSize;
        arrQueue = new int[this.arrMaxSize];
        // 将前后标记均指向队列的最前方（0位置），默认即为0，所以这里也可以省略显式赋值
        front = 0;
        rear = 0;
    }

    /**
     * 判断环形队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;   // 队列头部指针==队列尾部指针，说明队列为空
    }

    /**
     * 判断环形队列是否已满
     *
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % arrMaxSize == front;
    }

    /**
     * 添加队列成员到队列
     *
     * @param member
     */
    public void addQueueMember(int member) {
        // 判断队列是否已满
        if (isFull()) {
            System.out.println("队列已满，不能往队列中添加数据。");
            return;
        }
        arrQueue[rear] = member;    // 直接将数据加入
        rear = (rear + 1) % arrMaxSize; // 将rear后移,考虑取模,即当rear到数组末尾时取模归零
    }

    /**
     * 从队列中拿取队列成员
     *
     * @return
     */
    public int getQueueMember() {
        // 判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空，不能从队列获取数据。");
        }
        int value = arrQueue[front];    // 先把front对应的值保留到一个临时变量
        front = (front + 1) % arrMaxSize;   // 将front后移,考虑取模,即当front到数组末尾时取模归零
        return value;   // 将临时保存的变量返回
    }

    /**
     * 求出当前队列有效成员的个数
     *
     * @return
     */
    public int validMemberNum() {
        return (rear + arrMaxSize - front) % arrMaxSize;
    }

    /**
     * 显示队列中所有成员
     */
    public void showQueueMemberAll() {
        if (isEmpty()) {
            System.out.println("队列是空的，没有数据。");
        }
        // 从front开始遍历，遍历多少个元素
        for (int i = front; i < front + validMemberNum(); i++) {
            System.out.printf("arr[%d]=%d\n", i % arrMaxSize, arrQueue[i % arrMaxSize]);
        }
    }

    /**
     * 显示队列的头部成员
     *
     * @return
     */
    public int headQueueMember() {
        if (isEmpty()) {
            throw new RuntimeException("队列是空的，没有数据。");
        }
        return arrQueue[front];
    }

}

class Test {
    public static void main(String[] args) {
        //测试--创建一个队列
        AnnularArrQueue queue = new AnnularArrQueue(4);
        char key = ' ';// 接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;

        while (loop) {

            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");

            key = scanner.next().charAt(0); // 接收用户输入的第一个字符

            switch (key) {
                case 's' -> queue.showQueueMemberAll();
                case 'e' -> {
                    scanner.close();
                    loop = false;
                    System.out.println("程序退出");
                }
                case 'a' -> {
                    System.out.println("请输入一个整数");
                    int a = scanner.nextInt();
                    queue.addQueueMember(a);
                }
                case 'g' -> {
                    try {
                        int res = queue.getQueueMember();
                        System.out.println(res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                }
                case 'h' -> {
                    try {
                        int head = queue.headQueueMember();
                        System.out.println(head);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                }
            }
        }
    }
}

②测试结果

s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
队列是空的，没有数据。
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
2
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
arr[0]=2
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
3
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
arr[0]=2
arr[1]=3
arr[2]=5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
9
队列已满，不能往队列中添加数据。
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
arr[0]=2
arr[1]=3
arr[2]=5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
2
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
arr[1]=3
arr[2]=5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
3
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
队列为空，不能从队列获取数据。
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
队列是空的，没有数据。
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
3
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
h
3
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
h
3
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
e
程序退出

五、实验总结

从上述整体实验中可以看出，环形数组队列类的设计，完全呈现出了队列存储数据先进先出的特点。同时实现数组空间复用的效果！

标签：队列,环形,数组,front,数据,rear
From： https://www.cnblogs.com/zhao-XH/p/17298404.html

相关文章

  • 数组模拟单向队列的思路及代码
    JAVA实现数组模拟单向队列的思路及代码一、什么是队列？队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称......
  • 剑指offer66(Java)-构建乘积数组（中等）
    题目：给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1]，其中 B[i]的值是数组A中除了下标i以外的元素的积,即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24] 提示：所有元素乘积之和不会......
  • 剑指offer03(Java)-数组中重复的数字（简单）
    题目：找出数组中重复的数字。在一个长度为n的数组nums里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例1：输入：[2,3,1,0,2,5,3]输出：2或3 限制：2<=n<=1000......
  • 颜色分类(数组、双指针)、排列序列(递归、数学)、合并区间(数组、排序)
    颜色分类(数组、双指针)给定一个包含红色、白色和蓝色，一共n__个元素的数组，**原地(https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数0、1和2分别表示红色、......
  • JavaScript遍历数组用splice方法删除元素，这样写可能有遗漏，你遇到过吗？
    在编写“圳品”信息系统中，有时需要对二维数组中的数据进行筛选并删除一些元素，比如删除二维数组中首个元素为0的行。开始是用for循环访问数组+splice方法删除元素来做：vara=newArray([0,0,0,0],[1,1,1,1],[0,2,2,2],[......
  • 26. 删除有序数组中的重复项 & 80. 删除有序数组中的重复项 II
    力扣题目链接（26）给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重......
  • js数组对象如何改变里面对象键名
    方法二中，怎么就通过改变item，arr的值就直接改变了的呢?在JavaScript中，对象是引用类型，当你将一个对象赋值给一个变量时，实际上是将该对象的引用赋值给了变量，而不是复制了该对象本身letobj={name:'jack',age:23}letobj_son=obj;obj_son.name='tome'console.log(obj......
  • 一维数组的应用举例
    案例1从键盘读入学生成绩，找出最高分，并输出学生成绩等级成绩>=最高分-10等级为’A’成绩>=最高分-20等级为’B’成绩>=最高分-30等级为’C’其余等级为’D’提示：先读入学生人数，根据人数创建int数组，存放学生成绩。publicstaticvoidScoreTest(){//提示......
  • LeetCode习题——在排序数组中查找元素的第一个和最后一个位置（二分查找）
    在排序数组中查找元素的第一个和最后一个位置力扣链接：在排序数组中查找元素的第一个和最后一个位置题目给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target，返回[-1,-1]。你......
  • 数组遍历方法: map、filter、forEach
    区别map叫映射，可以重新赋值，拼接用+号，值+另外的值得新值filter叫筛选数组，可以重新赋值，用><=号，比较筛选值forEach叫跟for循环一样，不可以重新赋值......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99