数据结构与算法——队列

????????你们好，我是Benmao，本专栏永久免费，持续更新，喜欢可以收藏，讨厌可以吐槽。在此专栏我讲不断发表目前学习的数据结构与算法相关笔记，所以不是教程，用到的语言是Java语言。此外，向大家推荐学习Java的一个好帮手 笨猫编程手册，遇到有关Java的知识点可以进行查找，对数据结构与算法感兴趣的，可以收藏本栏目

---

目录

队列引入

队列介绍

数组模拟队列的思路? ? ??

缺陷与进一步优化

---

队列引入

????????想象一下，你有一群猫排成一列，它们想要进入一个箱子。但是，箱子只有一个入口，而且只能一个猫进去，一个猫出来。这就是队列的概念。

????????队列是一种线性数据结构，它遵循先进先出（First-In-First-Out，FIFO）的原则。就像排队买票一样，先来的人先买到票，后来的人需要等待前面的人买完才能买。

????????在队列中，新的元素被添加到队列的末尾，而从队列中移除元素的操作总是发生在队列的前端。这个过程称为入队（enqueue）和出队（dequeue）。

? ? ? ? 队列介绍

????????1. 队列是一个有序列表，可以用数组或是链表来实现（本文使用的是数组）

????????2. 遵循先入先出的原则。先存入队列的数据，先要取出；后存入队列的数据，要后去除????????

---

????????数组模拟队列的思路? ? ??

? ? ? ? 队列的主要操作包括：

• 入队（enqueue）：将元素添加到队列的末尾。
• 出队（dequeue）：从队列的前端移除并返回元素。
• 队列是否为空（isEmpty）：检查队列是否为空。
• 队列的大小（maxSize）：获取队列中元素的个数。

? ? ? ? 1. 首先，?我们需要知道，队列一旦创建，就像数组一样，长度是无法改变的，我们课通过数组来存储队列的元素，定义一个数组来存储队列的元素，以及两个指针front和rear分别指向队列的头部和尾部

????????2. 初始化队列时，这个时候队列没有任何元素，因此将front和rear都设置为-1，表示队列为空。

????????

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;//指向队列尾，有数据，队列最后一个数据
    }
}

? ? ? ? 3.?入队操作（enqueue）：

?? ?????????首先，检查队列是否已满，即rear是否指向数组的最后一个位置。如果已满，则无法入队。
?? ?????????如果队列不满，将rear指针向后移动一位，并将新元素存储在rear指向的位置。

?队列有效数据为：rear - front

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

//添加数据到队列
public void addQueue(int data) {
    //判断队列是否满
    if (isFull()) {
        System.out.println("队列满，不能添加数据");
        return;
    }
    arr[++rear] = data;
}

? ? ? ? 4.?出队操作（dequeue）：

?? ?????????首先，检查队列是否为空，即front和rear是否相等且都为-1。如果为空，则无法出队。
?? ?????????如果队列不为空，将front指针向后移动一位，表示出队一个元素。

//判断队列是否为空
public boolean isEmpty() {
    //当有数据出去的时候，front才会自增，随着数据一个共减少，front慢慢上升，达到与rear一样
    return rear == front;
}

//获取队列的数据，就是出队列
public int getQueue() {
    //判断队列是否为空
    if (isEmpty()) {
        throw new RuntimeException("队列为空，没有任何数据");
    }
    return arr[++front];
}

????????5. 获取队列头部元素（peek）：

?? ?????????首先，检查队列是否为空。如果为空，则无法获取头部元素。
?? ?????????如果队列不为空，返回front指针指向的元素。

//显示队列的头数据，注意不是取出数据
public int headQueue() {
    if (isEmpty()) {
         throw new RuntimeException("队列为空，没有任何数据");
    }
    return arr[front + 1];
}

? ? ? ? 6. 在运行测试时，可以通过遍历出队列数据来判断

