带你走进Java数据结构与算法（三）

开启掘金成长之旅！这是我参与「掘金日新方案 12 月更文应战」的第十四天，点击检查活动详情

前言：上文学习了稀疏数组，本文带领我们走进行列~

行列

• ==有序列表==，用数组或链表来完成
• ==先进先出== ：存入行列的数据，要先取出

• front 随着数据出队而改变
• rear 随着数据入队而改变

行列操作

0. 队空条件：front == rear == null，rear + 1
1. 队满条件：rear = maxSize – 1，则持续入队，否则队满：rear = maxSize – 1

import java.util.Scanner;
​
/**
 * @author Kcs 2022/8/7
 */
public class ArrayQueueDemo1 {
  public static void main(String[] args) {
    //创立一个行列目标
    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 'a':
          System.out.println("输入数字：");
          int value = scanner.nextInt();
          queue.addQueue(value);
          break;
​
        case 'g':
          try {
            int res = queue.getQueue();
            System.out.println("取出的数据是：" + res);
           } catch (Exception e) {
            System.out.println(e.getMessage());
           }
          break;
​
        //检查行列头数据
        case 'h':
​
          try {
            int res = queue.headQueue();
            System.out.println("行列头的数据：" + res);
           } catch (Exception e) {
            System.out.println(e.getMessage());
           }
          break;
        //程序退出
        case 'e':
          scanner.close();
          loop = false;
          break;
​
        default:
          break;
       }
     }
    System.out.println("程序退出");
   }
}
//使用数据模仿行列编写一个ArrayQueue类
​
class ArrayQueue {
​
  /**
   * 表示数组的最大容量
   */
  private int maxSize;
  /**
   * 行列头
   */
  private int front;
  /**
   * 行列尾
   */
  private int rear;
  /**
   * 寄存数据数组
   */
  private int[] array;
​
  /**
   * 构造器
   */
  public ArrayQueue(int arrMaxSize) {
    maxSize = arrMaxSize;
    array = new int[maxSize];
    //指向行列头部，行列头的前一个位置
    front = -1;
    //指向行列尾部，行列尾的数据（行列的最终一个数据）
    rear = -1;
   }
​
  /**
   * 判别行列是否满
   */
  public boolean isFull() {
    return rear == maxSize - 1;
   }
​
  /**
   * 判别行列是否为空
   */
  public boolean isEmpty() {
    return rear == front;
   }
​
  /**
   * 入队操作
   */
  public void addQueue(int n) {
    //判别是否队满
    if (isFull()) {
      System.out.println("队满，不可以增加数据");
      return;
     }
    // rear后移
    rear++;
    array[rear] = n;
   }
​
  /**
   * 出队操作
   */
  public int getQueue() {
    //判别是否为空
    if (isEmpty()) {
      throw new RuntimeException("行列为空，没有数据可取");
     }
    // front后移
    front++;
    return array[front];
   }
​
  /**
   * 显现行列数据
   */
  public void showQueue() {
    // 遍历行列
    if (isEmpty()) {
      System.out.println("行列为空，没有数据！！");
      return;
     }
    for (int i = 0; i < array.length; i++) {
      System.out.printf("array[%d] = %d\n", i, array[i]);
     }
​
   }
​
  /**
   * 显现行列头部数据,不是取数据
   */
  public int headQueue() {
    if (isEmpty()) {
      throw new RuntimeException("行列为空，没有数据~~");
     }
    return array[front + 1];
   }
​
}

此时把内容取出完，但也不能增参加数据，还在占用空间

环形行列

剖析

0. front 变量的意义做一个调整：front 指向行列的第一个元素，array[front] ，front 的初始值 = 0
1. rear 变量的意义做一个调整：rear 指向行列的最终一个元素的后一个位置，空出一个空间作为约好，rear 初始值 = 0
2. 行列==满==条件：(rear + 1) % maxSize = front
3. 行列为==空==的条件：rear = front
4. 行列中有用数据的个数：( rear +maxSize – front ) % maxSize // rear =1 , front = 0

import java.util.Scanner;
​
/**
 * @author Kcs 2022/8/7
 */
public class CircleArrayQueueDemo {
  public static void main(String[] args) {
    //创立一个环形行列目标
    // 行列有用数据最多只要3个
    CircleQueue queue = new CircleQueue(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 'a':
          System.out.println("输入数字：");
          int value = scanner.nextInt();
          queue.addQueue(value);
          break;
​
        case 'g':
          try {
            int res = queue.getQueue();
            System.out.println("取出的数据是：" + res);
           } catch (Exception e) {
            System.out.println(e.getMessage());
           }
          break;
​
        //检查行列头数据
        case 'h':
​
          try {
            int res = queue.headQueue();
            System.out.println("行列头的数据：" + res);
           } catch (Exception e) {
            System.out.println(e.getMessage());
           }
          break;
        //程序退出
        case 'e':
          scanner.close();
          loop = false;
          break;
​
        default:
          break;
       }
     }
    System.out.println("程序退出");
   }
}
//使用数据模仿行列编写一个ArrayQueue类
​
class CircleQueue {
​
  /**
   * 表示数组的最大容量
   */
  private int maxSize;
  /**
   * front 指向行列的第一个元素，array[front] ，front 的初始值 = 0
   */
  private int front;
  /**
   * 1. rear 指向行列的最终一个元素的后一个位置，空出一个空间作为约好，rear 初始值 = 0
   */
  private int rear;
  /**
   * 寄存数据数组
   */
  private int[] array;
​
  /**
   * 构造器
   */
  public CircleQueue(int arrMaxSize) {
    maxSize = arrMaxSize;
    array = new int[maxSize];
   }
​
  /**
   * 判别行列是否满 (rear + 1) % maxSize == front
   */
  public boolean isFull() {
    return (rear + 1) % maxSize == front;
   }
​
  /**
   * 判别行列是否为空 rear =  front
   */
  public boolean isEmpty() {
    return rear == front;
   }
​
  /**
   * 入队操作,增加数据
   */
  public void addQueue(int n) {
    //判别是否队满
    if (isFull()) {
      System.out.println("队满，不可以增加数据");
      return;
     }
    // 直接将数据参加
    array[rear] = n;
    //将rear后移，取模，判别队满,避免地址溢出
    rear = (rear + 1) % maxSize;
   }
​
  /**
   * 出队操作，取数据
   */
  public int getQueue() {
    //判别是否为空
    if (isEmpty()) {
      throw new RuntimeException("行列为空，没有数据可取");
     }
    // front直接指向行列的第一个元素
    //1. front 对应的值保存到暂时变量
    int value = array[front];
    //2. front 后移,取模，避免地址溢出
    front = (front + 1) % maxSize;
    //3.将暂时保存的变量回来
    return value;
   }
​
  /**
   * 显现行列数据
   */
  public void showQueue() {
    // 遍历行列
    if (isEmpty()) {
      System.out.println("行列为空，没有数据！！");
      return;
     }
    //从front开始遍历，有用个数:( rear +maxSize - front ) % maxSize
    for (int i = front; i < front + effectiveValue(); i++) {
      System.out.printf("array[%d] = %d\n", i % maxSize, array[i % maxSize]);
     }
​
   }
​
  /**
   * 求出当前行列有用数据的个数
   */
  public int effectiveValue() {
    return (rear + maxSize - front) % maxSize;
   }
​
  /**
   * 显现行列头部数据,不是取数据
   */
  public int headQueue() {
    //判别为空
    if (isEmpty()) {
      throw new RuntimeException("行列为空，没有数据~~");
     }
    return array[front];
   }
​
}