目錄
思考
一，循環(huán)隊(duì)列的初始化myCircularQueueCreate
二，判斷是否為空myCircularQueueIsEmpty
三，判斷隊(duì)列是否滿了bool myCircularQueueIsFull
四，隊(duì)列的插入myCircularQueueEnQueue
五，隊(duì)列的刪除myCircularQueueDeQueue
六，隊(duì)列取頭元素和尾元素myCircularQueueFront? ?//? ?myCircularQueueRear
七，銷毀隊(duì)列myCircularQueueFree
本題要點(diǎn)
完整答案
一般我們?nèi)胧值?span style="color:#fe2c24;">隊(duì)列都是單項(xiàng)不循環(huán)的，所以我們會(huì)更傾向于選擇用鏈表來實(shí)現(xiàn)，并且會(huì)選擇單鏈表來簡(jiǎn)化隊(duì)列先入先出的規(guī)則，但是這個(gè)題可能會(huì)顛覆你的認(rèn)知。
我們?cè)賮砜纯碿hargpt3.5給出的循環(huán)隊(duì)列的演示圖（足夠細(xì)致了）：
思考
這個(gè)題要我們從0開始實(shí)現(xiàn)循環(huán)隊(duì)列，那再用單鏈表就不太可能了，因?yàn)檠h(huán)不了嘛。這個(gè)時(shí)候腦洞比較大的人比如我，就會(huì)想到很早做過的約瑟夫環(huán)，單項(xiàng)循環(huán)鏈表，帶不帶頭無所謂的（帶頭反而浪費(fèi)空間）。
方案一：用單項(xiàng)循環(huán)鏈表。
可不可行呢，是循環(huán)了，但是不知道你們有沒有注意到函數(shù)的接口有一個(gè)Rear(獲取隊(duì)尾元素)，單項(xiàng)的鏈表獲取隊(duì)尾元素是不是比較困難，還不如雙向循環(huán)鏈表。
那可不可以換成用雙向循環(huán)鏈表來彌補(bǔ)單項(xiàng)的不足呢！
方案二：用雙向循環(huán)鏈表
可以是解決了取為難的問題，但是鏈表的結(jié)點(diǎn)是不是要一個(gè)一個(gè)創(chuàng)建再連接起來，連成k個(gè)，那鏈表實(shí)現(xiàn)的困難就是初始化困難很多，需要前后鏈接。再者，如果用鏈表來實(shí)現(xiàn)也不好判斷到底這個(gè)隊(duì)列是空的還是滿的，因?yàn)檠h(huán)了嘛。
方案三：用數(shù)組
在我們的眾多討論之下，選擇了用數(shù)組來實(shí)現(xiàn)，優(yōu)勢(shì)1：數(shù)組的數(shù)據(jù)是連續(xù)的（參考順序表），不需要去一個(gè)一個(gè)鏈接。優(yōu)勢(shì)2：處理起來更簡(jiǎn)單，增刪改等操作都簡(jiǎn)單。
然后我們用類似之前雙指針的思路，設(shè)置一個(gè)Front為數(shù)組的開頭元素的序號(hào)，一個(gè)Rear為數(shù)組的結(jié)尾元素的序號(hào)，來判斷數(shù)組是否空和滿，但是這個(gè)Rear應(yīng)該指向尾元素的下一個(gè)位置來。
因?yàn)椋绻鸕ear不指向下一個(gè)元素那么當(dāng)隊(duì)列只有有一個(gè)元素的情況下Rear和Front的值是相同的，沒有元素的情況下（初始化）也是相同的。就無法判斷了。
我們選定了方法，也有了思路，那就來實(shí)現(xiàn)一下這個(gè)題：
一，循環(huán)隊(duì)列的初始化myCircularQueueCreate
這里說一下為什么要多創(chuàng)造一個(gè)空間，主要是來好判斷隊(duì)列滿了的情況，后面會(huì)解釋的。
為什么obj也要?jiǎng)?chuàng)建一個(gè)空間呢，我們直接在實(shí)現(xiàn)順序表時(shí)都沒有這樣操作呀，那是因?yàn)橛捎趏bj這個(gè)結(jié)構(gòu)體是在創(chuàng)建函數(shù)之外創(chuàng)建的，這個(gè)函數(shù)的參數(shù)沒有這個(gè)結(jié)構(gòu)體，也就是說這個(gè)obj是創(chuàng)建在棧區(qū)了，出了函數(shù)就銷毀了，malloc是重新創(chuàng)建在堆區(qū)的，只要程序不結(jié)束就不會(huì)消失，所以就要重新創(chuàng)建空間。所以如果直接寫：
MyCircularQueue obj;? ? //……? ?//? return &obj;，這樣obj作為函數(shù)里的臨時(shí)變量，出函數(shù)就被銷毀了，取地址再返回也是不行的?。?！
二，判斷是否為空myCircularQueueIsEmpty
紅色的為空出來的空間，也就是多創(chuàng)建的空間，如圖其實(shí)不難發(fā)現(xiàn)不管是有元素還是沒有元素，rear循環(huán)了還是沒有循環(huán)，rear+1都==front。
三，判斷隊(duì)列是否滿了bool myCircularQueueIsFull
這里解釋一下為什么要多開辟一個(gè)空間來解決偽充滿的問題?。?！
如圖，當(dāng)rear的值增大到6時(shí)由于要循環(huán)，所以rear%k = 0，為了讓數(shù)組循環(huán)起來，%數(shù)組的大小是最好的選擇，此時(shí)如果（rear + 1）% k = 1，這樣永遠(yuǎn)都不會(huì)等于front，無法判斷，如果rear不加上1直接去%，那么rear%k = 0 = front這樣無法判斷隊(duì)列是空的還是滿的。
如果不讓rear指向尾元素的下一個(gè)，直接指向尾元素，這樣的話，當(dāng)rear等于5時(shí)，最后一個(gè)數(shù)據(jù)進(jìn)入隊(duì)列，這樣手動(dòng)將rear+1 = 6，（rear + 1）% k = 0 = front；但是如果在進(jìn)數(shù)據(jù)時(shí)有數(shù)據(jù)被取出，那front就不是等于0，有可能等于1，2……這樣，front和rear依然不相等呀。
所以，多創(chuàng)建一個(gè)空間就是最好的選擇：由圖可知：rear+1 == front，由于在不循環(huán)的情況時(shí)，rear+1一定不會(huì)大于k+1的所以%（k+1）也不會(huì)影響不循環(huán)的情況的，循環(huán)時(shí)為了防止rear一直加后越界，所以要%（k+1），這就是數(shù)組循環(huán)的條件！
四，隊(duì)列的插入myCircularQueueEnQueue
插入時(shí)需要先判斷隊(duì)列是否為滿的情況。
如果rear此時(shí)等于k時(shí)，如果前面沒有足夠的空位，那就需要考慮循環(huán)的問題就要%（k+1），不然就會(huì)越界訪問。如果沒有循環(huán)的問題那只需要插入在rear的位置就行，這個(gè)空格會(huì)一直出現(xiàn)在front的后面用以判斷是否滿了，空格就是多出來的空間。
五，隊(duì)列的刪除myCircularQueueDeQueue
刪除則要考慮隊(duì)列是否為空。剩下的思路和上面的插入差不多?。?！
六，隊(duì)列取頭元素和尾元素myCircularQueueFront? ?//? ?myCircularQueueRear
取頭尾元素都要先考慮隊(duì)列是否為空，但是由于取頭元素只要a[obj->Front]，因?yàn)閒ront沒有什么變化，都對(duì)應(yīng)著要取的數(shù)，那取尾會(huì)不會(huì)一樣呢？
細(xì)心的你當(dāng)然會(huì)發(fā)現(xiàn)肯定不是，如果沒有循環(huán)是這樣沒錯(cuò)，但是如果rear循環(huán)就不一樣了。
如圖，如果rear循環(huán)，那正常rear-1就是尾，但是如果rear=0，那rear+1=-1，所以需要加上一個(gè)隊(duì)列的大?。╧+1）使其轉(zhuǎn)正后再%（k+1），%（k+1）是為了防止rear越界，即使是不循環(huán)或者循環(huán)且rear不等于0的情況，加上一個(gè)隊(duì)列的大小再%這個(gè)隊(duì)列的大小值也是不變的。上圖的算數(shù)式可以更好的證明?。?！
七，銷毀隊(duì)列myCircularQueueFree
為什么不直接free(obj)呢？
分析obj的結(jié)構(gòu)可得，因?yàn)閛bj這個(gè)結(jié)構(gòu)體里面有a數(shù)組，如果直接free(obj)，是只把obj所占的空間銷毀了，但是里面的a數(shù)組的空間沒有被銷毀。
本題要點(diǎn)
本題主要是對(duì)于rear和front在移動(dòng)時(shí)會(huì)不會(huì)越界的判斷，和循環(huán)數(shù)組的處理方式(%(k+1))，rear-1越界的處理方式(+(k+1))，還需要更細(xì)致的判斷能力和理解循環(huán)隊(duì)列的循環(huán)結(jié)構(gòu)。難度中等實(shí)至名歸。
完整答案
這樣本題就解析+解答結(jié)束。下面為完整的解答過程。
typedef struct {
? ? int Front;
? ? int Rear;
? ? int* a;
? ? int capacity;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
? ? MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
? ? obj->Front = 0;
? ? obj->Rear = 0;
? ? obj->capacity = k + 1;
? ? obj->a = (int*)malloc(sizeof(int) * obj->capacity);
? ? return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
? ? if ((obj->Rear+1) % obj->capacity == obj->Front)
? ? {
? ? ? ? return false;
? ? }
? ? else
? ? {
? ? ? ? obj->a[obj->Rear] = value;
? ? ? ? obj->Rear = obj->Rear+1;
? ? ? ? obj->Rear = obj->Rear % obj->capacity;
? ? ? ? return true;
? ? }
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
? ? if (obj->Rear == obj->Front) {
? ? ? ? return false;
? ? }
? ? obj->Front = (obj->Front + 1) % obj->capacity;
? ? return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
? ? if (obj->Rear == obj->Front) {
? ? ? ? return -1;
? ? }
? ? return obj->a[obj->Front];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
? ? if (obj->Rear == obj->Front)
? ? {
? ? ? ? return -1;
? ? }
? ? else
? ? {
? ? ? ? return obj->a[(obj->Rear-1 + obj->capacity) % obj->capacity];
? ? }
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
? ? return obj->Rear == obj->Front;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
? ? return (obj->Rear+1) % obj->capacity == obj->Front;
}
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);文章來源：http://www.zghlxwxcb.cn/news/detail-839108.html
*/文章來源地址http://www.zghlxwxcb.cn/news/detail-839108.html
到了這里，關(guān)于力扣622：設(shè)計(jì)循環(huán)隊(duì)列（中等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
