队列

队列：

  1）队列是一个有序列表
  2）队列遵循先入后出原则

使用数组实现队列

// ArrayQueue类
/**
 * @author Little Boy
 * @title Queue
 * @projectName 数据结构与算法
 * @description 数组模拟队列
 * @date 2021/8/18 16:17
 */
public class ArrayQueue {

    // 数组的最大容量
    private int maxSize;

    // 队列的起始位置
    private int front;

    // 队列的尾部
    private int rear;

    // 存储数据
    private int[] arrays;

    /**
      * @auther Little Boy
      * @title
      * @description 初始化队列
      * @params
      * @date 2021/8/18 16:23
      */
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arrays = new int[maxSize];
        front = -1;
        rear = -1;
    }

    /**
      * @auther Little Boy
      * @title isFull
      * @description 判断队列是否满
      * @params []
      * @date 2021/8/18 16:30
      */
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    /**
      * @auther Little Boy
      * @title isEmpty
      * @description 判断队列是否为空
      * @params []
      * @date 2021/8/18 16:31
      */
    public boolean isEmpty(){
        return  rear == front;
    }

    /**
      * @auther Little Boy
      * @title addQueue
      * @description 添加数据
      * @params [num]
      * @date 2021/8/18 16:36
      */
    public void addQueue(int num){
        // 判断队列是否满了
        if(isFull()){
            System.out.println("当前队列已满");
            return;
        }
        // 让rear后移
        arrays[++rear] = num;
    }

    /**
      * @auther Little Boy
      * @title getQueue
      * @description 取出数据
      * @params []
      * @date 2021/8/18 16:38
      */
    public int getQueue(){
        // 判断是否为空
        if(isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        return arrays[++front];
    }

    /**
      * @auther Little Boy
      * @title showQueue
      * @description 显示所有队列数据
      * @params []
      * @date 2021/8/18 16:40
      */
    public void showQueue(){
        // 遍历数组
        if(isEmpty()){
            System.out.println("当前队列为空");
            return;
        }
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "\t");
        }
    }

    /**
      * @auther Little Boy
      * @title headQueue
      * @description 获取头部数据
      * @params []
      * @date 2021/8/18 16:42
      */
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        return arrays[front + 1];
    }

}

// 测试类
/**
 * @author Little Boy
 * @title ArrayQueueDemo
 * @projectName 数据结构与算法
 * @description 数组模拟队列
 * @date 2021/8/18 16:19
 */
public class ArrayQueueDemo {

    /**
      * @auther Little Boy
      * @title main
      * @description 测试队列
      * @params [args]
      * @date 2021/8/18 16:51
      */
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(5);
        // 添加数据
        System.out.println("-----添加数据-----");
        arrayQueue.addQueue(123);
        arrayQueue.addQueue(178);
        arrayQueue.addQueue(789);
        arrayQueue.addQueue(1589);
        arrayQueue.addQueue(4563);
        System.out.println();

        // 当队列满了后添加数据
        System.out.println("-----队列满了后添加数据-----");
        arrayQueue.addQueue(5555);
        System.out.println();

        // 显示队列
        System.out.println("-----显示队列-----");
        arrayQueue.showQueue();
        System.out.println();
        System.out.println();

        // 从队列中取数据
        System.out.println("-----从队列中取出数据-----");
        System.out.println(arrayQueue.getQueue());
        System.out.println();

        // 查看头部数据
        System.out.println("查看头部数据");
        System.out.println(arrayQueue.headQueue());
        System.out.println();

        // 添加数据
        System.out.println("添加数据");
        arrayQueue.addQueue(123);
    }

}

输出

-----添加数据-----

-----队列满了后添加数据-----
当前队列已满

-----显示队列-----
123	178	789	1589	4563	

-----从队列中取出数据-----
123

查看头部数据
178

添加数据
当前队列已满

存在的问题：队列是一次性的，当从队列中取出数据后，当队列满了以后即使拿出来数据，也不能往进存储数据

改进1：环形队列

环形队列：

  1.头部变量指向队列的第一个元素，初始值为0
  2.末尾变量指向队列的最后一个元素的后一个位置，初始值为0
  3.当队列满时条件是：(末尾变量 + 1) % 队列的大小 == 头部变量
  4.队列为空的条件，头部变量 == 末尾变量
  5.队列中的有效数据的个数：(末尾变量 + 队列大小 - 头部变量) % 队列大小

代码实现：

