[数据结构与算法]【数据结构】 环形队列（Java代码实现—带注释详解）

前言

随风潜入夜，润物细无声。—《春夜喜雨》
（每天一道数据结构，Day 1）

关于队列

队列是有序列表，可以用数组或链表来实现。
队列的特点：先入先出。今天我们采用数组实现队列。
比较关键的是要弄明白rear、front、maxSize之间的关系，最好自己先推一遍，这样理解地更加深刻。
图解如下：

必须理解的地方

• front、rear、maxSize
  使 front=0；rear=0；
  实际队列比maxSize小1。 空出一个空间做约定。
  出队列：front（队头）增加。
  入队列：rear（队尾）增加。
  a[ ] ：用来存放数据。
  front指向队列的第一个元素，rear指向队列的最后一个元素的后一个位置。
  ——————————————————————————————————
  当队列满时：(rear+1)%maxSize==front
  当队列为空：rear==front
  有效数据个数：(rear+maxSize-front)%maxSize
  遍历数据：

  for (int i = front;  i< front + size(); i++) {
            System.out.printf("a[%d]=%d\n", i%maxSize, a[i%maxSize]);
        }
    }

• CircleQueue方法
  isFull：判断队列是否已满。（注意计算方法）
  isEmpty：判断队列是否为空。
  size：返回有效的数据的个数。
  addDate：增加数据。
  getDate：取出数据。
  showHead：显示头部数据。
  listDate：显示所有数据。

Java代码实现

import java.util.Scanner;
/**
 * @Author 不知名网友鑫
 * @Date 2022/2/5
 **/
public class CircleArrayQueue {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Queue q = new Queue(4);  //预留了一个空间，4，实际空间是3。
        Boolean loop = true;
        while (loop) {
            System.out.println("a(增加数据)");
            System.out.println("g(取出数据)");
            System.out.println("s(显示数据)");
            System.out.println("h(显示头部数据)");
            System.out.println("e(退出程序)");
            char key = in.next().charAt(0);
            switch (key) {
                case 'a':
                    System.out.println("请输入数据：");
                    try {
                        q.addDate(in.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try {
                        System.out.println(q.getDate());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    try {
                        q.listDate();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        q.showHead();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    loop = false;
                    break;
            }

        }
        System.out.println("程序结束_by—Sivan_Xin");
    }
}
class Queue{
    private int maxSize;   //队列的最大值
    private int front=0;  //头部  注意：指向第一个数据。
    private int rear=0;  //尾部  注意：要指向最后一个数据的后一位。预留出一个空位。
    private int []a;    //用数组模拟队列
    //初始化构造器
    public Queue(int maxSize){
        this.maxSize=maxSize;
        a=new int [maxSize];
    }
    //判断队列是否为满
    public boolean isFull() {
        return (rear+1)%maxSize==front;   //注意这里的取模运算。
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return front==rear;
    }
    //向队列中添加数据，注意，尾部增加并且取模（环形）
    public void addDate(int date){
        if(isFull()){
            throw new RuntimeException("队列满，不能存入数据");
        }
        a[rear]=date;
        rear=(rear+1)%maxSize;
    }
    //从队列中取出数据，注意，头部增加并且取模（环形）
    public int getDate(){
        if(isEmpty()){   //空队列不能取数据，抛异常。
            throw new RuntimeException("队列为空，不能取数据");
        }
        int value=a[front];
        front=(front+1)%maxSize;  //将front控制在[0，4)之间
        return value;
    }
    //显示头部数据
    public void showHead(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，无头部数据");
        }
        System.out.println("头部数据为:"+a[front]);
    }
    //显示队列所有数据
    public void listDate() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有数据");
        }
        //思路：从front开始遍历，遍历一共加了多少元素即可。
        for (int i = front;  i< front + size(); i++) {
            System.out.printf("a[%d]=%d\n", i%maxSize, a[i%maxSize]);
        }
    }
    //显示现有元素个数
    public int size(){
            return (rear+maxSize-front)%maxSize;  //实际就是rear-front，尾减头。
        //尾大于头时，不需要加maxSize，加上maxSize实际就是绝对值的作用，如果尾小于头时，有用。
        }
}

最后，如果觉得写的还不错的话，欢迎关注哦！