摘要：為了方便大家查閱，筆者在這里貼出相關(guān)的地址版數(shù)據(jù)結(jié)構(gòu)數(shù)組版數(shù)據(jù)結(jié)構(gòu)棧版數(shù)據(jù)結(jié)構(gòu)隊(duì)列數(shù)組隊(duì)列為了解決數(shù)組隊(duì)列帶來的問題，本篇給大家介紹一下循環(huán)隊(duì)列。

在上一篇，筆者給大家介紹了數(shù)組隊(duì)列，并且在文末提出了數(shù)組隊(duì)列實(shí)現(xiàn)上的劣勢，以及帶來的性能問題（因?yàn)閿?shù)組隊(duì)列，在出隊(duì)的時候，我們往往要將數(shù)組中的元素往前挪動一個位置，這個動作的時間復(fù)雜度O(n)級別），如果不清楚的小伙伴歡迎查看閱讀。為了方便大家查閱，筆者在這里貼出相關(guān)的地址：

Java版-數(shù)據(jù)結(jié)構(gòu)-數(shù)組

Java版-數(shù)據(jù)結(jié)構(gòu)-棧

Java版-數(shù)據(jù)結(jié)構(gòu)-隊(duì)列（數(shù)組隊(duì)列）

為了解決數(shù)組隊(duì)列帶來的問題，本篇給大家介紹一下循環(huán)隊(duì)列。

啰嗦一下，由于筆者不太會弄貼出來的圖片帶有動畫效果，比如元素的移動或者刪除（畢竟這樣看大家比較直觀），筆者在這里只能通過靜態(tài)圖片的方式，幫助大家理解實(shí)現(xiàn)原理，希望大家不要見怪，如果有朋友知道如何搞的話，歡迎在評論區(qū)慧言。

在這里，我們聲明了一個容量大小為8的數(shù)組，并標(biāo)出了索引0-7，然后使用front和tail分別來表示隊(duì)列的，隊(duì)首和隊(duì)尾；在下圖中，front和tail的位置一開始都指向是了索引0的位置，這意味著當(dāng)front == tai的時候 隊(duì)列為空 大家務(wù)必牢記這一點(diǎn)，以便區(qū)分后面介紹隊(duì)列快滿時的臨界條件

為了大家更好地理解下面的內(nèi)容，在這里，我簡單做幾點(diǎn)說明

front：表示隊(duì)列隊(duì)首，始終指向隊(duì)列中的第一個元素（當(dāng)隊(duì)列空時，front指向索引為0的位置）

tail：表示隊(duì)列隊(duì)尾，始終指向隊(duì)列中的最后一個元素的下一個位置

元素入隊(duì)，維護(hù)tail的位置，進(jìn)行tail++操作

元素出隊(duì)，維護(hù)front的位置，進(jìn)行front++操作

上面所說的，元素進(jìn)行入隊(duì)和出隊(duì)操作，都簡單的進(jìn)行++操作，來維護(hù)tail和front的位置，其實(shí)是不嚴(yán)謹(jǐn)?shù)模_的維護(hù)tail的位置應(yīng)該是(tail + 1) % capacity，同理front的位置應(yīng)該是(front + 1) % capacity，這也是為什么叫做循環(huán)隊(duì)列的原因，大家先在這里知道下，暫時不理解也沒關(guān)系，后面相信大家會知曉。

下面我們看一下，現(xiàn)在如果有一個元素a入隊(duì)，現(xiàn)在的示意圖：

我們現(xiàn)在看到了元素a入隊(duì)，我們的tail指向的位置發(fā)生了變化，進(jìn)行了++操作，而front的位置，沒有發(fā)生改變，仍舊指向索引為0的位置，還記得筆者上面所說的，front的位置，始終指向隊(duì)列中的第一個元素，tail的位置，始終指向隊(duì)列中的最后一個元素的下一個位置

現(xiàn)在，我們再來幾個元素b、c、d、e進(jìn)行入隊(duì)操作，看一下此時的示意圖：

想必大家都能知曉示意圖是這樣，好像沒什么太多的變化（還請大家別著急，筆者這也是方便大家理解到底是什么循環(huán)隊(duì)列，還請大家原諒我O(∩_∩)O哈?。?/p>

看完了元素的入隊(duì)的操作情況，那現(xiàn)在我們看一下，元素的出隊(duì)操作是什么樣的？

元素a出隊(duì)，示意圖如下：

現(xiàn)在元素a已經(jīng)出隊(duì)，front的位置指向了索引為1的位置，現(xiàn)在數(shù)組中所有的元素不再需要往前挪動一個位置

這一點(diǎn)和我們的數(shù)組隊(duì)列（我們的數(shù)組隊(duì)列需要元素出隊(duì)，后面的元素都要往前挪動一個位置）完全不同，我們只需要改變一下front的指向就可以了，由之前的O(n)操作，變成了O(1)的操作

