循环队列

示例练习>>>

在前面讲队列的数组实现的时候会有一个问题，就是如果不停的删除和添加元素，会导致 front 和 tail 越来越大，前面的空间都不能在使用了，最后数组可用的空间就越来越少，如下图所示。

如果还想使用前面的存储空间，可以让数组首尾相连，类似一个环形，这样当在数组的最后一个位置存放数据之后就让 tail 变成 0 ，指向数组的第一个位置，如下图所示。

来看下代码：

public class CircularQueue<E> {
    private final Object[] data; // 队列中存放元素的数组。
    private final int maxSize;// 队列的最大容量。
    private int size; // 队列中元素的个数。
    private int front = 0;// 队列的头，只能删除，指向队列的第一个元素。
    private int tail = 0; // 队列的尾，只能添加，指向队列最后一个元素的下一个位置。

    public CircularQueue(int maxSize) {
        if (maxSize <= 0)
            throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
        this.maxSize = maxSize;
        data = new Object[this.maxSize];
    }

    public void add(E val) {
        if (isFull())
            throw new IllegalStateException("队列已经满了，无法再加入……");
        data[tail++] = val;
        tail %= maxSize;// 循环。
        size++;
    }

    // 删除
    public E remove() {
        if (isEmpty())
            throw new IllegalStateException("队列是空的，无法删除……");
        E res = (E) data[front];
        data[front++] = null;
        front %= maxSize;// 循环。
        size--;
        return res;
    }

    // 获取队列头部元素
    public E top() {
        if (isEmpty())
            throw new IllegalStateException("队列为空");
        return (E) data[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == maxSize;
    }

    public int size() {
        return size;
    }
}

相关链接