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

一、什么是队列？

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

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

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

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

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

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实现数组模拟环形队列的思路及代码》一问中说明。

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 类模板实现简单的数组
• 用jacoco统计JAVA项目测试代码覆盖率
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• GDB调试之源代码查看与管理(六)
• 写代码时如何合理的画图表达逻辑结构
• 十行python代码实现文件去重，去除重复文件的脚本
• 第二章 Spring Boot 整合 Kafka消息队列 生产者
• 数组内存图
• [代码随想录] 第四天

队列 数组 单向 思路 代码队列 数组 单向 思路 环形 队列 数组 思路 数组leetcode思路33 队列 数组 队列 数组 字典 容器 题解 数组 思路pta 末尾 数组 顺序 思路 数组 队列spfa bfs 思路 代码 数据结构 队列 数组 结构