队列进化->环形队列

前言

队列（Queue）是一个很常见的数据结构类型，今天学习了一个队列的升级版——环形队列，在这里总记录一下~(￣▽￣)~*。

性质

1、 约定front指向队列的第一个元素，也就是说data[front]就是队头数据，front初始值为0。
2、 约定rear指向队列的最后一个元素的后一个，也就是说data[rear-1]就是队尾数据，rear初始值为0。 如下图

##

1、 队列满的条件是：( rear+1 )% maxSize == front
2、 队列空的条件是：rear == front
3、 队列中的元素个数为：( rear + maxsize – front) % maxSize因为rear指向队尾的后面一个位置，这个位置就不能存数据，因此有效数据只有maxSize-1个

实现(java版)

class CircleArray {

    private int maxSize;//表示数组的最大容量
    private int front;//队列头:指向队列的第一个元素
    private int rear;//队列的最后一个元素的后一个位置
    private int[] arr;//用于存放数据，模拟对列

    public CircleArray(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }
    //判断队列是否满
    public boolean isFull(){
        return (rear+1) % maxSize == front;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if(isFull()){
            System.out.println("队列满，不能添加数据");
            return;
        }
        //直接将数据加入
        arr[rear] = n;
        //将rear后移，考虑取模
        rear = (rear +1 ) % maxSize;
    }

    //获取队列的数据，出队列
    public int getQueue(){
        //判断队列是否空
        if (isEmpty()){
            //通过抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        //front是指向队列的第一个元素.1.先把front对应的值保留到一个临时变量
        //2.将front后移,考虑取模
        //3.将临时保存的变量返回
       int value =  arr[front];
        front= (front+1)%maxSize;
        return value;
    }

    //显示队列的所有数据
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println("队列是空的，没有数据");
            return;
        }
        //思路：从front开始遍历，遍历多少个元素
        for (int i = front; i <front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize , arr[i % maxSize]);

        }
    }
    //求出当前数据有效数据的个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }
    //显示队列的头部，不是取出数据
    public int headQueue(){
        //判断
        if(isEmpty()){
            throw new RuntimeException("队列空，不能取数据");
        }
        return  arr[front];
    }

}

希望对你有帮助 （*＾-＾*）

文章永久链接：https://tech.souyunku.com/29478