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

数组模拟单向队列的思路及代码

时间：2023-04-08 13:56:01浏览次数：35  
标签：arr return 队列 单向 数组 front 数据

JAVA实现数组模拟单向队列的思路及代码

一、什么是队列？

队列是一种特殊的线性表 ，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。 进行插入操作的端称为队尾，进行删除操作的端称为队头。 队列中没有元素时，称为空队列。 队列的数据元素又称为队列元素。

二、队列的特点及存储数据的方式

  1. 队列是一种先进先出的线性存储结构，即谁先入队谁就先出队列。

image-20230325154503356

三、创建单向数组队列类前思考

考虑到单向队列存取数据的特点，要想创建一个单向数组队列类，我们需要设立如下几个类属性：

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

以上属性的定义在如下代码预设计中可以体会的更加深刻，继续往下看！

四、单向数组队列类的预设计

①单向数组队列类的初始设计

/**
 * ClassName: directionalArrQueue
 * Package: com.zhao.test
 * Description:
 *
 * @Author XH-zhao
 * @Create 2023/3/25 16:04
 * @Version 1.0
 */
public class DirectionalArrQueue {

    private final int[] arrQueue;   // 创建的数组队列的地址引用
    private final int arrMaxSize;   // 代表创建的该单向队列数组的最大存储容量
    private int front;  // 用于指向队列头部前一个的位置
    private int rear;   // 用于指向队列尾部，用来指向队列尾部数据的一个指针

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

}

class test{
    public static void main(String[] args) {
        // 创建一个单向数组队列
        DirectionalArrQueue queue = new DirectionalArrQueue(4);
    }
}

通过以上单向数组队列类的设计，就可创建一个如下的单向数组队列对象。

②判断数组队列是否为空或为满

从前后两个指针标记角度考虑，由于rear的初始值为-1，增加队列成员的时候rear指针肯定要先向前移一位，再将队列成员的值添加到队列当中，在拿取队列成员的时候，front指针标记也是一样，要先向前移一位然后拿取对应指针下标标记的队列成员（由于对应下标的队列成员已经被取出，所以我们描述front的含义时说其总是指向队列头部前一个的位置）。

由上述增添和拿取队列成员的过程可以发现，每当两个指针相遇时（即rear == front），队列便是空的状态。

从上述增添队列成员过程中对rear标记的描述中，我们可以发现每次添加完队列成员后，rear标记总是指向队列尾部成员。所以我们可以推断出当rear位于数组队列最后的时候（即rear == arrMaxSize - 1），可以判定为队列已经满了。

/**
 * 判断该队列是否为空
 * @return
 */
public boolean isNull() {
    return rear == front;
}

/**
 * 判断该队列是否已经存满了数据
 * @return
 */
public boolean isFull() {
    return rear == arrMaxSize - 1;
}

代码测试：

public static void main(String[] args) {
    // 创建一个单向数组队列
    DirectionalArrQueue queue = new DirectionalArrQueue(4);

    // 判断队列是否为空
    boolean aNull = queue.isNull();
    System.out.println("队列是否为空:" + aNull);

    // 判断队列是否为满
    boolean full = queue.isFull();
    System.out.println("队列是否为满:" + full);
}

测试结果：

队列是否为空:true
队列是否为满:false

由于我们还没有完善增添和拿取队列成员的方法，所以此刻的单向队列queue肯定是空的。

③完善数组队列增添和拿取队列成员的方法

在充分理解②中我对增添和拿取队列成员的描述中，front和rear的含义以及标记的移动过程的情况下，理解如下增添和拿取队列成员的方法实现。

/**
 * 添加队列成员到队列
 *
 * @param member
 */
public void addQueueMember(int member) {
    // 先判断该队列是否满了,如果没满,则可以把数据添加到该队列
    if (isFull()) {
        System.out.println("该数列已满,不能再添加数据了");
        return;
    }
    // 该队列没满的情况下执行下面的代码
    rear++;
    arrQueue[rear] = member;
}

/**
 * 从队列中拿取队列成员
 *
 * @return
 */
public int getQueueMember() {
    // 从队列取队列成员时,先判断该队列是否为空
    if (isNull()) {
        // 如果执行到这里,就代表该队列是空的,所以执行时,抛出一个异常
        throw new RuntimeException("该队列为空,不能再进行出列操作了");
        // 抛出异常之后，就自己return了,所以不用再写return了，再在这个异常下面写代码就会
        // 之所以使用抛异常的方式结束,而不使用return 0;是因为防止成员队列就是数值0,产生误导
    }
    front++;    // front后移
    return arrQueue[front]; // 把从队列中取到的队列成员返回
}

后续为方便整体测试代码，不再逐步对方法进行测试，查看测试结果请继续往下学习！

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

/**
 * 得到队列的第一个队列成员,即头部成员注意 不是取出头部成员，无需对front做++操作
 *
 * @return
 */
public int getHeadMember() {
    if (isNull()) {
        // 如果队列为空,则抛出异常
        throw new RuntimeException("该队列为空,取不到头部数据");
    }
    // 这里只是显示头部成员,所以front指针不往后移,只需要在arr[]中让front+1就可以了。
    return arrQueue[front + 1];
}

/**
 * 显示队列的所有成员
 */
