一、普通隊(duì)列的弊端

隊(duì)列：是一種可以分別在兩端進(jìn)行增刪的特殊線性表。既然是線性表，那么可以使用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)來(lái)實(shí)現(xiàn)，如果是鏈?zhǔn)酱鎯?chǔ)的話，那么增刪的復(fù)雜度都是O(1)，這一點(diǎn)很好理解，應(yīng)該只要修改一下指針就好了，如果是順序存儲(chǔ)的話，在隊(duì)尾增加的時(shí)間復(fù)雜度是O(1)，但是在隊(duì)頭進(jìn)行刪除的時(shí)候，會(huì)涉及到遷移操作，這時(shí)候的時(shí)候復(fù)雜度就是O(n)，所以一般來(lái)講不會(huì)直接使用順序存儲(chǔ)的方式來(lái)實(shí)現(xiàn)普通隊(duì)列。

image.png

二、循環(huán)隊(duì)列的原理概述

較之普通隊(duì)列用順序存儲(chǔ)來(lái)實(shí)現(xiàn)存在刪除帶來(lái)的時(shí)間損耗，怎么去避免它，因?yàn)槠胀?duì)列刪除隊(duì)頭結(jié)點(diǎn)，會(huì)將后續(xù)結(jié)點(diǎn)進(jìn)行整體的一個(gè)前移，所以才會(huì)帶來(lái)O(n)的時(shí)間復(fù)雜度，如果不前移結(jié)點(diǎn)，而是調(diào)整頭結(jié)點(diǎn)的位置，刪除一個(gè)結(jié)點(diǎn)，就將頭結(jié)點(diǎn)往后移動(dòng)一位。

TIP：front是指向頭結(jié)點(diǎn)的指針，rear是指向下一個(gè)要插入結(jié)點(diǎn)的指針

隊(duì)列初始狀態(tài).png

隊(duì)列刪除結(jié)點(diǎn)后的狀態(tài).png

那么這樣子是可以避免刪除帶來(lái)的時(shí)間損耗了，但是可以發(fā)現(xiàn)當(dāng)往下標(biāo)4插入數(shù)據(jù)后，rear指針該何去何從，放在腳標(biāo)5？那么會(huì)報(bào)數(shù)組越界，而且很明顯下標(biāo)0和1的位置都空著，所以rear應(yīng)該指向0才對(duì)，那么這種實(shí)現(xiàn)方式其實(shí)就是循環(huán)列表。

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

實(shí)現(xiàn)循環(huán)列表存在幾個(gè)要考慮的事情：
1：啥時(shí)候表示隊(duì)列空著？
一般在循環(huán)隊(duì)列的初始狀態(tài)，可以將front和rear指針都指向下標(biāo)0，當(dāng)插入元素時(shí)，rear會(huì)順時(shí)針?lè)较蚶奂?，?dāng)刪除元素時(shí)，front也會(huì)順時(shí)針?lè)较蚶奂?，那么刪的和加的一樣多，其實(shí)在同一個(gè)方向走的下標(biāo)也一樣多，那么自然容易想到當(dāng)front == rear時(shí)，表示隊(duì)列為空。只不過(guò)這里需要注意一點(diǎn)，因?yàn)槭茄h(huán)隊(duì)列，front和rear的值不能無(wú)限遞增，比如一個(gè)數(shù)組，大小為5，最大下標(biāo)是4，難道還能4+1=5，出來(lái)個(gè)5下標(biāo)，明顯不可能，所以，這里的遞增，需要這么操作：
(front + 1) % maxSize，巧妙的用到了取模運(yùn)算符。

2：啥時(shí)候表示隊(duì)列滿了？
隊(duì)列啥時(shí)候算滿呢？其實(shí)可以發(fā)現(xiàn)front可能在rear的后面，也有可能在rear的前面，仔細(xì)想想可能會(huì)發(fā)現(xiàn)某種情況下，當(dāng)rear == front也是隊(duì)列滿的時(shí)候，但是這樣就跟隊(duì)列空著的時(shí)候，判斷條件一致了，這樣明顯也不行，為了區(qū)分開(kāi)來(lái)，單獨(dú)留一個(gè)結(jié)點(diǎn)不存值，當(dāng)rear和front相差一個(gè)結(jié)點(diǎn)時(shí)，即證明循環(huán)隊(duì)列已滿。判斷條件為：(rear + 1) % maxSize = front

循環(huán)隊(duì)列滿的狀態(tài).png

