数据结构——数组模拟循环队列

队列是一种带限制的线性表，与普通线性表相比，是一种插入和删除位置受限的线性表。队列限制只能在线性表的头部删除，只能在线性表的尾部插入，因此队列遵循先入先出的原则。可以解决程序设计中的类排队问题。
文尾附代码地址。

准备阶段

• 需要两个变量 front 及 rear 分别记录队列前后端的下标，其中front队头，会随着数据出队而改变；rear队尾，随着数据入队而改变
• 使用数组模拟队列，设数组大小的maxSize，那么当rear=maxSize-1时再入队会发生溢出，其中front=0 并且 rear=maxSize-1时再入队认为是真溢出；front不等于0 并且 rear=maxSize-1时再入队认为是假溢出。

为了解决假溢出的问题，可以通过取模%的方式实现循环队列。将队列想象成一个循环的表，分配给队列的存储空间可以循环使用，当rear为maxSize-1时，而front不为零（即队列的开始端空着），可以从头使用空着的空间，即base[maxSize-1]的下一个元素是base[0]。front同理。

• 为什么有少用一个元素空间的约定？

一般认为空队列的条件是front=rear=0，当从队尾插入一个元素时，front=0，rear=1，你可以想象一个列表，此时列表中只有一个元素，这个元素即是队头，又是队尾。此时队头front仍指向队列的第一个元素，即front=0；但队尾rear实际指向的是队尾元素的下一个元素的下标，即rear=1。

这样的话，当队列满时，此时下标为maxSize-1的元素刚入队，根据上述循环使用数组存储空间的构想，rear需要指向的是下标为0的元素，即rear=0。如果之前没有出队，此时front=0，队列已满（实际上rear=maxSize，此时rear % maxSize=front）。但是这个队满的条件包含队空的条件front=rear=0，无法区分队空和队满。

所以为了解决队空和队满判断条件相同的问题，就约定少使用一个元素空间，即manSize大小的数组，最多能存储maxSize-1个队列元素。约定的不使用的那个元素是数组的最后一个元素，判断队满的条件也就变成了(rear+1)%maxSize=front。

需要注意的是，少使用一个元素空间是一个约定俗成解决方案，并不是唯一方案，可以另设一个标志区分队空，队满；还可以另设一个变量记录元素个数。

使用数组模拟循环队列

class CircleQueue {
    private int front;
    private int rear;
    private int[] arr;
    private int maxSize;

    public CircleQueue(int size) {
        //front rear初始值都为0，rear这里指向的是最后一个元素的后一个元素
        maxSize = size;
        arr = new int[maxSize];
    }
}

• 判断队空

    public boolean isEmpty() {
        return front == rear;
    }

• 判断队满

    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

• 入队

    public void addQueue(int num) {
        if (isFull()) {
            System.out.println("队列已满，无法入队");
            return;
        }
        arr[rear] = num;
        rear = (rear + 1) % maxSize;
    }

• 出队

    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法出队");
        }
        int val = arr[front];
        front = (front + 1) % maxSize;
        return val;
    }

• 显示队头元素

    public int peekQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front];
    }

• 遍历队列元素

    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
        }
        //从front遍历到rear
        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;
    }

代码地址

代码git地址