public void showAllMember() {
    // 先判断该队列是否为空
    if (isNull()) {
        System.out.println("该队列为空,取不到数据");
        return;
    }
    for (int i = 0; i < arrQueue.length; i++) {
        System.out.printf("arr[%d]=%d\n", i, arrQueue[i]);
    }
}

五、实验测试单向数组队列的代码准确性

①单向队列实现以及测试的整体代码


import java.util.Scanner;

/**
 * ClassName: directionalArrQueue
 * Package: com.zhao.test
 * Description:
 *
 * @Author XH-zhao
 * @Create 2023/3/25 16:04
 * @Version 1.0
 */
public class DirectionalArrQueue {

    private final int[] arrQueue;   // 创建的数组队列的地址引用
    private final int arrMaxSize;   // 代表创建的该单向队列数组的最大存储容量
    private int front;  // 用于指向队列头部前一个的位置
    private int rear;   // 用于指向队列尾部，用来指向队列尾部数据的一个指针

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

    /**
     * 判断该队列是否为空
     *
     * @return
     */
    public boolean isNull() {
        return rear == front;
    }

    /**
     * 判断该队列是否已经存满了数据
     *
     * @return
     */
    public boolean isFull() {
        return rear == arrMaxSize - 1;
    }

    /**
     * 添加队列成员到队列
     *
     * @param member
     */
    public void addQueueMember(int member) {
        // 先判断该队列是否满了,如果没满,则可以把数据添加到该队列
        if (isFull()) {
            System.out.println("该数列已满,不能再添加数据了");
            return;
        }
        // 该队列没满的情况下执行下面的代码
        rear++;
        arrQueue[rear] = member;
    }

    /**
     * 从队列中拿取队列成员
     *
     * @return
     */
    public int getQueueMember() {
        // 从队列取队列成员时,先判断该队列是否为空
        if (isNull()) {
            // 如果执行到这里,就代表该队列是空的,所以执行时,抛出一个异常
            throw new RuntimeException("该队列为空,不能再进行出列操作了");
            // 抛出异常之后，就自己return了,所以不用再写return了，再在这个异常下面写代码就会
            // 之所以使用抛异常的方式结束,而不使用return 0;是因为防止成员队列就是数值0,产生误导
        }
        front++;    // front后移
        return arrQueue[front]; // 把从队列中取到的队列成员返回
    }

    /**
     * 得到队列的第一个队列成员,即头部成员注意 不是取出头部成员，无需对front做++操作
     *
     * @return
     */
    public int getHeadMember() {
        if (isNull()) {
            // 如果队列为空,则抛出异常
            throw new RuntimeException("该队列为空,取不到头部数据");
        }
        // 这里只是显示头部成员,所以front指针不往后移,只需要在arr[]中让front+1就可以了。
        return arrQueue[front + 1];
    }

    /**
     * 显示队列的所有成员
     */
    public void showAllMember() {
        // 先判断该队列是否为空
        if (isNull()) {
            System.out.println("该队列为空,取不到数据");
            return;
        }
        for (int i = 0; i < arrQueue.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arrQueue[i]);
        }
    }

}

class test {
    public static void main(String[] args) {
        //测试--创建一个队列
        DirectionalArrQueue queue = new DirectionalArrQueue(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.showAllMember();
                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.getHeadMember();
                        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
arr[1]=0
arr[2]=0
arr[3]=0
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
2
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):查看队列头的数据
s
arr[0]=2
arr[1]=3
arr[2]=0
arr[3]=0
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
arr[3]=0
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
3
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
h
5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
arr[0]=2
arr[1]=3
arr[2]=5
arr[3]=0
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
7
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
s
arr[0]=2
arr[1]=3
arr[2]=5
arr[3]=7
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
8
该数列已满,不能再添加数据了
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
5
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
7
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
g
该队列为空,不能再进行出列操作了
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据
a
请输入一个整数
2
该数列已满,不能再添加数据了
s(show):显示队列
e(exit):退出程序
a(add):添加数据到队列
g(get):从队列取出数据
h(head):查看队列头的数据

六、实验总结

从上述整体实验中可以看出，单向数组队列类的设计，完全呈现出了队列存储数据先进先出的特点。

单向数组队列的缺点

但在其中我们发现，单向数组队列存在一个明显的缺点，它是"一次性"的。在队列增添和拿取队列成员的过程中，前后标记指针在不断往队列数组的末端移动，导致就算队列数组前面的成员被取出之后，队列数组前面的数组空间不能复用，导致我们的队列顶多只能添加并拿取maxSize个成员。这很明显不是我们想要的！

那么我们如何将取出后的数组队列空间复用呢？

答案是实现环形数组队列！如何实现环形数组队列，我将在《JAVA实现数组模拟环形队列的思路及代码》一问中说明。

标签：arr,return,队列,单向,数组,front,数据
From： https://www.cnblogs.com/zhao-XH/p/17298403.html

相关文章

  • 剑指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循环一样，不可以重新赋值......
  • 1250. 检查「好数组」
    题目链接：1250.检查「好数组」方法：最大公约数gcd裴蜀定理简介（1）若\(a,b\)是整数，且\(gcd(a,b)=d\)，那么对于任意的整数\(x，y\)，\(ax+by\)都一定是\(d\)的倍数，特别地，一定存在整数\(x，y\)，使\(ax+by=d\)成立。（2）推论：\(a,b\)互质gcd(a,b)=1的充分必要条件是存在整数\(x，y\)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99