• Java数据结构：使用数组模拟队列（队列与环形队列）

    在这里插入图片描述

    文章目录

    1 队列

    1.1 何为队列及实现思路

    何为队列？

    • 队列是一个有序列表，可以通过数组或者链表来实现；
    • 满足：先存入的数据先取出，后存入的数据后取出，即 先入先出。

    实现思路：
    在这里插入图片描述

    1. 队列本身是有序列表，可以使用数组进行模拟，上图所示，maxSize为队列的最大容量；
    2. 由于队列先入先出的特点，分别使用front和rear记录队列的队首与队尾，其中front指向队首的前一个位置，rear指向队尾（实际值）；
    3. 当入队操作完成时，则相应的rear要发生变化，如图（入队三个元素时），此时数组0、1、2索引都有值，rear指向队尾，即索引为2的位置；
    4. 取出队首元素时，由于front指向的是队尾的前一个元素，所以需要先让front自增1，而后再取值，即第一次取出时，front=0对应的为队首元素；
    5. 当front = rear时队列为空，当rear=maxSize-1，即队尾指向数组末尾，说明队列已满，在设计入队和出队方法时需要特别注意！

    1.2 数组模拟队列ArrayQueue的实现

    详细可见代码注释，ArrayQueue.java参考代码如下：

    /**
 * 使用数组模拟队列 ArrayQueue类
 */
class ArrayQueue{
    private int maxSize; //数组的最大容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //用于存放数据

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; //指向队列头的前一个位置
        rear = -1; //指向队列尾部，指向具体的数据
    }

    //判断队列是否已满
    public boolean isFull(){
        return rear == maxSize-1;
    }

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

    //添加数据到队列
    public void addQueue(int item){
        //先判断队列是否满
        if (isFull()){
            System.out.println("队列已满,不能加入数据");
            return;
        }
        //添加操作
        arr[++rear] = item; //rear后移，加入元素item
    }

    //获取队列的数据
    public int getQueue(){
        //判断是否为空
        if (isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        return arr[++front];
    }

    //显示当前队列中的所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("当前队列为空");
        }
        for (int i = front+1; i <= rear; i++) {
            System.out.printf("arr[%d] = %d\n", i, arr[i]);
        }
    }

    //显示头数据
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("当前队列为空!");
        }
        return arr[front+1];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65

    1.3 测试队列ArrayQueueDemo测试类的实现

    为了便于队列的测试，我们初始假定队列的最大元素数量为3，具体代码及结果如下：

    import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 使用数组模拟队列
 */
public class ArrayQueueDemo {