// ArrayRingQueue 
/**
 * @author Little Boy
 * @title ArrayRingQueue
 * @projectName 数据结构与算法
 * @description 环形队列
 * @date 2021/8/19 10:03
 */
public class ArrayRingQueue {

    // 队列的最大存储值
    private int maxSize;

    // 队列的起始位置
    private int front;

    // 队列的末尾位置
    private int rear;

    // 存储队列的数组、
    private int[] arrays;

    /**
      * @auther Little Boy
      * @title ArrayRingQueue
      * @description 初始化队列
      * @params [maxSize]
      * @date 2021/8/19 10:07
      */
    public ArrayRingQueue(int maxSize){
        this.maxSize = maxSize;
        arrays = new int[maxSize];
    }

    /**
      * @auther Little Boy
      * @title isFull
      * @description 判断是否已满
      * @params []
      * @date 2021/8/19 10:08
      */
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    /**
      * @auther Little Boy
      * @title isEmpty
      * @description 判断是否为空
      * @params []
      * @date 2021/8/19 10:09
      */
    public boolean isEmpty(){
        return front == rear;
    }

    /**
      * @auther Little Boy
      * @title addQueue
      * @description 添加数据
      * @params [num]
      * @date 2021/8/19 10:12
      */
    public void addQueue(int num){
        // 判断是否满
        if(isFull()){
            System.out.println("当前队列已满");
        }
        arrays[rear] = num;
        // 指针后移
        rear = (rear + 1) % maxSize;
    }

    /**
      * @auther Little Boy
      * @title
      * @description 取出数据
      * @params
      * @date 2021/8/19 10:13
      */
    public int getQueue(){
        // 判断是否为空
        if(isEmpty()){
            throw new RuntimeException("当前队列为空");
        }

        int result = arrays[front];
        // 指针后移
        front = (front + 1) % maxSize;
        return result;
    }

    /**
      * @auther Little Boy
      * @title
      * @description 输出所有的数据
      * @params
      * @date 2021/8/19 10:16
      */
    public void showQueue(){
        // 判断当前队列是否为空
        if(isEmpty()){
            System.out.println("当前吗队列为空");
        }
        // 输出数据
        for (int i = front; i < front + getNum(); i++) {
            System.out.println(arrays[i % maxSize] + "\t");
        }
    }

    /**
      * @auther Little Boy
      * @title getNum
      * @description 当前队列的有效个数
      * @params []
      * @date 2021/8/19 11:13
      */
    public int getNum(){
        return (rear + maxSize - front) % maxSize;
    }

    /**
      * @auther Little Boy
      * @title headQueue
      * @description 获得头部数据
      * @params []
      * @date 2021/8/19 10:18
      */
    public int headQueue(){
        // 判断是否为空
        if(isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        return arrays[front];
    }

}

// ArrayRingQueueDemo 
/**
 * @author Little Boy
 * @title ArrayRingQueueDemo
 * @projectName 数据结构与算法
 * @description 测试环形队列
 * @date 2021/8/19 10:19
 */
public class ArrayRingQueueDemo {

    /**
      * @auther Little Boy
      * @title main
      * @description 测试环形队列
      * @params [args]
      * @date 2021/8/19 10:20
      */
    public static void main(String[] args) {
        ArrayRingQueue arrayRingQueue = new ArrayRingQueue(5);
        // 添加数据
        System.out.println("==========添加数据==========");
        arrayRingQueue.addQueue(123);
        arrayRingQueue.addQueue(148);
        arrayRingQueue.addQueue(753);
        arrayRingQueue.addQueue(789);
        System.out.println();

        // 取出数据
        System.out.println("==========取出数据==========");
        System.out.println(arrayRingQueue.getQueue());
        System.out.println();

        // 显示所有的数据
        System.out.println("==========显示所有的数据==========");
        arrayRingQueue.showQueue();
        System.out.println();

        // 读取头数据
        System.out.println("==========显示第一个数据==========");
        System.out.println(arrayRingQueue.headQueue());
        System.out.println();

        // 添加数据
        System.out.println("==========添加数据==========");
        arrayRingQueue.addQueue(123456);
        System.out.println();

        // 显示所有的数据
        System.out.println("==========显示所有的数据==========");
        arrayRingQueue.showQueue();
        System.out.println();
    }

}

输出：

==========添加数据==========

==========取出数据==========
123

==========显示所有的数据==========
148	
753	
789	

==========显示第一个数据==========
148

==========添加数据==========

==========显示所有的数据==========
148	
753	
789	
123456