队列的 2 种实现方式

引言

队列，是一个线性表，和数组，栈，链表类似。队列和栈类似，戏称“边吃边拉”。即 FIFO。

队列和栈还有一个不同，栈只需维护一个栈顶指针，而队列需要维护 2 个指针，队首和队尾。

实现 1

队列可以使用数组实现，例如 Java 类库的 LinkedBlockingQueue，也可以使用数组实现，例如 Java 的 ArrayBlockingQueue。这里我们讨论数组的实现。

通常使用数组实现，会使用循环数组，也称 ringBuffer，好处是不用 copy 数组进行迁移，另外，传统实现，如果数组满了，就不能再继续插入了，即使前面还有空间，因此就需要刚刚说的 copy 进行迁移。下面是最简单的一个 Java 循环数组实现。

public class Queue {
    int[] node = new int[8];
    int n = node.length;
    int putIndex = 0;
    int getIndex = 0;
    public boolean enqueue(int x) {
        if (isFull()) {
            return false;
        }
        node[putIndex] = x;
        putIndex = (putIndex + 1) % n;
        return true;
    }

    public int dequeue() {
        if (isEmpty()) {
            return -1;
        }
        int x = node[getIndex];
        getIndex += 1;
        getIndex = getIndex % n;
        return x;
    }
    public boolean isFull() {
        return (putIndex + 1) % n == getIndex;
    }
    public boolean isEmpty() {
        return putIndex == getIndex;
    }
}

这个是一个标准的实现，但是存在一个问题：如果队列长度是 8，那么就只能存储 7 个元素。原因下面分析。

这个图，表示队列为空，因为 put 指针和 get 指针，指向了同一个槽位。get 指针不能够再继续移动。

那如果表示满了呢？

这个图，get 指针在 5 槽位，put 指针 4 槽位，put 指针不能再继续移动，否则会覆盖 5 槽位的值。

由此我们得到公式：

isEmpty = put == get;
ifFull = (put + 1) % n == get;

所以，put 一定比 get 少在一个槽位。

当 put 在 7 这个槽位，get 在 0 这个槽位，他还能继续放入元素在 7 这个位置吗？答案是不能，因为我们通过 put + 1 % n == get 这个公式计算，如果在 7 个槽位加入了元素，那么 put 指针就会变成 0，问题来了，put 是 0 ，get 也是0。

而 isEmpty 的公式是 put == get。这个时候，就会发生判断错误：原本是满的，却判断是空的。

所以，这个实现导致必须有一个空位。当然，我们也可以把槽位加1，也就是把数组长度加 1，避免实际长度不符合预期，也可以避免这个问题。

实现 2

通过上面的分析，我们知道了，如果不加上1，将导致 isEmpty 判断错误。原因是如果 put 和 get 指针重合，我们无法区分到底是满了还是空了。因为我们判断是满还是空，利用的是指针。

如果不使用指针呢？使用一个计算器，例如，添加一个元素，计算器 + 1，删除一个元素，计算器 - 1. 是否可以呢？答案是可以的.

下面是具体实现：

int[] node = new int[8];
    int n = node.length;
    int putIndex = 0;
    int getIndex = 0;
    int size = 0;

    public boolean enqueue(int x) {
        if (isFull()) {
            return false;
        }
        int index = (putIndex + 1) % n;
        node[index] = x;
        putIndex++;
        size++;
        return true;
    }
    public int dequeue() {
        if (isEmpty()) {
            return -1;
        }
        int index = (getIndex + 1) % n;
        getIndex++;
        int x = node[index];
        size--;
        return x;
    }
    public boolean isFull() {
        return size == n;
    }
    public boolean isEmpty() {
        return size == 0;
    }

我们判断 ifEmpty ，使用 size == 0 判断；判断 isFull，使用 size == n 判断，这样就解决了这个问题。

总结

队列可以使用链表和数组实现，通常使用使用数组实现，效率高，不用搬移。使用循环数组，需要考虑的是 ifFull 判断和 isEmpty 判断。

这里我建议使用 size 这种方式，而不是 + 1 这种方式，为什么呢？使用 size 这种方式，我们可以利用 & 运算来快速计算下标——只要用户指定的队列长度是 2 的幂次方。

如果使用 + 1 的方式，即使用户指定的队列长度是 2 的幂次方，也无法使用 & 运算快速获取下标。

当然，我们也可以根据用户指定的队列长度是否为2 的幂次方，来觉得到底是使用 size 方式，还是使用 + 1 方式。