今天我們一起來做一道關于隊列的OJ題目，這是力扣題目622題，點擊題目鏈接可以直接跳轉，https://leetcode.cn/problems/design-circular-queue/

首先，我們看到要求，需要我們實現哪些功能？?

?我們需要設置隊列長度K，隊首元素，隊尾元素，插入元素，刪除元素，判斷空，判斷滿。那這么多接口，我們要從哪里入手呢？我們現在做題無外乎要么用順序表的方式，要么用鏈表的方式，使用兩者其實都可以，今天我們就用順序表的方式實現吧。既然使用順序表也就是數組，那么我們要考慮一點，在什么情況下這個隊列為空？要確定這個循環隊列為空，那就需要保證，頭元素的下標和尾元素的下標相等才可以，假設我們設頭元素下標為front，back為尾元素下一個位置，因為我們要區分back=0時，到底是有一個元素還是沒有元素的情況。即要保證front=back時，隊列為空。

考慮了隊列為空的情況，那什么時候循環隊列滿了呢？滿了就是已經不能再放其它元素，也就是尾位置，back就要追上front了，也就是back=front嗎？那我們想一想，隊列為空的時候和隊列為滿的時候，都是front=back，我們要怎么區分這兩種情況呢？

我們不妨設置隊列長度K的時候多開一個空間，即k+1,我們保證k+1個空間最多只使用k個，留出一個位置，讓back+1=front時為滿隊列。這樣就能區分隊列滿和隊列空的情況了。

下來我們開始做題。

typedef struct {int *a;//數組int front;//隊首元素下標int back;//隊尾元素下標的下一個位置int k;//隊列大小
} MyCircularQueue;

我們定義完結構體變量下來需要對結構題的成員初始化，即

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

為什么我們要給開k+1個空間呢？原因我們在上面講過了，就是為了讓隊列滿的情況時back+1=front。

下來我們先把容易實現的接口先完成，先把什么時候為空，什么時候為滿實現。

為空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->back;
}

為滿

bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->back+1=obj->front;//這樣做合適嗎？
}

?我們要考慮到，這是一個循環隊列，下面這種情況能滿足嗎？

back要一直往后走嗎？?顯然不是，這是一個循環隊列，當back走到k時，下一次就要回到起點，那怎么表示呢？我們不妨這樣表示，(obj->back+1)%(obj->k+1)==obj->front，這個隊列一共有k+1個空間，我們知道，如果一個小的數%一個比自己大的數是不會改變值的，所以，如果back+1=k+1,此時，back就要回到起點了。所以判斷隊列滿我們可以這樣寫

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1)%(obj->k+1)==obj->front;
}

?下面我們寫插入接口

這是一個bool類型，也就是要返回true和false,那什么時候要返回false呢？注意這是往隊列插入元素，如果隊列已經滿了，我們就插不了元素了。剩下就可以正常插入了，直接讓obj->a[obj->back]=value即可，再讓obj->back++。注意到這里，我們還要需要檢查back有沒有超過隊列空間的大小，即我們需要在后面讓obj->back%=obj->k+1;即

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj->back++;obj->back=(obj->back)%(obj->k+1);return true;
}

隊列刪除

刪除接口同樣是bool類型，我們要判斷什么時候刪除失敗？當然就是隊列為空的時候刪除失敗，我們要先檢查隊列是否為空，再刪除，刪除非常簡單，直接讓front++就可以了，front一直在++,有沒有可能front也會超出隊列的空間大小？當然有可能，所以我們也需要對front檢查一下，即obj->front%=obj->k+1;

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj->front++;obj->front=(obj->front)%(obj->k+1);return true;
}

下面就是返回對頭元素

題目里說了，如果隊列為空就返回-1，這種情況我們也要處理一下，其余就直接返回obj->a[obj->front]即可。

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

?隊尾元素

同樣我們也要處理一次隊列為空返回-1的情況，然后直接返回obj->a[obj->back-1]可以嗎？

我們思考一下，如果back=0呢？我說的不是隊列為空時，因為為空時我們已經處理了，我說的時當back已經走了至少一輪重新回到起點的情況，此時的back-1就成-1了，那我們怎么處理呢？我們要知道，這種情況下的back時已經被取模了k+1后，那我們不妨可以給back-1+k+1再給它取模k+1;即(obj->back-1)+(obj->k+1)%(obj->k+1);怎么理解這個公式，還是那句話，back-1不可能大于k+1，一個數%比他小的數值不變，(a+b)%b,如果a比b小且a是正數，那這個值是不變的，這一種情況也就對應了我們此處back!=0的情況，如果back=0,尾元素就在k的位置，那back-1就是-1，他再加上k+1再%k+1要比k+1小，所以結果就是k那個位置。

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
}

到這里這道題就大功告成了，此時我們運行，報了一個這樣錯誤

是因為，我們在前面調用了就很多次隊列為空為滿的情況，也沒有聲明，所以我們可以把判斷隊列為空，為滿挪到插入接口前面就可以啦。

好啦，本次題目就到這里了，希望大家能夠多多支持，我們下次再見！