使用数组完成一个环形队列

队列的性质不多介绍，这里介绍如果使用数组完成一个环形队列。使用数组实现一个环形队列只有一个难点，就是如何判断一个环形队列是否已满。

判断队满是一个稍微需要理解的概念，刚开始大家会好奇为什么使用求余 % 这个操作符。

首先我们需要知道求余操作符的特性：当被除数小于除数的时候，其余数为被除数本身。其次我们需要始终记得，当尾指针rear的前一位等于头指针front的时候，代表该队列已满。(即当rear=7，front=0或者rear=2，front=3时，见图)

环形队列

队满代码

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

此时我们仔细观察表达式，会发现(rear+1)%max有两种情况：

当指针指向除尾部的最后一个值时，rear+1始终小于max，则其值等于该指针的后一位。(当rear指针指向0-6的时候，见图)
当指针指向数组的最后端时，rear+1会等于数组的最大长度，则其值等于0，正好也是环形队列中的尾指针的后一位。(即指针指向7的时候，见图)

完整代码

class ArrayQueue{
    // 头指针
    int front = 0;
    // 尾指针
    int rear = 0;
    // 存放数据的数组
    int[] queue;
    // 数组的长度,用于后序判断栈是否满
    int max;

    public ArrayQueue(int max) {
        this.max = max;
        queue = new int[max];
    }

    // 判断是否队空
    public boolean isEmpty() {
        // 当头指针和尾指针指向同一个值的时候，代表该队列为空
        return front == rear;
    }

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

    // 向队列中添加元素
    public void add(int n) throws Exception  {
        if (isFull()) {
            throw new Exception("queue is full");
        }

        queue[rear] = n;
        // 将rear指针后移一位（当你理解如何判断栈满时，后移一位也很容易理解了）
        rear = (rear + 1) % max;
    }

    // 向队列中获取头元素
    public int get() throws Exception {
        if ( isEmpty() ) {
            throw new Exception("queue is empty");
        }

        int res = queue[front];
        // 将front指针后移一位
        front = (front + 1) % max;
        return res;
    }
}

CATALOG

FEATURED TAGS

FRIENDS