二、队列，

二、队列，

队列

队列介绍

数组模拟队列

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量
• 因为队列的输入、输出是分别从前后端来处理，因此需要两个变量front及rear分别队列前后端的下标，front会随着数据的取出而改变，而rear则是随着数据的移入而改变

代码：

public class ArrayQueue{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;//用于存放数据

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }

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

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

    /**
     * 添加数据
     */
    public void add(int n){
        if (isFull()){
            System.out.println("队列已满！");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    /**
     * 获取数据
     */
    public int get(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        front++;
        return arr[front];
    }

    /**
     * 显示所有数据
     */
    public void show(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        for (int i=front+1;i<=rear;i++){
            System.out.print(arr[i]+" ");
        }
    }

    /**
     * 显示头数据
     */
    public int getHead(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        return arr[front+1];
    }
}

数组模拟环形队列

思路：

public class CircleArray{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;//用于存放数据

    public CircleArray(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

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

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

    /**
     * 添加数据
     */
    public void add(int n){
        if (isFull()){
            System.out.println("队列已满！");
            return;
        }
        arr[rear] = n;
        rear = (rear+1)%maxSize;
    }

    /**
     * 获取数据
     */
    public int get(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;
    }

    /**
     * 显示所有数据
     */
    public void show(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        for (int i=front;i<front+size();i++){
            System.out.print(arr[i%maxSize]+" ");
        }
    }

    /**
     *  队列的大小
     */
    public int size(){
        return (rear-front+maxSize)%maxSize;
    }

    /**
     * 显示头数据
     */
    public int getHead(){
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        return arr[front];
    }
}