Melonico
2021-03-15
734
blog
原创

Java数据结构——用数组实现队列并简单分析

队列

在这里插入图片描述

队列是一个有序列表，队列可以使用数组或者链表实现

队列遵循FIFO(先进先出)的原则，即根据元素存入队列的顺序取出元素，先进入队列的元素先出队列

在现实生活中，存在很多出现队列的场景，如当我们去食堂打饭时，就会出现排队的情况，后来的人排到队列的尾部，先来的人先打完饭然后离队，这就是一种存在队列的场景

用数组实现简单队列

初始化队列
// 初始化队列参数
public ArrayQueue(int maxSize) {
    this.maxSize = maxSize;
    arr = new int[maxSize];
    front = -1;
    rear = -1;
}

创建一个队列时传入一个整型表示该队列的最大容量，并创建一个数组

队头指向队列中第一个元素之前(不包含第一个元素)

队尾指向队列中最后一个元素(包含最后一个元素)

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

当队头队尾指向同一个位置时，则认为该队列为空

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

当队尾指向最大容量-1的位置时，则认为该队列已满

显示队列元素个数
// 获取元素个数
public int getNumOfQueue(){
    return rear - front;
}
显示队列
// 显示队列数据
public void showQueue(){
    if (queueIsEmpty()){
        throw new RuntimeException("队空，没有数据");
    }
    System.out.print("队列：");
    for (int i = front + 1; i <= rear; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println("队列元素个数为:" + getNumOfQueue());
}

当队列为空时，无法显示队列元素，则抛出异常并设置错误信息

入队
// 入队
public void addQueue(int n){
    if (queueIsFull()){
        throw new RuntimeException("队满，无法加入队列");
    }
    rear++; // 队尾后移
    arr[rear] = n;
}

当队列已满时，无法加入新的数据，则抛出一个异常并设置错误信息

当队列不满时，使队尾后移一位，并在改位置存入数据

获取元素（出队）
// 出队
public int getQueue(){
    if (queueIsEmpty()){
        throw new RuntimeException("队列为空，无法取出数据");
    }
    front++; // 队头后移
    return arr[front];
}

当队列为空时，无法获取数据，则抛出一个异常并设置错误信息

当队列不为空时，使队头后移一位，并输出该位置的数据

获取队头元素但不出队
/ 显示队头数据
public int peekQueueHead(){
    if (queueIsEmpty()){
        throw new RuntimeException("队空，没有队头数据");
    }
    return arr[front+1];
}

当队列为空时，无法显示队头数据，则抛出一个异常并设置错误信息

当队列不为空时，输出队头下一个位置的元素（因为这里队头指向的是第一个数据之前的一个位置，并不包含第一个数据）

完整代码
package dataStructures;

import java.util.Scanner;

/**
 * 用数组实现简单队列
 * @author Melonico
 */
public class Queue {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(15);
        Scanner sc = new Scanner(System.in);
        char key = ' '; // 接收用户输入
        boolean flag = true;
        // 显示菜单
        while (flag){
            System.out.println("s:显示队列");
            System.out.println("a:添加数据");
            System.out.println("g:获取数据");
            System.out.println("h:显示队头");
            System.out.println("e:退出程序");
            key = sc.next().charAt(0);
            switch (key){
                case 's' :
                    try {
                        arrayQueue.showQueue();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a' :
                    try {
                        System.out.println("输入一个数");
                        int num = sc.nextInt();
                        arrayQueue.addQueue(num);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g' :
                    try {
                        System.out.println("取出的数据是：" + arrayQueue.getQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h' :
                    try {
                        System.out.println("队头数据是：" + arrayQueue.peekQueueHead());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e' :
                    sc.close();
                    flag = false;
                default : break;
            }
        }
    }
}

// 使用数组模拟队列
class ArrayQueue {
    private int maxSize; // 表示队列的最大容量
    private int front; // 指向队头
    private int rear; // 指向队尾
    private int[] arr; // 模拟队列，存放数据

    public ArrayQueue() {
    }

    // 初始化队列参数
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }

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

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

    // 入队
    public void addQueue(int n){
        if (queueIsFull()){
            throw new RuntimeException("队满，无法加入队列");
        }
        rear++; // 队尾后移
        arr[rear] = n;
    }

    // 出队
    public int getQueue(){
        if (queueIsEmpty()){
            throw new RuntimeException("队列为空，无法取出数据");
        }
        front++; // 队头后移
        return arr[front];
    }

    // 显示队列数据
    public void showQueue(){
        if (queueIsEmpty()){
            throw new RuntimeException("队空，没有数据");
        }
        System.out.print("队列：");
        for (int i = front + 1; i <= rear; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("队列元素个数为:" + getNumOfQueue());
    }

    // 获取元素个数
    public int getNumOfQueue(){
        return rear - front;
    }

    // 显示队头数据
    public int peekQueueHead(){
        if (queueIsEmpty()){
            throw new RuntimeException("队空，没有队头数据");
        }
        return arr[front+1];
    }
}
该队列的缺点

假设存在一个最大容量为6的队列

在这里插入图片描述

此时，队头front和队尾rear都指向-1的位置

当执行入队操作后，队列情况变为

在这里插入图片描述

队头指向第一个元素的前一个位置，队尾指向最后一个元素的位置

当执行出队操作后

在这里插入图片描述

此时，当队尾指向arr[5]即最大容量-1的位置时判断该队已满，但是队头指向的位置和队头的前一个位置为空，而且这两个位置无法加入新的数据，资源因此被浪费掉

环形队列

为了解决上面简单队列使用一次后，之前的剩余空间无法再次使用的问题，我们可以使用环形队列来解决这个问题

为了实现环形队列，需要对front和rear的指向做出调整

在之前的简单队列中

  • front指向队列中第一个元素的前一个位置，初始值为-1
  • rear指向队列中最后一个元素，初始值为-1

在环形数组中，头尾的指向更改为

  • front指向队列中第一个元素，初始值为0
  • rear指向队列中最后一个元素的下一个位置，初始值为0

另外，在环形队列中，一些判断条件也会发生相应的改变

  • 队空的判断为：rear == front

    在初始状态下，由于front和rear初始值都未0，在进行入队操作时队列一定为空，所以此时断定rear == front时，环形队列为空

在这里插入图片描述

在其他状态下，在队即将空（队列中只有一个元素）的情况下，front指向的是队列中唯一一个元素（这个元素是队列中第一个也是最后一个元素），当出队后，front会后移一位，而rear指向的恰好是队列中最后一个元素的下一个位置，所以在这种情况下，也可以使用rear == front来判断队列是否为空

在这里插入图片描述

  • 队满的判断为：(rear + 1) % maxSize == front

    这里的判断有两个点需要注意

    1. 为什么需要对maxSize取余

      在环形队列中，无论是front还是rear，当他们指向队列中maxSize - 1的位置时，都会面临下一位的指向问题

      以maxSize为4的队列为例，队列中的空间依次为 queue[0]、queue[1] 、queue[2] 、queue[3]

      当一个指针指向maxSize - 1，即指向queue[3]的时候，再进行指针后移的操作，数组下标就会越界(即移动到不存在的queue[4])

      因此，需要将数组下标控制在 0 ~ maxSize-1 这个范围中，而对maxSize取余正好可以实现这个要求

      即当一个指针指向queue[3]时，他指向的下一个位置应为 queue[3 + 1 % maxSize] => queue[4 % 4] => queue[0]

    2. rear指向的已经是队列中最后一个元素的下一个位置，为什么还需要+1

      如果使用 rear % maxSize == front 来判断队满的话，当队列将满（队列中空余一个位置）时，执行入队操作

在这里插入图片描述

由于通过 rear % maxSize == front 判断该队未满，所以元素可以成功加入到队列中，此时，front和rear指向了同一个位置，在这种情况下，front == rear判断队空已经不成立了，因为此时队列是满状态

所以在环形队列中，需要牺牲一个队列空间用来做判断

在这里插入图片描述

用数组实现环形队列
初始化队列
// 初始化队列参数
public CircleArray(int maxSize) {
    this.maxSize = maxSize;
    arr = new int[maxSize];
    front = 0;
    rear = 0;
}
判断队列是否已满

判断标准 (rear + 1) % maxSize == front

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

判断标准 rear == front

// 判断队列是否为空
public boolean isEmpty(){
    return rear == front;
}
显示队列元素个数

在环形队列中，无法使用简单的rear - front获取队列中的元素个数

在简单队列中，rear所指的数组下标永远大于front，但在环形队列中，会出现以下情况

在这里插入图片描述

此时，front指向数组下标为3的位置，rear指向数组下标为0的位置，如果使用rear - front来计算的话，得到的结果是 -3

就算是对负数结果取绝对值也救不回来这个错误的元素个数

对于这一点，我是这样理解的

  1. 第一种理解是，在环形队列中，front和rear一直在做顺时针运动，如果通过数组下标来看的话，front和rear谁前谁后的概念会变得很模糊，忽略数组下标去分析，front是永远无法跑到rear之前的，因为front移动的前提是出队，在front和rear指向同一位置时已经代表队列为空，无法进行出队操作，所以从这点分析，rear永远跑在front之前

    通过这一点考虑，如果出现rear数组下标小于front的情况的话，一定是rear比front先跑完了一圈

    在这个基础上进一步分析的话，不难得出一个结论 rear + maxSize - front应该可以得出环形队列中的元素个数

在这里插入图片描述

用上面的例子测试一下 元素个数 = rear + maxSize - front = 0 + 4 - 3 = 1

看起来好像得出了正确答案，但是这种情况只是rear所指下标小于front的情况，如果rear大于front的话

在这里插入图片描述

元素个数 = rear + maxSize - front = 3 + 4 - 1 = 6

这肯定是有毛病的

在队列中，元素数组的个数肯定不可能超过队列的最大值，而且我们已经空余了一位用来判断队满，所以元素个数应该在 0 ~ maxSize - 1之间，恰好，在考虑指针后移的情况中，也出现了这个范围，当时使用了对maxSize取模来解决，这里同样也可以使用这种方法

最后结论：元素个数 = (rear + maxSize - front) % maxSize

例：

(0 + 4 - 3) % 4 = 1 % 4 = 1 正确

(3 + 4 - 1) % 4 = 6 % 4 = 2 正确

  1. 第二种理解是，当rear所指的数组下标小于front时，进行rear - front得到的结果肯定是负值，而通过观察，我们可以发现这个负值有一些存在的意义

在这里插入图片描述

通过观察可以发现，这些负值好像刚好是队列中空缺的位置个数，那如果我们用最大容量减去空缺的数量呢

maxSize - ( - (rear - front)) = 4 - ( - (0 - 2)) = 4 - 2 = 2

maxSize - ( - (rear - front)) = 4 - ( - (0 - 1)) = 4 - 1 = 3

maxSize - ( - (rear - front)) = 4 - ( - (2 - 3)) = 4 - 1 = 3

这样就可以得到了正确的元素个数，那么如果对这个式子优化一下，不难得出 元素个数 = maxSize + rear - front这个结论

同样的，为了兼顾rear所指下标大于front下标的情况，我们还是需要对这个结果进行取模

最终结论 元素个数 = (maxSize + rear - front) % maxSize

// 显示当前队列元素个数
public int getNumOfQueue(){
    return (rear + maxSize - front) % maxSize;
}
显示队列
// 显示队列
public void showQueue(){
    // 判断队列是否为空
    if (isEmpty()){
        throw new RuntimeException("队空，无法取得数据");
    }
    for (int i = front; i < front + getNumOfQueue(); i++) {
        System.out.println("arr[" + i % maxSize + "]=" + arr[i % maxSize]);
    }
}

在显示队列时，不能使用 front ~ rear这个范围来遍历，因为rear所指的下标有可能会小于front

假设front指向1，队列中有3个元素，则遍历范围应该为 1 ~ 3

这个范围可以是[1,3]即[front,front + 元素个数 - 1]，也可以是[1,4)，即[front,front + 元素个数)

入队
// 添加数据到队列，入队
public void addQueue(int n){
    // 判断队列是否满
    if (isFull()){
        throw new RuntimeException("队满，无法加入");
    }
    // 加入数据
    arr[rear] = n;
    // 将rear后移，需要考虑取模
    rear = (rear + 1) % maxSize;
}

入队前需要先判断队列是否已满

在加入数据后需要考虑rear后移时的取模问题，如果不进行取模，可能会出现数组下标越界的情况

arr[maxSize - 1 + 1] => arr[maxSize] 越界

获取元素（出队）
// 从队列中取出数据，出队
public int getQueue(){
    // 判断队列是否为空
    if (isEmpty()){
        throw new RuntimeException("队空，无法取得数据");
    }
    // 暂存front对应的值
    int temp = arr[front];
    // 将front后移
    front = (front + 1) % maxSize;
    // 将之前暂存的数据返回
    return temp;
}

出队之前需要判断队列是否为空

在这里，由于front的指向已经变为指向队列中第一个元素，所以如果返回arr[front]的话，就无法对front后移，这里需要暂存一下arr[front]中的值

在对front进行后移时，也需要考虑它的取模问题

获取队头但不出队
// 显示队头数据
public int peekQueueHead(){
    if (queueIsEmpty()){
        throw new RuntimeException("队空，没有队头数据");
    }
    return arr[front+1];
}
完整代码
package dataStructures;

import java.util.Scanner;
/**
 * 用数组实现环形队列
 * @author Melonico 
 */
public class CircleArrayQueue {
    public static void main(String[] args) {
        CircleArray circleArray = new CircleArray(5);
        Scanner sc = new Scanner(System.in);
        char key = ' '; // 接收用户输入
        boolean flag = true;
        // 显示菜单
        while (flag){
            System.out.println("s:显示队列");
            System.out.println("a:添加数据");
            System.out.println("g:获取数据");
            System.out.println("h:显示队头");
            System.out.println("e:退出程序");
            key = sc.next().charAt(0);
            switch (key){
                case 's' :
                    try {
                        circleArray.showQueue();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a' :
                    try {
                        System.out.println("输入一个数");
                        int num = sc.nextInt();
                        circleArray.addQueue(num);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g' :
                    try {
                        System.out.println("取出的数据是：" + circleArray.getQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h' :
                    try {
                        System.out.println("队头数据是：" + circleArray.getQueueHead());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e' :
                    sc.close();
                    flag = false;
                default : break;
            }
        }
    }
}

class CircleArray {
    private int maxSize; // 表示队列的最大容量
    private int front; // 指向队头,队列中的第一个元素
    private int rear; // 指向队尾,队列中最后一个元素的下一个位置
    private int[] arr; // 模拟队列，存放数据

    public CircleArray() {
    }

    // 初始化队列参数
    public CircleArray(int maxSize) {
        this.maxSize = maxSize;
        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 n){
        // 判断队列是否满
        if (isFull()){
            throw new RuntimeException("队满，无法加入");
        }
        // 加入数据
        arr[rear] = n;
        // 将rear后移，需要考虑取模
        rear = (rear + 1) % maxSize;
    }

    // 从队列中取出数据，出队
    public int getQueue(){
        // 判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException("队空，无法取得数据");
        }
        // 暂存front对应的值
        int temp = arr[front];
        // 将front后移
        front = (front + 1) % maxSize;
        // 将之前暂存的数据返回
        return temp;
    }

    // 显示队列
    public void showQueue(){
        // 判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException("队空，无法取得数据");
        }
        for (int i = front; i < front + getNumOfQueue(); i++) {
            System.out.println("arr[" + i % maxSize + "]=" + arr[i % maxSize]);
        }
    }

    // 显示当前队列元素个数
    public int getNumOfQueue(){
        return (rear + maxSize - front) % maxSize;
    }

    // 获取队列头元素，但不出队
    public int getQueueHead(){
        if (isEmpty()){
            throw new RuntimeException("队列为空，无法获取第一个元素");
        }
        return arr[front];
    }

}
数据结构
Java
赞
  • 作者：Melonico
  • 发表时间：2021-03-15 18:00
  • 更新时间：2021-03-15 18:00

评论

暂无评论，快来发表第一个评论吧!
留言
TOP