    public static void main(String[] args) {
        //创建一个最大元素数量为3的队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //菜单
        while (loop){
            System.out.println("s: 显示队列");
            System.out.println("e: 退出程序");
            System.out.println("a: 添加数据到队列");
            System.out.println("p: 查看头数据");
            System.out.println("g: 从队列里取出数据");
            key = scanner.next().charAt(0);
            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.print("请输入一个数字: ");
                    int item = scanner.nextInt();
                    arrayQueue.addQueue(item);
                    break;
                case 'g':
                    try {
                        int queue = arrayQueue.getQueue();
                        System.out.println("取出的数据是: " + queue);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'p':
                    try {
                        int peek = arrayQueue.peek();
                        System.out.println("查看的数据是: " + peek);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("已退出程序");
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    实现结果：

    s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 3
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 7
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
p
查看的数据是: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 3
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
s
arr[2] = 7
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
e
已退出程序

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    但是，经过笔者的反复测试，很快就发现了一个巨大的bug！
    比如：先让三个数入队，即先将队列存满。然后，让三个元素出队。此时理论上队列应该为空，但是当我继续入队一个元素时，结果如下:
    队列虽然为空，但是无法继续存储数据！
    在这里插入图片描述

    实际上，此时虽然满足front=rear，但队列的样子应该是这样的：
    在这里插入图片描述
    即 此时队列虽然看起来是满的，但是，实际没满， 相当于以这种方式实现队列属于一次性产品！因此，我们通过算法进行优化，引出 环形队列。

    2 环形队列

    2.1 环形队列简介及实现思路

    由于之前的方式会出现队列为满实际未满的情况，为了实现使用数组模拟队列，我们可以通过对前面的数组模拟队列进行优化，充分利用数组，即 将数组看成一个环形的（主要通过取模的方式来实现）。

    实现思路：

    1. front变量指向队首元素， 即arr[front]就是队列的第一个元素;

    2. rear变量指向队尾元素的后一个位置， 即arr[rear-1]为队尾元素。这么做的目的是为了空出一个空间，为了区分队列满和队列空的条件；

    3. 当队列满时：(rear+1)%maxSize = front。 在环形队列中，由于空出一个空间，则数组最多存放maxSize-1个元素，rear的最大值为maxSize-1;
      在这里插入图片描述

    4. 出队操作：(front+1)%maxSize = front，入队操作：(rear+1)%maxSize = rear；

    5. 当队列为空的时候：front = rear;
      在这里插入图片描述

    6. 队列中有效的数据个数为：(rear+maxSize-front)%maxSize。 也可以写成 abs(rear-front)%maxSize。

    • 当rear在front之后(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=rear-front=(rear+maxSize-front)%maxSize
    • 当rear在front之前(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=(rear+maxSize-front)%maxSize

    环形队列的图片出自：@csdn-所遇皆惊喜：数据结构 - 队列 && 环形队列（循环队列）

    2.2 数组模拟环形队列CircleArrayQueue的实现

    详细可见代码注释，CircleArrayQueue.java参考代码如下：

    /**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 数组模拟环形队列
 */
public class CircleArrayQueue {
    private int maxSize; //数组的最大容量
    private int front; //队列头
    private int rear; //队列尾后一个元素
    private int[] arr; //用于存放数据

    //创建队列的构造器
    public CircleArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }

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

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

    //添加数据到队列
    public void addQueue(int item){
        //先判断队列是否满
        if (isFull()){
            System.out.println("队列已满,不能加入数据");
            return;
        }
        //添加操作
        arr[rear] = item; //直接添加, 因为rear指向队尾后一个位置
        rear = (rear + 1) % maxSize; //rear后移
    }

    //获取队列的数据
    public int getQueue(){
        //判断是否为空
        if (isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        //1.先把front对应的值保存
        int value = arr[front];
        //2.front后移
        front = (front + 1) % maxSize;
        return value;
    }

    //返回有效数据的个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }

    //显示当前队列中的所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("当前队列为空");
        }
        //注意取模
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i%maxSize]);
        }
    }

    //显示头数据
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("当前队列为空!");
        }
        return arr[front];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    2.3 测试队列CircleArrayQueueDemo测试类的实现

    为了便于队列的测试，我们还是初始假定队列的最大元素数量为3，具体代码及结果如下：

    import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 测试环形队列
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个最大元素数量为3的队列
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //菜单
        while (loop){
            System.out.println("s: 显示队列");
            System.out.println("e: 退出程序");
            System.out.println("a: 添加数据到队列");
            System.out.println("p: 查看头数据");
            System.out.println("g: 从队列里取出数据");
            key = scanner.next().charAt(0);
            switch (key){
                case 's':
                    circleArrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.print("请输入一个数字: ");
                    int item = scanner.nextInt();
                    circleArrayQueue.addQueue(item);
                    break;
                case 'g':
                    try {
                        int queue = circleArrayQueue.getQueue();
                        System.out.println("取出的数据是: " + queue);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'p':
                    try {
                        int peek = circleArrayQueue.peek();
                        System.out.println("查看的数据是: " + peek);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("已退出程序");
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    结果如下：

    s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 2
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 3
队列已满,不能加入数据
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 2
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
java.lang.RuntimeException: 当前队列为空
	at com.hxh.queue.CircleArrayQueue.getQueue(CircleArrayQueue.java:48)
	at com.hxh.queue.CircleArrayQueueDemo.main(CircleArrayQueueDemo.java:36)
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
s
arr[2] = 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
e
已退出程序

Process finished with exit code 0

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    可见，最大有效数量由于一个置空位置，由3变成了2。当两个元素入队后，将两个元素出队，再次入队，可以成功入队。说明，将数组看成环形数组，通过取模运算可以解决之前的一次性使用的问题。

    写在最后

     本文被 Java数据结构 收录点击订阅专栏 ， 持续更新中。
     创作不易，如果你有任何问题，欢迎私信，感谢您的支持！
    在这里插入图片描述
    在这里插入图片描述

  • 相关阅读:
    【C++】：日期类实现
    网络协议--Traceroute程序
    vue setup：Options API 迁移至 Composition API 的一些语法要点
    星星的等级和财富水平
    String的字符串拼接
    Java HashMap 实现线程安全
    Kafka - Broker 详解
    使用1688开放平台API接口获取商品详情信息
    redis stream 实现消息队列
    Ubuntu 20.04使用源码安装nginx 1.14.0
  • 原文地址：https://blog.csdn.net/m0_60353039/article/details/127428465