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

数组,模拟,环形,队列,思路,代码 · 浏览次数 : 46

小编点评

**测试结果**s(show):显示队列e(exit):退出程序a(add):添加数据到队列g(get):从队列取出数据h(head):查看队列头的数据 **s(show):显示队列e(exit):退出程序a(add):添加数据到队列g(get):从队列取出数据h(head):查看队列头的数据a请输入一个整数3s(show):显示队列e(exit):退出程序a(add):添加数据到队列g(get):从队列取出数据h(head):查看队列头的数据a请输入一个整数5s(show):显示队列e(exit):退出程序a(add):添加数据到队列g(get):从队列取出数据h(head):查看队列头的数据h3s(show):显示队列e(exit):退出程序a(add):添加数据到队列g(get):从队列取出数据h(head):查看队列头的数据e程序退出五、实验总结从 above整体实验中可以看出，环形数组队列类的设计，完全呈现出了队列存储数据先进先出的特点。同时实现数组空间复用的效果！

正文

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
程序退出

五、实验总结

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

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

与数组模拟环形队列的思路及代码相似的内容：

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

JAVA实现数组模拟环形队列的思路及代码 前言 在对Java实现数组模拟队列零了解的情况下，建议先去阅读《JAVA实现数组模拟单向队列的思路及代码》一文，可以辅助理解本文核心思想。 一、环形数组队列 实现：让数组达到复用的效果，即：当我们从数组队列中取出了数据，那取出数据后后这个空间可以再次使用。

数组 模拟 环形 队列
46
Jupyter Notebook入门指南

Jupyter Notebook是一套基于web的交互式开发环境。用户可以在线开发和分享包含代码和输出的交互式文档，支持实时代码，数学方程，可视化和 markdown等。用途包括：数据清理和转换，数值模拟，统计建模，机器学习等等。

jupyter notebook 入门 指南
453
mock server 基础篇

1- mock 基础 mock翻译过来是‘模拟’的意思，也就是模拟接口返回的信息，用已有的信息替换接口返回的信息，从而提供仿真环境，实现模拟数据下的功能测试 因为在实际的项目研发过程中，我们经常会遇到如下的尴尬场景： 前端开发依赖于后端接口数据，但是后台人员不足或者无法立即到位，前端迟迟不能开工，或

mock server 基础
6
POWERBI_1分钟学会_连续上升或下降指标监控

一：数据源 模拟数据为三款奶茶销量的日销售数据源，日期是23.8.24-23.8.31。A产品为连续7天，日环比下降，B产品为连续3天，日环比下降，C产品为连续2天，日环比下降。 二：建立基础度量值 首先，我们建立两个基础度量值，计算我们的产品销量和日环比。 产品销量 = CALCULATE(SUM

powerbi 分钟 学会 连续
58
初识上位机（下）：C#读写PLC数据块数据

作为一个工业自动化领域的程序员，不懂点PLC和上位机，貌似有点说不过去。这里我用两篇小文带你快速进入上位机开发领域。上一篇，我们搭建了一个PLC的模拟仿真环境，本篇我们使用C#开发一个简单的PLC数据读取和写入的应用程序。

plc
0
C#S7.NET实现西门子PLCDB块数据采集的完整步骤

前言 本文介绍了如何使用S7.NET库实现对西门子PLC DB块数据的读写，记录了使用计算机仿真，模拟PLC，自至完成测试的详细流程，并重点介绍了在这个过程中的易错点，供参考。 用到的软件： 1.Windows环境下链路层网络访问的行业标准工具（WinPcap_4_1_3.exe）下载链接：http

s7 net plcdb
179
C#使用MX Component实现三菱PLC软元件数据采集的完整步骤（仿真）

前言 本文介绍了如何使用三菱提供的MX Component插件实现对三菱PLC软元件数据的读写，记录了使用计算机仿真，模拟PLC，直至完成测试的详细流程，并重点介绍了在这个过程中的易错点，供参考。 用到的软件： 1. PLC开发编程环境GX Works2，GX Works2下载链接 https://

mx component plc
230
python入门基础(15)--模块和python中数学、日期、时间类模块。

接上篇，当我们创建了很多类，比如 图书馆里的藏书，分社会科学类，艺术类、生活类、农业类、工业类等，而工业类又分为轻工业、重工业、信息工业，然后再细分。当分的越来越细时，程序就会越来越大。如何管理，便成了程序开发过程中一个重要的环节。于是可以按照图书馆分类管理的思想，对程序代码进行管理。 将一个应用程

python 入门 基础 模块
60
#Python pandas库，读取模块，代码笔记

日常数据清洗中，利用python清洗的第一步就是读取对应文件，今天一起复盘一下数据读取环节的常规操作。 csv和xlsx格式读取类似，所以用csv做案例 X-MIND图

python pandas 读取 模块
13
突破传统监测模式：业务状态监控HM的新思路

在系统架构设计中非常重要的一环是要做数据监控和数据最终一致性，这里主要讲如何去补偿？补偿的方案哪些？这就引出来数据监控系统了。有小伙伴会问了，为什么业务状态监控系统可以做补偿？别急，且看本文。

突破 传统 监测 模式
84
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.