//显示队列的所有数据
public void listQueue() {
    if (isEmpty()) {
        System.out.println("队列为空，没有数据");
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.printf("arr[%d]=%d\n", i, arr[i]);
    }
}

---

?????????缺陷与进一步优化

? ? ? ? 细心的博友可以发现，上述代码测试运行后，会发现一个问题，当一个队列长度为3，放满元素后，再出队列一个元素，发现再次添加元素后，发现队列已满，这是因为此队列是静态队列。想要解决这个问题，就得用动态队列，也就是环形队列，核心就是取模。

//通病：数组用完有多余的位置不能使用，相当于这个用数组实现的队列只能使用一次，不能复用

//优化：使用算法改为一个环形数组，核心就是取模?

?????????当rear指针到达数组的末尾时，可以选择将队列的元素整体向前移动，以便在数组的开头重新插入新的元素，从而实现循环队列的效果。

思路
????1.重新定义front变量：front指向队列第一个元素，也就是说arr[front]总是变量第一个元素，初始值为0
????2.重新定义rear变量：rear指向队列最后一个元素的后一个位置，初始值为0
??????解释，rear是从0开始，而最后一个元素为arr[maxSize-1], 银川需要空出一个空间作为约定
????3.当队列满时，条件为(rear+1)%maxSize=front
????4.当队列为空时，条件不变，rear=front
????5.队列中有效数据为rear-front, 但因为需要创建环形列表，加一个周期取模，隐藏判断队列的有效数据为(rear-front+maxSize)%maxSize

? ? ? ? ?以下是修改后的代码

class CircleArray {
    private int maxSize; //数组最大容量
    //front指向队列第一个元素,初始值为0
    private int front; //队列头，随着数据删除而自增
    //rear就指向队列最后一个元素的后一个位置，初始值为0
    private int rear; //队列尾，随着数据添加而自增
    private int[] arr; //用于存放数据，模拟队列

    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        //不用初始化赋值指针，因为默认自动为0
    }

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

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

    //添加数据到队列
    public void addQueue(int data) {
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列满，不能添加数据");
            return;
        }
        arr[rear] = data;
        //rear++
        rear = (rear + 1) % maxSize;
        //万一rear加过了maxSize，所有考虑取模
    }

    //获取队列的数据，就是出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有任何数据");
        }
        //这里需要知道front是指向队列第一个元素
        //1. 先把front对应的值保存到一个临时变量
        //2. 将front后移
        //3. 将临时保存的变量返回
        int value = arr[front];
        //也需要考虑数组越界，考虑取模
        front = (front + 1) % maxSize;
        return value;
    }

    //求出当前队列有效数据个数
    public int size() {
        return (rear - front + maxSize) % maxSize;
    }

    public void listQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
            return;
        }
        //思路，从第一个元素front开始变量，遍历有效数据
        for (int i = front; i < front + size(); i++) {
            //i可能超过数组长度，考虑取模
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有任何数据");
        }
        return arr[front];
    }

? ? ? ? 运行测试代码?

public static void main(String[] args) {
        //测试数组模拟环形队列
        System.out.println("测试数组模拟环形队列");
        //创建一个队列
        CircleArray circleArray = new CircleArray(4);//意思就是有效数据最大为3
        String key = "";
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            System.out.println("1:显示队列");
            System.out.println("2:退出程序");
            System.out.println("3:添加数据");
            System.out.println("4:取出数据");
            System.out.println("5:查看头部");
            key = scanner.next();
            switch (key) {
                case "1":
                    circleArray.listQueue();
                    break;
                case "2":
                    scanner.close();
                    loop = false;
                    break;
                case "3":
                    System.out.println("输出一个数字");
                    circleArray.addQueue(scanner.nextInt());
                    break;
                case "4":
                    try {
                        int res = circleArray.getQueue();
                        System.out.printf("取出的数据的%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "5":
                    try {
                        int res = circleArray.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                default:
                    break;
            }
        }
        System.out.println("已退出");
    }
}