力扣 -- 設計回圈佇列（題解）

此題需要實作一個回圈佇列，那么在此之前我們得知道佇列的概念和結構

佇列：只允許在一端插入，另一端洗掉操作的特殊線性表，具有先進先出后進后出的特性
出佇列：洗掉的一端叫隊頭
入佇列：插入的一端叫隊尾

知道了佇列的概念和結構就能開始做此題了，
題目鏈接
題目描述：

思路：首先先找到，佇列是空的條件和佇列是滿的條件，找到這兩個條件就很容易的做出來了，佇列為空的條件我給的是當隊頭和隊尾相等的時候說明，這個佇列為空，佇列滿的條件這個佇列和隊尾的下一個相等的時候就是滿的，看到這里細心的朋友可能已經看出來了，這樣的話豈不是要少一個資料？事實確實是也是這樣但是為了解決這一問題我決定佇列的最后一個空間用來作為結束條件，但是我又不希望傳過來的資料丟失一個，于是我直接在創建的時候多開一個空間來用于結束判斷，這樣就完美的解決了資料不少又能判斷佇列是否滿了的問題

首先我們需要一個回圈佇列的結構，我是這樣定義的如下：

typedef struct {
    int* a;
    int k;//佇列總大小
    int front;//隊頭
    int tail;//隊尾

} MyCircularQueue;

大概是這個樣子的：

我們來實作一個初始化函式MyCircularQueue* myCircularQueueCreate(int k);

MyCircularQueue* myCircularQueueCreate(int k) {
    //一個佇列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //初始化佇列
    //這里要多開一個空間用于判斷佇列是否滿了
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;

    //回傳佇列的地址
    return obj;
}

實作好了上面這個函式我們開始實作一個判斷佇列是否為空的函式bool myCircularQueueIsEmpty(MyCircularQueue* obj);和判斷佇列是否滿了的函式bool myCircularQueueIsFull(MyCircularQueue* obj);

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
    //如果front和tail相等說明是空的
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

    //隊尾的下一個坐標給tailNext;
    int tailNext = obj->tail + 1;

    //如果它和最后一個空間的坐標相等說明此時的佇列已經滿了
    if (tailNext == obj->k + 1)
    {
        //把它置為頭的坐標
        tailNext = 0;
    }

    return tailNext == obj->front;
}

有了這兩個函式我們就可以開始實作佇列的插入函式

根據上面的步驟我們可以很快的實作出插入函式

bool myCircularQueueEnQueue( MyCircularQueue* obj, int value) {

    //判斷是否滿了，如果滿了就不插入
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        //插入到tail位置，并自增
        obj->a[obj->tail] = value;
        obj->tail++;

        //用于防止越界，當tail大于k的時候，就置成0以此來完成回圈佇列
        obj->tail %= (obj->k + 1);

        return true;
    }
}

由于洗掉佇列的洗掉函式和插入類似這里就不一一贅述了，我相信你們看懂了插入的邏輯洗掉應該很簡單就能實作，

所有的代碼：

typedef struct {
    int* a;
    int k;//佇列總大小
    int front;//隊頭
    int tail;//隊尾

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    //一個佇列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //初始化佇列
    //這里要多開一個空間用于判斷佇列是否滿了
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;

    //回傳佇列的地址
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
    //如果front和tail相等說明是空的
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

    //隊尾的下一個坐標給tailNext;
    int tailNext = obj->tail + 1;

    //如果它和最后一個空間的坐標相等說明此時的佇列已經滿了
    if (tailNext == obj->k + 1)
    {
        //把它置為頭的坐標
        tailNext = 0;
    }

    return tailNext == obj->front;
}

bool myCircularQueueEnQueue( MyCircularQueue* obj, int value) {

    //判斷是否滿了，如果滿了就不插入
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        //插入到tail位置，并自增
        obj->a[obj->tail] = value;
        obj->tail++;

        //用于防止越界，當tail大于k的時候，就置成0以此來完成回圈佇列
        obj->tail %= (obj->k + 1);

        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    
    if ( myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        //每自增一次頭相當于出一個佇列的資料
        obj->front++;

        //用于防止越界，當front大于k時就置0，以此完成回圈佇列
        obj->front %= (obj->k + 1);

        return true;
    }

}

int myCircularQueueFront(MyCircularQueue* obj) {

    //判斷是否為空，如果為慷訓傳-1
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else//如果不為慷訓傳隊頭資料
    {
        return obj->a[obj->front];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {

    //如果佇列為慷訓傳-1
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }

    //tail是前一個才是最后一個資料
    int tailPrev = obj->tail - 1;

    //如果tailPrev等于-1說明此時的tail是0
    if (tailPrev == -1)
    {
        tailPrev = obj->k;
    }

    //回傳tailPrev的資料
    return obj->a[tailPrev];
}

void myCircularQueueFree(MyCircularQueue* obj) {

    //釋放佇列
    free(obj->a);
    free(obj);

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/