环形队列

利用数组通过取模的方式实现环形队列，使队列达到复用的效果。

图一

图1中，rear和front分别代表队尾和队头并且初始化值都为0，此时都指队头，开始添加队列的操作，每次添加数据后，front不变，rear后移，rear的后移单位按照公式 (rear 1)%maxSize，maxSize表示队列的长度。

图二

图2中第一行，Queue中获取数据，出队列，rear和front分别代表队尾和队头并且初始化值都为0，此时都指队头，开始取出队列的操作，每次取出数据后，front后移，rear不变，front后移单位按照(front 1)%maxSize，maxSize表示队列的长度。当front和rear都指向2的时候代表队列空了，第二行中，在队列空了的情况下继续添加数据，会在队列下标为2和0的位置上添加， 当rear指向下标为1的位置时，队列再一次满了，从而实现了环形队列的效果，在编写代码的时候通过取模的方式即可实现以上效果。添加数据和移除数据时的rear和front都通过取模的方式计算出。

代码语言：javascript复制

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        CircleArray circleArray = new CircleArray(3);
        circleArray.addQueue(1);
        circleArray.addQueue(2);
        circleArray.showQueue();
        System.out.println("head "   circleArray.headQueue());
        System.out.println("size "   circleArray.size());
    }
}

class CircleArray{
    private int maxSize;
    private int front; // 指向队头，初始值是0
    private int rear; // 指向队尾，初始值是0，最大下标是maxSize - 1，所以rear 1 = maxSize
    private int[] arr;

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

    /**
     * 判断队列是否满了
     */
    public Boolean isFull(){
        return (rear   1) % maxSize == front; // front指向队头且初始值为0，当front指向队头且rear到最大下标 1与maxSize相等，此时取模是0，与front相等，表示队列满了
    }

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

    /**
     * 添加数据
     */
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列满，不能加入数据");
            return;
        }
        arr[rear] = n;
        rear = (rear   1) % maxSize;
    }

    /**
     * 获取队头的数据，出队列
     * @return
     */
    public int getQueue(){
        if (isEmpty()) {
            throw new RuntimeException("队列空，不能取数据");
        }
        int value = arr[front];
        front = (front   1) % maxSize;
        return value;
    }

    /**
     * 显示队列的所有数据
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列空了，没有数据");
            return;
        }

        for (int i = front;i<front size();i  ){
            System.out.printf("arr[%d]=%dn",i % maxSize,arr[i % maxSize]);
        }
    }

    /**
     * 当前有效数据的个数
     * @return
     */
    public int size(){
        return (rear   maxSize - front) % maxSize;
    }

    /**
     * 返回队头
     * @return
     */
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列空了，没有数据");
        }
        return arr[front];
    }
}

queue 队列

0 人点赞