3：怎么才能知道隊(duì)列當(dāng)前含有元素的多少?
由于循環(huán)隊(duì)列的特性，隊(duì)列里面的元素可能是連續(xù)的，也有可能是分成兩段的，那么怎么去統(tǒng)計(jì)含有多少元素呢？可以使用這個(gè)公式(rear - front + maxSize) % maxSize，因?yàn)閞ear - front可能為正數(shù)，也有可能會(huì)負(fù)數(shù)，為正數(shù)表示是連續(xù)的，為負(fù)數(shù)表示不連續(xù)的。

三、循環(huán)隊(duì)列的實(shí)現(xiàn)-java

public class CircularQueue<E> {
    /**
     * 循環(huán)隊(duì)列
     */
    /**
     * 循環(huán)隊(duì)列常用的方法如下：
     * 1、InitCircularQueue()    初始化一個(gè)循環(huán)隊(duì)列
     * 2、ClearCircularQueue()   清空一個(gè)循環(huán)隊(duì)列
     * 3、CircularEmpty()    判斷循環(huán)隊(duì)列是否為空
     * 4、GetHead()  獲取循環(huán)隊(duì)列尾部結(jié)點(diǎn)數(shù)據(jù)
     * 5、EnCircularQueue()  在循環(huán)隊(duì)列尾部插入新結(jié)點(diǎn)
     * 6、DeCircularQueue()  刪除循環(huán)隊(duì)列頭部結(jié)點(diǎn)
     * 7、CircularQueueLength()  返回循環(huán)隊(duì)列的長(zhǎng)度
     */

    Object[] queueArray = null;
    int front; //隊(duì)頭指針
    int rear; //隊(duì)尾指針
    int maxQueueSize;
    public CircularQueue(int maxSize){
        // 初始化循環(huán)隊(duì)列的基礎(chǔ)存儲(chǔ)結(jié)構(gòu)，數(shù)組
        this.maxQueueSize = maxSize;
        this.queueArray = new Object[maxSize];
        this.front = 0; //隊(duì)頭指針指向循環(huán)隊(duì)列的第一個(gè)結(jié)點(diǎn)，初始為0
        this.rear = 0;//隊(duì)尾指針指向循環(huán)隊(duì)列的待插入結(jié)點(diǎn)位置，初始為0
    }
    public void ClearCircularQueue(){
        if (front == rear){return;}
        //清空一個(gè)循環(huán)隊(duì)列，只需要從front開(kāi)始，一直到rear-1，將節(jié)點(diǎn)元素賦值成null
        for (;front != rear;){
            DeCircularQueue();
        }
    }

    public Boolean CircularEmpty(){
        if (front == rear){return true;}
        else{return false;}
    }

    public E GetHead(){
        return (E)queueArray[front];
    }

    public void EnCircularQueue(E elem){
        //滿足(rear+1)%maxSize=front說(shuō)明該循環(huán)隊(duì)列已經(jīng)達(dá)到滿隊(duì)列狀態(tài)，無(wú)法在插入
        if ((rear + 1) % maxQueueSize == front){
            return;
        }
        queueArray[rear] = elem;
        //循環(huán)隊(duì)列在rear指針時(shí)，如果只是簡(jiǎn)單累加，很可能會(huì)出現(xiàn)空指針異常
        rear = (rear + 1) % maxQueueSize;
    }

    public E DeCircularQueue (){
        //滿足front = rear時(shí)，說(shuō)明隊(duì)列為空
        if (front == rear){return null;}
        E returnElem = (E)queueArray[front];
        queueArray[front] = null;
        front = (front + 1) % maxQueueSize;
        return returnElem;
    }

    public int CircularQueueLength(){
        return (rear - front + maxQueueSize) % maxQueueSize;
    }

    public String toString(){
        StringBuffer stringBuffer = new StringBuffer();
        for (int index = 0;index < maxQueueSize;index++){
            if (index + 1 < maxQueueSize){
                stringBuffer.append(queueArray[index]);
                stringBuffer.append(",");
            }else{
                stringBuffer.append(queueArray[index]);
            }
        }
        return stringBuffer.toString();
    }

    public static void main(String[] args) {
    }
}

四、循環(huán)隊(duì)列時(shí)間復(fù)雜度分析

可以很明顯發(fā)現(xiàn)，循環(huán)隊(duì)列的增刪操作時(shí)間復(fù)雜度都是O(1)，并且還能實(shí)現(xiàn)充分利用申請(qǐng)到的空間，所以如果能夠確認(rèn)一個(gè)隊(duì)列的大小，那么就使用順序方式來(lái)實(shí)現(xiàn)，并且是循環(huán)隊(duì)列，而不是普通隊(duì)列。如果確認(rèn)不了，那么還是使用鏈?zhǔn)椒绞絹?lái)實(shí)現(xiàn)。