JAVA数据结构（三）数组环形队列

数组环形队列

前提： 一般的数组队列使用一次就不能再使用，没有达到复用的效果。

所以为了充分利用数组，优化数组队列，将数组看做是一个环形。（通过取模的方式来实现）

思路分析：

设front初始值为0，rear初始值为0，

1.front变量含义：front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素。

2.rear变量含义：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定。示意图如下：

3.当队列满时，条件为**(rear+1)%maxSize == front**；

4.但队列空时，条件为rear==front

5.队列中有效的数据的个数:(rear+maxsize-front)%maxSize

代码演示

class CircleArray{
    private int maxSize;//数组最大容量 但实际数组容量为maxSize-1
    private  int front;//队列头
    private  int rear;//队列尾
    private int[] arr;//存放数据，模拟队列

    /**
     * 构造创建数组队列
     * @param arrMaxSize 数组最大容量
     */
    public CircleArray(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0;//指向队列头部
        rear = 0;//指向队列尾部
    }
    /**
     * 判断数组队列是否为满
     * @return
     */
    public  boolean isFull(){
        return  (rear+1) % maxSize == front;
    }

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

    /**
     * 存入数据
     * @param n
     */
    public  void  addQueue(int n){
        if (isFull()){
            System.out.println("队列满");
            return;
        }
        arr[rear] = n;
        rear = (rear+1)%maxSize;
        System.out.println( "front:"+front);
        System.out.println( "rear:"+rear);
    }
    /**
     * 取出头数据
     * @return
     */
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;

    }
    /**
     * 有效数据的个数
     * @return
     */
    public int size(){
        return (rear + maxSize - front)% maxSize;
    }
    
    /**
     * 遍历输出数组队列
     */
    public void print(){
        if (isEmpty()){
            return;
        }
        for (int i = front; i<front+size();i++){
            System.out.println("arr["+i%maxSize+"}"+":"+arr[i%maxSize]);
        }
    }
    /**
     * 显示队列的头数据，注意不是取数据
     * @return
     */
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return arr[front];
    }
}
           

测试：

public class CircleArrayQueue {
    public static void main(String[] args) {
        CircleArray arrayQueue = new CircleArray(6);
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        while (flag){
            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':
                    arrayQueue.print();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    int res = arrayQueue.getQueue();
                    System.out.println("取出数据" + res);
                    break;
                case 'h':
                    int a = arrayQueue.headQueue();
                    System.out.println("队列头数据" + a);
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
    }
}