我們再次進(jìn)行元素b出隊(duì)，示意圖如下：

到這里，可能有的小伙伴會問，為什么叫做，循環(huán)隊(duì)列？那么現(xiàn)在我們嘗試一下，我們讓元素f、g分別進(jìn)行入隊(duì)操作，此時的示意圖如下：

大家目測看下來還是沒什么變化，如果此時，我們再讓一個元素h元素進(jìn)行入隊(duì)操作，那么問題來了我們的tail的位置該如何指向呢？示意圖如下：

根據(jù)我們之前說的，元素入隊(duì)：維護(hù)tail的位置，進(jìn)行tail++操作，而此時我們的tail已經(jīng)指向了索引為7的位置，如果我們此時對tail進(jìn)行++操作，顯然不可能（數(shù)組越界）

細(xì)心的小伙伴，會發(fā)現(xiàn)此時我們的隊(duì)列并沒有滿，還剩兩個位置（這是因?yàn)槲覀冊爻鲫?duì)后，當(dāng)前的空間，沒有被后面的元素?cái)D掉），大家可以把我們的數(shù)組想象成一個環(huán)狀，那么索引7之后的位置就是索引0

如何才能從索引7的位置計(jì)算到索引0的位置，之前我們一直說進(jìn)行tail++操作，筆者也在開頭指出了，這是不嚴(yán)謹(jǐn)?shù)?，?yīng)該的是(tail + 1) % capacity這樣就變成了(7 + 1) % 8等于 0

所以此時如果讓元素h入隊(duì)，那么我們的tail就指向了索引為0的位置，示意圖如下：

假設(shè)現(xiàn)在又有新的元素k入隊(duì)了，那么tail的位置等于（tail + 1） % capacity 也就是（0 + 1）% 8 等于1就指向了索引為1的位置

那么問題來了，我們的循環(huán)隊(duì)列還能不能在進(jìn)行元素入隊(duì)呢？我們來分析一下，從圖中顯示，我們還有一個索引為0的空的空間位置，也就是此時tail指向的位置

按照之前的邏輯，假設(shè)現(xiàn)在能放入一個新元素，我們的tail進(jìn)行(tail +1) % capacity計(jì)算結(jié)果為2（如果元素成功入隊(duì)，此時隊(duì)列已經(jīng)滿了），此時我們會發(fā)現(xiàn)表示隊(duì)首的front也指向了索引為2的位置

如果新元素成功入隊(duì)的話，我們的tail也等于2，那么此時就成了 tail == front ，一開始我們提到過，當(dāng)隊(duì)列為空的tail == front，現(xiàn)在呢，如果隊(duì)列為滿時tail也等于front，那么我們就無法區(qū)分，隊(duì)列為滿時和隊(duì)列為空時收的情況了

所以，在循環(huán)隊(duì)列中，我們總是浪費(fèi)一個空間，來區(qū)分隊(duì)列為滿時和隊(duì)列為空時的情況，也就是當(dāng) ( tail + 1 ) % capacity == front的時候，表示隊(duì)列已經(jīng)滿了，當(dāng)front == tail的時候，表示隊(duì)列為空。

了解了循環(huán)隊(duì)列的實(shí)現(xiàn)原理之后，下面我們用代碼實(shí)現(xiàn)一下。

接口定義 ：Queue

public interface Queue {
    /**
     * 入隊(duì)
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出隊(duì)
     *
     * @return
     */
    E dequeue();

    /**
     * 獲取隊(duì)首元素
     *
     * @return
     */
    E getFront();

    /**
     * 獲取隊(duì)列中元素的個數(shù)
     *
     * @return
     */
    int getSize();

    /**
     * 判斷隊(duì)列是否為空
     *
     * @return
     */
    boolean isEmpty();
}

接口實(shí)現(xiàn)：LoopQueue

public class LoopQueue implements Queue {
    /**
     * 承載隊(duì)列元素的數(shù)組
     */
    private E[] data;
    /**
     * 隊(duì)首的位置
     */
    private int front;
    /**
     * 隊(duì)尾的位置
     */
    private int tail;
    /**
     * 隊(duì)列中元素的個數(shù)
     */
    private int size;

