1.學習內容：

今天 我們講解一道能夠很好的總結所學隊列知識的題目---設計循環隊列

?622. 設計循環隊列 - 力扣（LeetCode）

?2.題目描述：

讓我們設計一個隊列? 要求是循環的 這和我們的雙向鏈表有些類似

讓我們按要求設計出這些相對應函數?

此題目特殊之處在于 “滿了就不能再插入”，“循環如何判斷滿和空”圈起來后面要用到

?

3. 題目思路：

為了解決以上問題 我們要先設計我們的解題思路

設計循環隊列，那我們是選擇用數組處理還是選擇用鏈表處理呢？ 為什么？

?先給答案：? 建議用數組?

為什么：? 首先我們用front指向頭? back指向隊尾的下一個 使用鏈表確實可以在判斷為空為滿部分很快捷 我們只需要判斷back->next 是否等于 front即可 但是唯獨在取隊尾時不方便 這時候我們可以選擇采用雙向鏈表 或者增加一個back->prev的指針來表示上一個 但哪怕是采用雙向鏈表 對于我們來說依舊不是很友好 我們還需要新建節點 釋放等等 在難度上和數組大差不差 所以我們還是選擇數組來解決

?首先，我們要解決一開始提到的問題------“滿了就不能再插入”，“循環如何判斷滿和空”

?我們有兩種解決方案

先上示意圖

1.? 采用size? 新增加一個size? size==0時 也就是front==back為空? size != 0 就是滿

?2.采用新開辟一個空間 因為我們使back指向隊尾的下一個 所以每次賦值后++back??

所以當? （back+1）% (k+1) == front 時就是滿的情況 黃色位置就表示插入滿后back的指向

此時就可以完美解決無法判斷滿和空的區別

?

?

?

?接下來我們解決其他函數：插入和刪除

首先進行插入判斷： 為空不能插入 返回false? ?back指向下一個位置++??

核心：? 當我的back小于我開辟的k+1個空間時 怎么%取的都是back的下標

但當他滿了的時候 需要讓他的下標重新返回0? 所以?obj->back %= (obj->k+1);是專門為返回原下標也就是他滿了的時候準備的 同理 front也一樣 不進行二次贅述

第三重點：返回rear

?有兩種表示方法 上面的很好理解 就是back為空或者滿直接返回隊尾元素

重點是下面的

這個表示相當于在原先back滿了要循環的情況下? 不進行循環 直接在后面添加

也就是back為0的情況下? ? ? ?當back為0? back-1就代表數組下標越界?

這個時候為他加上我的空間長度 k+1? 再%k+1? ? 就可以返回任意情況 包括front不在第一位

因為如果back沒滿時? ? ?back-1? %? ?k+1? ?就會直接返回back-1?

而? ?back == 0? ? ? k+1就發揮作用了? ??

以上就是本題的大致講解 下面將附下全代碼僅供參考