引言

隊(duì)列，是一個線性表，和數(shù)組，棧，鏈表類似。隊(duì)列和棧類似，戲稱“邊吃邊拉”。即 FIFO。

隊(duì)列和棧還有一個不同，棧只需維護(hù)一個棧頂指針，而隊(duì)列需要維護(hù) 2 個指針，隊(duì)首和隊(duì)尾。

實(shí)現(xiàn) 1

隊(duì)列可以使用數(shù)組實(shí)現(xiàn)，例如 Java 類庫的 LinkedBlockingQueue，也可以使用數(shù)組實(shí)現(xiàn)，例如 Java 的 ArrayBlockingQueue。這里我們討論數(shù)組的實(shí)現(xiàn)。

通常使用數(shù)組實(shí)現(xiàn)，會使用循環(huán)數(shù)組，也稱 ringBuffer，好處是不用 copy 數(shù)組進(jìn)行遷移，另外，傳統(tǒng)實(shí)現(xiàn)，如果數(shù)組滿了，就不能再繼續(xù)插入了，即使前面還有空間，因此就需要剛剛說的 copy 進(jìn)行遷移。下面是最簡單的一個 Java 循環(huán)數(shù)組實(shí)現(xiàn)。

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;
    }
}

這個是一個標(biāo)準(zhǔn)的實(shí)現(xiàn)，但是存在一個問題：如果隊(duì)列長度是 8，那么就只能存儲 7 個元素。原因下面分析。

這個圖，表示隊(duì)列為空，因?yàn)?put 指針和 get 指針，指向了同一個槽位。get 指針不能夠再繼續(xù)移動。

那如果表示滿了呢？

這個圖，get 指針在 5 槽位，put 指針 4 槽位，put 指針不能再繼續(xù)移動，否則會覆蓋 5 槽位的值。

由此我們得到公式：

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

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

當(dāng) put 在 7 這個槽位，get 在 0 這個槽位，他還能繼續(xù)放入元素在 7 這個位置嗎？答案是不能，因?yàn)槲覀兺ㄟ^ put + 1 % n == get 這個公式計算，如果 在 7 個槽位加入了元素，那么 put 指針就會變成 0，問題來了，put 是 0 ，get 也是0。

而 isEmpty 的公式是 put == get。這個時候，就會發(fā)生判斷錯誤：原本是滿的，卻判斷是空的。

所以，這個實(shí)現(xiàn)導(dǎo)致必須有一個空位。當(dāng)然，我們也可以把槽位加1，也就是把數(shù)組長度加 1，避免實(shí)際長度不符合預(yù)期，也可以避免這個問題。

實(shí)現(xiàn) 2

通過上面的分析，我們知道了，如果不加上1，將導(dǎo)致 isEmpty 判斷錯誤。原因是如果 put 和 get 指針重合，我們無法區(qū)分到底是 滿了 還是 空了。因?yàn)槲覀兣袛嗍菨M還是空，利用的是指針。

如果不使用指針呢？使用一個計算器，例如，添加一個元素，計算器 + 1， 刪除一個元素，計算器 - 1. 是否可以呢？答案是可以的.

下面是具體實(shí)現(xiàn)：

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 判斷，這樣就解決了這個問題。

總結(jié)

隊(duì)列可以使用鏈表和數(shù)組實(shí)現(xiàn)，通常使用使用數(shù)組實(shí)現(xiàn)，效率高，不用搬移。使用循環(huán)數(shù)組，需要考慮的是 ifFull 判斷和 isEmpty 判斷。

這里我建議使用 size 這種方式，而不是 + 1 這種方式，為什么呢？使用 size 這種方式，我們可以利用 & 運(yùn)算來快速計算下標(biāo)——只要用戶指定的隊(duì)列長度是 2 的冪次方。

如果使用 + 1 的方式，即使用戶指定的隊(duì)列長度是 2 的冪次方，也無法使用 & 運(yùn)算快速獲取下標(biāo)。

當(dāng)然，我們也可以根據(jù)用戶指定的隊(duì)列長度是否為2 的冪次方，來覺得到底是使用 size 方式，還是使用 + 1 方式。