    /**
     * 指定容量，初始化隊(duì)列大小
     * (由于循環(huán)隊(duì)列需要浪費(fèi)一個空間，所以我們初始化隊(duì)列的時候，要將用戶傳入的容量加1)
     *
     * @param capacity
     */
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
    }

    /**
     * 模式容量，初始化隊(duì)列大小
     */
    public LoopQueue() {
        this(10);
    }


    @Override
    public void enqueue(E e) {
        // 檢查隊(duì)列為滿
        if ((tail + 1) % data.length == front) {
            // 隊(duì)列擴(kuò)容
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }


    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊(duì)列為空");
        }
        // 出隊(duì)元素
        E element = data[front];
        // 元素出隊(duì)后，將空間置為null
        data[front] = null;
        // 維護(hù)front的索引位置(循環(huán)隊(duì)列)
        front = (front + 1) % data.length;
        // 維護(hù)size大小
        size--;

        // 元素出隊(duì)后，可以指定條件，進(jìn)行縮容
        if (size == getCapacity() / 2 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return element;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊(duì)列為空");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }


    // 隊(duì)列快滿時，隊(duì)列擴(kuò)容；元素出隊(duì)操作，指定條件可以進(jìn)行縮容
    private void resize(int newCapacity) {
        // 這里的加1還是因?yàn)檠h(huán)隊(duì)列我們在實(shí)際使用的過程中要浪費(fèi)一個空間
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // 注意這里的寫法：因?yàn)樵跀?shù)組中，front 可能不是在索引為0的位置，相對于i有一個偏移量
            newData[i] = data[(i + front) % data.length];
        }
        // 將新的數(shù)組引用賦予原數(shù)組的指向
        data = newData;
        // 充值front的位置（front總是指向隊(duì)列中第一個元素）
        front = 0;
        // size 的大小不變，因?yàn)樵谶@過程中，沒有元素入隊(duì)和出隊(duì)
        tail = size;
    }


    private int getCapacity() {
        // 注意：在初始化隊(duì)列的時候，我們有意識的為隊(duì)列加了一個空間，那么它的實(shí)際容量自然要減1
        return data.length - 1;
    }

    @Override
    public String toString() {
        return "LoopQueue{" +
                "【隊(duì)首】data=" + Arrays.toString(data) + "【隊(duì)尾】" +
                ", front=" + front +
                ", tail=" + tail +
                ", size=" + size +
                ", capacity=" + getCapacity() +
                "}";
    }
}

測試類：LoopQueueTest

public class LoopQueueTest {
    @Test
    public void testLoopQueue() {
        LoopQueue loopQueue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            loopQueue.enqueue(i);
        }
        // 初始化隊(duì)列數(shù)據(jù)
        System.out.println("原始隊(duì)列: " + loopQueue);
        // 元素0出隊(duì)
        loopQueue.dequeue();
        System.out.println("元素0出隊(duì): " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素1出隊(duì): " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素2出隊(duì): " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素3出隊(duì): " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素4出隊(duì),發(fā)生縮容: " + loopQueue);
        // 隊(duì)首元素
        System.out.println("隊(duì)首元素：" + loopQueue.getFront());
    }
}

測試結(jié)果：

原始隊(duì)列: LoopQueue{【隊(duì)首】data=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【隊(duì)尾】, front=0, tail=10, size=10, capacity=10}
元素0出隊(duì): LoopQueue{【隊(duì)首】data=[null, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【隊(duì)尾】, front=1, tail=10, size=9, capacity=10}
元素1出隊(duì): LoopQueue{【隊(duì)首】data=[null, null, 2, 3, 4, 5, 6, 7, 8, 9, null]【隊(duì)尾】, front=2, tail=10, size=8, capacity=10}
元素2出隊(duì): LoopQueue{【隊(duì)首】data=[null, null, null, 3, 4, 5, 6, 7, 8, 9, null]【隊(duì)尾】, front=3, tail=10, size=7, capacity=10}
元素3出隊(duì): LoopQueue{【隊(duì)首】data=[null, null, null, null, 4, 5, 6, 7, 8, 9, null]【隊(duì)尾】, front=4, tail=10, size=6, capacity=10}
元素4出隊(duì),發(fā)生縮容: LoopQueue{【隊(duì)首】data=[5, 6, 7, 8, 9, null]【隊(duì)尾】, front=0, tail=5, size=5, capacity=5}
隊(duì)首元素：5

完整版代碼GitHub倉庫地址：Java版數(shù)據(jù)結(jié)構(gòu)-隊(duì)列（循環(huán)隊(duì)列） 歡迎大家【關(guān)注】和【Star】

至此筆者已經(jīng)為大家?guī)砹藬?shù)據(jù)結(jié)構(gòu)：靜態(tài)數(shù)組、動態(tài)數(shù)組、棧、數(shù)組隊(duì)列、循環(huán)隊(duì)列；接下來，筆者還會一一的實(shí)現(xiàn)其它常見的數(shù)組結(jié)構(gòu)，大家一起加油。

靜態(tài)數(shù)組

動態(tài)數(shù)組

棧

數(shù)組隊(duì)列

循環(huán)隊(duì)列

鏈表

循環(huán)鏈表

二分搜索樹

優(yōu)先隊(duì)列

堆

線段樹

字典樹

AVL

紅黑樹

哈希表

....

持續(xù)更新中，歡迎大家關(guān)注公眾號：小白程序之路（whiteontheroad），第一時間獲取最新信息！?。?/p>

筆者博客地址：http:www.gulj.cn