【数据结构】Java数组模拟队列

Alan 523 2022-09-01
数组模拟队列

队列数据结构的特点是先进先出,后进后出。

使用数组和链表可以模拟队列的实现。

这里用Java的数组来实现一个队列。

  1. 创建Java类,包含成员变量maxSize来表示队列的最大容量。front表示队列前端的索引下标,rear表示队列后端的索引下标。

arr数组表示队列存储的内容。

/**
 * 队列最大长度
 */
private int maxSize;
/**
 * 队列头
 */
private int front;
/**
 * 队列尾
 */
private int rear;
/**
 * 数组
 */
private int[] arr;
  1. 构造函数初始化队列。初始化时front值为-1,rear值为-1。
/**
 * 构造函数
 */
public ArrayQueue(int arrMaxSize) {
    this.maxSize = arrMaxSize;
    int[] arr = new int[maxSize];
    front = -1;
    rear = -1;
}
  1. 编写方法,判断队列是否为满,当 rear = maxSize - 1 时满。
/**
 * 判断队列是否满,rear 等于 maxsize - 1时满
 */
public Boolean isFull() {
    return rear == maxSize - 1;
}
  1. 编写方法,判断队列是否为空,当 rear = front 时为空。
/**
 * 判断队列是否为空,rear 等于 front时为空
 */
public Boolean isEmpty() {
    return rear == front;
}
  1. 编写方法,将数据添加到队列,添加数据的时候,队列头是不会动的,而队尾rear的位置往后移动一位。
/**
 * 将数据添加到队列
 */
public void add(int num) {
    //判断队列是否为满,为满给出提示
    if (isFull()) {
        System.out.println("队列满,不能加入到队列");
    }
    //将队尾++
    rear++;
    arr[rear] = num;
}
  1. 编写方法,从队列中取数据。取数据的时候从队列头取,所以要将队头front的位置往后移动一位。
/**
 * 从队列中取数据
 */
public int get() {
    //判断队列是否为空,为空抛出异常
    if (isEmpty()) {
        throw new RuntimeException("队列为空,无数据可取");
    }
    front++;
    return arr[front];
}
  1. 编写方法,遍历数组。
/**
 * 遍历数组
 */
public void showQueue() {
    //遍历
    if (isEmpty()) {
        System.out.println("队列空的,没有数据。。。。");
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.printf("arr[%d] = %d\n", i, arr[i]);
    }
}
  1. 编写方法,显示队列头的信息。队列头front由于指向的是队列的前一个位置的信息,所以front应该+1
/**
 * 显示队列头的信息
 */
public int showHead() {
    //判断是否为空
    if (isEmpty()) {
        System.out.println("队列为空,无数据");
    }
    return arr[front + 1];
}
  1. 编写测试方法,来模拟队列的添加和取出数据的过程。
public static void main(String[] args) {
    //创建一个容量为3的数组
    ArrayQueue queue = new ArrayQueue(3);
    //接受用户输入
    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.showQueue();
                break;
            case 'e':
                System.out.println("程序退出~");
                loop = false;
                scanner.close();
                break;
            case 'a':
                try {
                    System.out.println("请输入要添加的数字:");
                    int num = scanner.nextInt();
                    queue.add(num);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'g':
                try {
                    int i = queue.get();
                    System.out.printf("从队列取出的数据是:%d", i);
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'h':
                try {
                    int head = queue.showHead();
                    System.out.printf("队列头数据是:%d", head);
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
        }
    }
}

刚开始输入s显示队列,会显示队列为空。

然后添加三个数字10,20,30到队列。

显示队列中的内容:

输入g,从队列中取出数据,会从头开始取,第一次会取出10,然后输入h查看队列头的数据,会显示为20:

依次取出20和30,最后会显示队列为空,无数据:

这个时候,由于队列加入了3个数据,rear的值已经由-1变成了2,再回顾下队列是否满的判断,rear的值为maxsize-1的时候队列满。所以这个队列已经无法再添加任何数据了。

数组模拟环形队列

这个时候可以改造下代码来实现环形队列。

这里修改下rear和front的定义,rear表示的是队尾的后面一个位置,初始值为0,表示占据一个未使用的位置,front表示的是对头的位置,初始值也为0。

这里通过推断得出:队列满的判断应该是 (rear + 1) % maxSize = front; 而队列的个数应该是 (rear + maxSize - front)% maxSize。

  1. 改造下构造方法,这里由于int初始值默认为0,所以省略掉了 int rear = 0 ; int front = 0 ;
public CircleArrayQueue(int arrMaxSize) {
    maxSize = arrMaxSize;
    arr = new int[maxSize];
}
  1. 改造数组是否为满方法,当 (rear + 1)% maxSize == front 时为满。
/**
 * 判断队列是否满, (rear + 1) % maxSize == front 时满
 */
public Boolean isFull() {
    return (rear + 1) % maxSize == front;
}
  1. 改造添加数据到队列方法。将队列rear位置的值赋值为num,由于rear值有可能会重新回到起始位置,所以需要将值+1,然后对maxSize取模。
/**
 * 将数据添加到队列
 */
public void add(int num) {
    //判断队列是否为满,为满给出提示
    if (isFull()) {
        System.out.println("队列满,不能加入到队列。。");
        return;
    }
    //将队尾++
    arr[rear] = num;
    rear = (rear + 1) % maxSize;
}
  1. 改造从队列取出数据的方法, 记录队列front位置的值,然后将(front+1)%maxSize,这么做和rear同理,为了达到位置循环使用的目的。然后将记录的值返回。
/**
 * 将数据添加到队列
 */
public void add(int num) {
    //判断队列是否为满,为满给出提示
    if (isFull()) {
        System.out.println("队列满,不能加入到队列。。");
        return;
    }
    //将队尾++
    arr[rear] = num;
    rear = (rear + 1) % maxSize;
}
  1. 改造遍历数组的方法,循环是从front开始,循环的次数是队列的有效个数次。所以首先创建获取队列个数的方法。
/**
 * 获取数组中有效元素的个数
 *
 * @return
 */
private int size() {
    return (rear + maxSize - front) % maxSize;
}
  1. 遍历数组。为了保证不会发生索引越界,(i的值有可能大于数组的个数),所以要对数组取模。
/**
 * 遍历数组
 */
public void showQueue() {
    //遍历
    if (isEmpty()) {
        System.out.println("队列空的,没有数据。。。。");
        return;
    }
    for (int i = front; i < front + size(); i++) {
        System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]);
    }
}
  1. 编写测试方法开始测试。
public static void main(String[] args) {
    //创建一个容量为3的数组
    CircleArrayQueue queue = new CircleArrayQueue(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.showQueue();
                break;
            case 'e':
                System.out.println("程序退出~");
                loop = false;
                scanner.close();
                break;
            case 'a':
                try {
                    System.out.println("请输入要添加的数字:");
                    int num = scanner.nextInt();
                    queue.add(num);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'g':
                try {
                    int i = queue.get();
                    System.out.printf("从队列取出的数据是:%d", i);
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'h':
                try {
                    int head = queue.showHead();
                    System.out.printf("队列头数据是:%d", head);
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            default:
                break;
        }
    }
}

首先向队列添加10,20,30三个数字。

然后再从队列取三次数据。

这个时候,再从数据添加数据,就可以添加了。

这样就实现了一个环形的队列。


# 数据结构 # 队列