??作者 : D. Star.
??專欄 : 數(shù)據(jù)結(jié)構(gòu)
??今日分享 : 丟臉其實(shí)并沒有那么可怕，我們可以從另一個(gè)角度來(lái)想：別人能夠記住我了，而且過了還有多少人能記得我呢？雖然這種出場(chǎng)不太優(yōu)雅??

??題目鏈接：

【力扣–622】設(shè)計(jì)循環(huán)隊(duì)列

??題目：

設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。 循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為“環(huán)形緩沖器”。

循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲(chǔ)新的值。

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 設(shè)置長(zhǎng)度為 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，隊(duì)列已滿
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

??解題思路：

通過一個(gè)定長(zhǎng)數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列
入隊(duì)：首先要判斷隊(duì)列是否已滿，再進(jìn)行入隊(duì)的操作，入隊(duì)操作需要考慮索引循環(huán)的問題，當(dāng)索引越界，需要讓它變成最小值
出隊(duì)：首先要判斷隊(duì)列是否為空，再進(jìn)行出隊(duì)操作，出隊(duì)也需要考慮索引循環(huán)的問題
判空： 隊(duì)頭 == 隊(duì)尾
判滿： 隊(duì)尾 + 1 == 隊(duì)頭

??代碼詳情：

typedef struct {
    int* a;
    int front;
    int rear;
    int k;//數(shù)組大小
} MyCircularQueue;


//構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 k 。
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

//檢查循環(huán)隊(duì)列是否已滿。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return ((obj->rear+1) % (obj->k+1) == obj->front);
}

// 檢查循環(huán)隊(duì)列是否為空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front == obj->rear;
}

//向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        //法一：
        // obj->a[obj->rear] = value;
        // obj->rear = (obj->rear+1)%(obj->k+1);

        //法二：
        obj->a[obj->rear++] = value;
        obj->rear %= (obj->k+1);

        return true;  
    }
}

//從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        //出數(shù)據(jù)
        obj->front++;
        obj->front %= (obj->k+1);
        return true;
    }
}

// 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

// 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;  
    else
    {
        int ret = obj->rear == 0 ? obj->k : obj->rear - 1;
        return obj->a[ret];
    }
}

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

總結(jié)：

一定要理解好判空和判滿的邏輯，不然做題很費(fèi)勁的?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-459279.html

家人們,點(diǎn)個(gè)再走唄~

到了這里，關(guān)于【力扣--622】設(shè)計(jì)循環(huán)隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！