所屬專欄：玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)題型??
?? >博主首頁：初陽785??
?? >代碼托管：chuyang785??
?? >感謝大家的支持，您的點贊和關注是對我最大的支持?。?！??
?? >博主也會更加的努力，創(chuàng)作出更優(yōu)質(zhì)的博文！！??
?? >關注我，關注我，關注我，重要的事情說三遍?。。。。。。?！??
??????????????????????????????????????????????????

?? 1.題目來源

LeetCode 設計循環(huán)鏈表

??2.題目描述

設計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。
循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。

• 你的實現(xiàn)應該支持如下操作：
  1.MyCircularQueue(k): 構(gòu)造器，設置隊列長度為 k 。
  2.Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
  3.Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
  4.enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
  5.deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
  6.isEmpty(): 檢查循環(huán)隊列是否為空。
  7.isFull(): 檢查循環(huán)隊列是否已滿。

??3.解題思路

• ?? 所謂循環(huán)隊列，指的就是開辟的空間可以重復利用，這個有點類似于在一個圈里你追我趕的樣子，所以我們可以定義追的變量front，一個跑的變量rear，當每添加一個數(shù)據(jù)時rear就走一步，每刪除一個數(shù)據(jù)的時候front就走一步，而front與rear之間的距離就是元素的個數(shù)，而只要元素個數(shù)小于我們的開辟的空間就說明還可以添加數(shù)據(jù)??。

• ??我們分析一下題目給我們的要求是，給定固定長度的環(huán)元素個數(shù)，要返回隊首和隊尾的元素，以及判斷是否滿了，是否是空，而當我們觀察上面的圖后會發(fā)現(xiàn)，如果我們實現(xiàn)函數(shù)用的時隊列的話，那必須是一個循環(huán)隊列??，而如果要返回隊首元素的話是比較簡單的，但是如果要返回隊尾元素的話就不好找rear的前一個數(shù)據(jù)，而且再判斷是否滿以及是否為空的時候不好確定，因為滿和空front都等于rear??。

*所以思來想去我們不妨不使用隊列，??我們使用數(shù)組來實現(xiàn)這一操作。而且為了區(qū)分滿和為空，我們想到了一個特別的方法，??就是多開一個空間，這塊空間不存放數(shù)據(jù)，??這樣子當front = = rear 的時候就是為空的時候，當rear+1 = = front 的時候就是為滿的時候。??而且這個時候返回隊頭和隊尾的數(shù)據(jù)都是比較簡單的。??但是這有個問題，那就是數(shù)組怎么實循環(huán)？這個時候就要用到取模操作了，當rear走到多開的那個空間的時候，如果還能還能進行添加數(shù)據(jù)，那么rear就要回到數(shù)組下標為0處的空間，也就是rear = rear%(k+1)，同理front = front%(k+1)，這個樣子就實現(xiàn)了數(shù)組循環(huán)。那怎么判斷滿了呢？就是判斷rear的下一個是不是front那就是(rear+1)%(k+1) == front如果相等就是滿了，反之沒有滿。

• ??同時解釋一下我們oj刷題的時出現(xiàn)的一些一些疑問

typedef struct {

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {

}

這個是我們題目出現(xiàn)的函數(shù)接口，我來解釋一下表示什么意思。文章來源地址http://www.zghlxwxcb.cn/news/detail-638688.html

1. 我們分析過了要定義兩個變量，front和rear同時還有一個固定長度k，而我們通常遇到這種兩個及以上的要使用的成員時，??為了減少傳遞的參數(shù)，以及代碼的可讀性，簡潔性，??我們通常會用一個結(jié)構(gòu)體把他們封裝起來，并且這個結(jié)構(gòu)體還是個匿名結(jié)構(gòu)體，匿名結(jié)構(gòu)體的特點就是只能用一次，這里我們只需要使用一次即可，所以匿名合理。
2. 而另一個函數(shù)接口是用來初始化我們的結(jié)構(gòu)體的，并返回結(jié)構(gòu)體指針。??

??4.代碼展示

typedef struct {
	//a用來開辟數(shù)組
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    ret->a =(int*)malloc((k+1)*sizeof(int));
    ret->front = ret->rear = 0;
    ret->k = k;
    return ret;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	//如果相等數(shù)組為空
    return (obj->front) == (obj->rear);
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	//如果rear的下一個是front說明滿了
    return (obj->rear+1)%(obj->k+1) == obj->front;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->rear == 0 ? obj->a[obj->k] : obj->a[obj->rear-1];
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
        return false;
    
    obj->a[obj->rear] = value;
    obj->rear++;
    //設計循環(huán)數(shù)組
    obj->rear %= (obj->k+1);

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return false;
    
    obj->front++;
    //設計循環(huán)數(shù)組
    obj->front %= (obj->k+1);
    
    return true;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

到了這里，關于【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（13）[設計循環(huán)鏈表]的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！