組實(shí)現(xiàn)循環(huán)隊(duì)列（Ring Buffer）)
LeetCode-Go 題解 622Design Circular Queue用數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列Ring Buffer【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 倉(cāng)庫(kù)中 622. Design Circular Queue 題目文檔 為核心完整講解循環(huán)隊(duì)列環(huán)形緩沖器 Ring Buffer的設(shè)計(jì)思路與 Go 語(yǔ)言實(shí)現(xiàn)。讀者將掌握MyCircularQueue六個(gè)核心 API 的底層原理、下標(biāo)取模的環(huán)繞技巧以及倉(cāng)庫(kù)內(nèi)配套源碼與單元測(cè)試的驗(yàn)證方法可直接在本地復(fù)現(xiàn) LeetCode 622 的滿分解法。題目要求LeetCode 622. Design Circular Queue循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)其操作基于FIFO先進(jìn)先出原則并且隊(duì)尾被連接回隊(duì)首形成一個(gè)環(huán)因此也被稱為環(huán)形緩沖器Ring Buffer。循環(huán)隊(duì)列最大的好處是能復(fù)用隊(duì)列前部已經(jīng)用過的空間在普通隊(duì)列中一旦隊(duì)列滿了就無法再插入下一個(gè)元素即使隊(duì)列頭部已經(jīng)騰出了空閑位置而循環(huán)隊(duì)列可以借助取模運(yùn)算讓隊(duì)尾指針繞回隊(duì)首把這些空間繼續(xù)用于存儲(chǔ)新值。API 定義需要實(shí)現(xiàn)MyCircularQueue類接口如下方法行為返回MyCircularQueue(k)構(gòu)造器初始化長(zhǎng)度為k的隊(duì)列對(duì)象實(shí)例Front()獲取隊(duì)首元素隊(duì)列為空時(shí)返回-1intRear()獲取隊(duì)尾元素隊(duì)列為空時(shí)返回-1intenQueue(value)向循環(huán)隊(duì)列插入一個(gè)元素成功插入返回truebooleandeQueue()從循環(huán)隊(duì)列刪除一個(gè)元素成功刪除返回truebooleanisEmpty()檢查隊(duì)列是否為空booleanisFull()檢查隊(duì)列是否已滿boolean約束條件1 k 1000隊(duì)列容量上限為 10000 value 1000元素取值非負(fù)最多進(jìn)行3000次enQueue、deQueue、Front、Rear、isEmpty、isFull調(diào)用。官方示例Input [MyCircularQueue, enQueue, enQueue, enQueue, enQueue, Rear, isFull, deQueue, enQueue, Rear] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 3, true, true, true, 4]對(duì)應(yīng)的逐步執(zhí)行過程MyCircularQueue myCircularQueue new MyCircularQueue(3); myCircularQueue.enQueue(1); // return True myCircularQueue.enQueue(2); // return True myCircularQueue.enQueue(3); // return True myCircularQueue.enQueue(4); // return False ← 容量為 3隊(duì)列已滿 myCircularQueue.Rear(); // return 3 myCircularQueue.isFull(); // return True myCircularQueue.deQueue(); // return True ← 彈出隊(duì)首 1 myCircularQueue.enQueue(4); // return True ← 復(fù)用騰出的空間 myCircularQueue.Rear(); // return 4Follow-up 追問題目額外要求能否在不使用內(nèi)置隊(duì)列的前提下解決本題答案是肯定的——本倉(cāng)庫(kù)的解法完全不依賴任何內(nèi)置隊(duì)列容器而是用定長(zhǎng)數(shù)組加雙指針手寫實(shí)現(xiàn)天然滿足該要求。解題思路數(shù)組 雙指針 下標(biāo)取模本倉(cāng)庫(kù) README 給出的解題思路非常明確設(shè)計(jì)一個(gè)環(huán)形隊(duì)列底層用數(shù)組實(shí)現(xiàn)。額外維護(hù) 4 個(gè)變量隊(duì)列的總?cè)萘縞ap、隊(duì)列當(dāng)前大小size、隊(duì)首下標(biāo)left、隊(duì)尾下標(biāo)right。每添加一個(gè)元素便維護(hù)left、right、size下標(biāo)需要對(duì)cap取余因?yàn)槌^cap大小之后需要循環(huán)存儲(chǔ)。其核心機(jī)制可以概括為三點(diǎn)定長(zhǎng)數(shù)組承載數(shù)據(jù)容量固定為k無論進(jìn)出多少元素內(nèi)存占用始終保持O(k)兩個(gè)游標(biāo)指針代替物理搬運(yùn)left指向隊(duì)首、right指向下一個(gè)可寫位置出隊(duì)/入隊(duì)只移動(dòng)指針不搬移數(shù)組元素取模實(shí)現(xiàn)環(huán)繞right (right 1) % cap、left (left 1) % cap讓指針在越界時(shí)自動(dòng)繞回?cái)?shù)組頭部形成邏輯上的環(huán)。判空、判滿則直接依賴size計(jì)數(shù)size 0為空size cap為滿。這樣避免了頭尾指針相遇無法區(qū)分空/滿這一經(jīng)典問題實(shí)現(xiàn)起來最直觀。完整源碼解析LeetCode-Go 的 Go 實(shí)現(xiàn)倉(cāng)庫(kù)中 622. Design Circular Queue.go 與題目文檔中的代碼一致全部操作均為O(1)時(shí)間復(fù)雜度。先看結(jié)構(gòu)體定義type MyCircularQueue struct { cap int size int queue []int left int right int }字段含義cap隊(duì)列總?cè)萘考礃?gòu)造時(shí)傳入的ksize當(dāng)前已存儲(chǔ)的元素個(gè)數(shù)用于判空/判滿queue底層定長(zhǎng)數(shù)組make([]int, k)left隊(duì)首元素的下標(biāo)Front直接讀它right下一個(gè)可寫入位置的下標(biāo)EnQueue寫它構(gòu)造器 Constructorfunc Constructor(k int) MyCircularQueue { return MyCircularQueue{cap: k, size: 0, left: 0, right: 0, queue: make([]int, k)} }一次性分配長(zhǎng)度為k的底層數(shù)組四個(gè)指針/計(jì)數(shù)全部初始化為0。對(duì)應(yīng)源碼見 Constructor 實(shí)現(xiàn)。入隊(duì) EnQueuefunc (this *MyCircularQueue) EnQueue(value int) bool { if this.size this.cap { return false } this.size this.queue[this.right] value this.right this.right % this.cap return true }入隊(duì)分四步先判滿size cap直接返回falsesize自增把value寫入right指向的位置right前進(jìn)并對(duì)cap取模實(shí)現(xiàn)環(huán)繞。例如容量為 3 時(shí)right從 2 走到 3 后3 % 3 0自動(dòng)回到數(shù)組頭部。對(duì)應(yīng)源碼見 EnQueue 實(shí)現(xiàn)。出隊(duì) DeQueuefunc (this *MyCircularQueue) DeQueue() bool { if this.size 0 { return false } this.size-- this.left this.left % this.cap return true }出隊(duì)同樣先判空size 0返回falsesize自減left前進(jìn)并取模。注意這里無需清空或搬移元素被彈出的位置會(huì)在后續(xù)入隊(duì)時(shí)被覆蓋寫入這正是環(huán)形緩沖復(fù)用空間的體現(xiàn)。對(duì)應(yīng)源碼見 DeQueue 實(shí)現(xiàn)。隊(duì)首 Frontfunc (this *MyCircularQueue) Front() int { if this.size 0 { return -1 } return this.queue[this.left] }隊(duì)列非空時(shí)直接返回this.queue[this.left]空隊(duì)列按題目約定返回-1。對(duì)應(yīng)源碼見 Front 實(shí)現(xiàn)。隊(duì)尾 Rearfunc (this *MyCircularQueue) Rear() int { if this.size 0 { return -1 } if this.right 0 { return this.queue[this.cap-1] } return this.queue[this.right-1] }Rear是本實(shí)現(xiàn)中唯一需要特殊分支的方法隊(duì)尾元素位于right - 1但當(dāng)right恰好取模回到0時(shí)right - 1為-1此時(shí)真正的隊(duì)尾在數(shù)組末尾queue[cap-1]。對(duì)應(yīng)源碼見 Rear 實(shí)現(xiàn)。判空與判滿func (this *MyCircularQueue) IsEmpty() bool { return this.size 0 } func (this *MyCircularQueue) IsFull() bool { return this.size this.cap }兩個(gè)方法都直接基于size計(jì)數(shù)判斷邏輯極簡(jiǎn)且無歧義。對(duì)應(yīng)源碼見 IsEmpty / IsFull 實(shí)現(xiàn)。復(fù)雜度分析時(shí)間復(fù)雜度構(gòu)造、入隊(duì)、出隊(duì)、取隊(duì)首、取隊(duì)尾、判空、判滿全部為O(1)空間復(fù)雜度O(k)僅存儲(chǔ)定長(zhǎng)數(shù)組和幾個(gè)標(biāo)量不隨調(diào)用次數(shù)增長(zhǎng)。官方示例逐步推演以容量k 3為例跟蹤left、right、size三個(gè)游標(biāo)的變化初始left0, right0, size0操作結(jié)果sizeleftright數(shù)組內(nèi)容僅展示有效區(qū)EnQueue(1)true101[1]EnQueue(2)true202[1, 2]EnQueue(3)true300[1, 2, 3]滿EnQueue(4)false300已滿拒絕Rear()3300走right 0分支讀queue[2]isFull()true300size capDeQueue()true210彈出隊(duì)首1EnQueue(4)true311復(fù)用下標(biāo) 0 的空間寫入4Rear()4311讀queue[0]可以看到第 8 步中right在寫入后由0前進(jìn)到1元素4恰好寫入之前被彈出的1所在的下標(biāo) 0 位置——這就是循環(huán)隊(duì)列利用隊(duì)列前面空間的直觀體現(xiàn)。倉(cāng)庫(kù)測(cè)試用例驗(yàn)證倉(cāng)庫(kù)在 622. Design Circular Queue_test.go 中提供了針對(duì)本題的單元測(cè)試覆蓋了若干關(guān)鍵邊界場(chǎng)景空隊(duì)列邊界對(duì)空隊(duì)列執(zhí)行DeQueue應(yīng)返回falseFront、Rear應(yīng)返回-1正常填充與判滿連續(xù)入隊(duì) 3 個(gè)元素后EnQueue(40)應(yīng)返回false隊(duì)首隊(duì)尾取值Front()返回最先入隊(duì)的10Rear()返回最后入隊(duì)的30環(huán)繞分支覆蓋先DeQueue騰出空間再EnQueue(40)讓right取模回到0隨后驗(yàn)證Rear()命中right 0分支返回40——該用例專門用于覆蓋Rear中與普通分支不同的取模回繞路徑。本地運(yùn)行測(cè)試倉(cāng)庫(kù)根目錄的 gotest.sh 使用如下命令一次性跑完所有題目并生成覆蓋率報(bào)告go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想驗(yàn)證本題可單獨(dú)執(zhí)行g(shù)o test -v ./leetcode/0622.Design-Circular-Queue/由于Test_Problem622中所有分支包括right 0的特例都被顯式斷言覆蓋該目錄的 Go 代碼在本倉(cāng)庫(kù)的測(cè)試體系中可達(dá)到完整的分支覆蓋。拓展環(huán)形緩沖區(qū)與工程實(shí)踐與倉(cāng)庫(kù)通用 Queue 的對(duì)比本倉(cāng)庫(kù)在 structures/Queue.go 中提供了一個(gè)通用的Queue結(jié)構(gòu)其實(shí)現(xiàn)是切片 append 頭部裁剪的普通隊(duì)列Push通過append追加到尾部Pop通過q.nums q.nums[1:]移除頭部元素。這種實(shí)現(xiàn)簡(jiǎn)單直接但存在兩點(diǎn)差異空間復(fù)用普通隊(duì)列每次Pop都會(huì)丟棄切片頭部無法回頭利用已彈出的空間而循環(huán)隊(duì)列通過指針回繞固定復(fù)用底層數(shù)組容量上限structures.Queue可隨append動(dòng)態(tài)擴(kuò)容而MyCircularQueue容量固定為k適合對(duì)內(nèi)存占用有硬性上限的場(chǎng)景。數(shù)組雙端實(shí)現(xiàn)的其他變體本題常見的另一種寫法是不維護(hù)size而是額外預(yù)留一個(gè)空位讓left指向隊(duì)首、right指向隊(duì)尾元素本身以(right 1) % cap left判滿、left right判空代價(jià)是容量為k的數(shù)組實(shí)際只能存儲(chǔ)k-1個(gè)元素。本倉(cāng)庫(kù)采用獨(dú)立的size計(jì)數(shù)器犧牲一個(gè)int的空間換取滿容量可用與更直觀的判斷邏輯是一種更實(shí)用的工程選擇。現(xiàn)實(shí)世界的 Ring Buffer循環(huán)隊(duì)列的工程原型環(huán)形緩沖區(qū)廣泛用于生產(chǎn)者-消費(fèi)者模型、內(nèi)核/驅(qū)動(dòng)中的 DMA 數(shù)據(jù)緩存、網(wǎng)絡(luò)收發(fā)緩沖、日志環(huán)形記錄等場(chǎng)景。其核心價(jià)值在于讀寫雙方只需各自維護(hù)一個(gè)游標(biāo)互不搬移數(shù)據(jù)就能在固定大小的內(nèi)存上以 O(1) 代價(jià)持續(xù)流轉(zhuǎn)數(shù)據(jù)。理解了本題的left/right取模回繞也就掌握了這一類工業(yè)級(jí)數(shù)據(jù)結(jié)構(gòu)的基本盤。小結(jié)LeetCode 622 是一道簡(jiǎn)單但經(jīng)典的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題。LeetCode-Go 倉(cāng)庫(kù)給出的解法用定長(zhǎng)數(shù)組 left/right雙游標(biāo) 對(duì)容量取模三件套實(shí)現(xiàn)了全部 O(1) 操作且不依賴任何內(nèi)置隊(duì)列正面回答了題目的 Follow-up。配合倉(cāng)庫(kù)內(nèi)針對(duì)空隊(duì)列、滿隊(duì)列、指針回繞分支的完整單測(cè)題目文檔、源碼實(shí)現(xiàn) 與 單元測(cè)試 三者互為印證可以作為理解環(huán)形緩沖區(qū)的首選參考資料。【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode-Go 題解 622：Design Circular Queue，用數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列（Ring Buffer）
LeetCode-Go 題解 622Design Circular Queue用數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列Ring Buffer【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 倉(cāng)庫(kù)中 622. Design Circular Queue 題目文檔 為核心完整講解循環(huán)隊(duì)列環(huán)形緩沖器 Ring Buffer的設(shè)計(jì)思路與 Go 語(yǔ)言實(shí)現(xiàn)。讀者將掌握MyCircularQueue六個(gè)核心 API 的底層原理、下標(biāo)取模的環(huán)繞技巧以及倉(cāng)庫(kù)內(nèi)配套源碼與單元測(cè)試的驗(yàn)證方法可直接在本地復(fù)現(xiàn) LeetCode 622 的滿分解法。題目要求LeetCode 622. Design Circular Queue循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)其操作基于FIFO先進(jìn)先出原則并且隊(duì)尾被連接回隊(duì)首形成一個(gè)環(huán)因此也被稱為環(huán)形緩沖器Ring Buffer。循環(huán)隊(duì)列最大的好處是能復(fù)用隊(duì)列前部已經(jīng)用過的空間在普通隊(duì)列中一旦隊(duì)列滿了就無法再插入下一個(gè)元素即使隊(duì)列頭部已經(jīng)騰出了空閑位置而循環(huán)隊(duì)列可以借助取模運(yùn)算讓隊(duì)尾指針繞回隊(duì)首把這些空間繼續(xù)用于存儲(chǔ)新值。API 定義需要實(shí)現(xiàn)MyCircularQueue類接口如下方法行為返回MyCircularQueue(k)構(gòu)造器初始化長(zhǎng)度為k的隊(duì)列對(duì)象實(shí)例Front()獲取隊(duì)首元素隊(duì)列為空時(shí)返回-1intRear()獲取隊(duì)尾元素隊(duì)列為空時(shí)返回-1intenQueue(value)向循環(huán)隊(duì)列插入一個(gè)元素成功插入返回truebooleandeQueue()從循環(huán)隊(duì)列刪除一個(gè)元素成功刪除返回truebooleanisEmpty()檢查隊(duì)列是否為空booleanisFull()檢查隊(duì)列是否已滿boolean約束條件1 k 1000隊(duì)列容量上限為 10000 value 1000元素取值非負(fù)最多進(jìn)行3000次enQueue、deQueue、Front、Rear、isEmpty、isFull調(diào)用。官方示例Input [MyCircularQueue, enQueue, enQueue, enQueue, enQueue, Rear, isFull, deQueue, enQueue, Rear] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 3, true, true, true, 4]對(duì)應(yīng)的逐步執(zhí)行過程MyCircularQueue myCircularQueue new MyCircularQueue(3); myCircularQueue.enQueue(1); // return True myCircularQueue.enQueue(2); // return True myCircularQueue.enQueue(3); // return True myCircularQueue.enQueue(4); // return False ← 容量為 3隊(duì)列已滿 myCircularQueue.Rear(); // return 3 myCircularQueue.isFull(); // return True myCircularQueue.deQueue(); // return True ← 彈出隊(duì)首 1 myCircularQueue.enQueue(4); // return True ← 復(fù)用騰出的空間 myCircularQueue.Rear(); // return 4Follow-up 追問題目額外要求能否在不使用內(nèi)置隊(duì)列的前提下解決本題答案是肯定的——本倉(cāng)庫(kù)的解法完全不依賴任何內(nèi)置隊(duì)列容器而是用定長(zhǎng)數(shù)組加雙指針手寫實(shí)現(xiàn)天然滿足該要求。解題思路數(shù)組 雙指針 下標(biāo)取模本倉(cāng)庫(kù) README 給出的解題思路非常明確設(shè)計(jì)一個(gè)環(huán)形隊(duì)列底層用數(shù)組實(shí)現(xiàn)。額外維護(hù) 4 個(gè)變量隊(duì)列的總?cè)萘縞ap、隊(duì)列當(dāng)前大小size、隊(duì)首下標(biāo)left、隊(duì)尾下標(biāo)right。每添加一個(gè)元素便維護(hù)left、right、size下標(biāo)需要對(duì)cap取余因?yàn)槌^cap大小之后需要循環(huán)存儲(chǔ)。其核心機(jī)制可以概括為三點(diǎn)定長(zhǎng)數(shù)組承載數(shù)據(jù)容量固定為k無論進(jìn)出多少元素內(nèi)存占用始終保持O(k)兩個(gè)游標(biāo)指針代替物理搬運(yùn)left指向隊(duì)首、right指向下一個(gè)可寫位置出隊(duì)/入隊(duì)只移動(dòng)指針不搬移數(shù)組元素取模實(shí)現(xiàn)環(huán)繞right (right 1) % cap、left (left 1) % cap讓指針在越界時(shí)自動(dòng)繞回?cái)?shù)組頭部形成邏輯上的環(huán)。判空、判滿則直接依賴size計(jì)數(shù)size 0為空size cap為滿。這樣避免了頭尾指針相遇無法區(qū)分空/滿這一經(jīng)典問題實(shí)現(xiàn)起來最直觀。完整源碼解析LeetCode-Go 的 Go 實(shí)現(xiàn)倉(cāng)庫(kù)中 622. Design Circular Queue.go 與題目文檔中的代碼一致全部操作均為O(1)時(shí)間復(fù)雜度。先看結(jié)構(gòu)體定義type MyCircularQueue struct { cap int size int queue []int left int right int }字段含義cap隊(duì)列總?cè)萘考礃?gòu)造時(shí)傳入的ksize當(dāng)前已存儲(chǔ)的元素個(gè)數(shù)用于判空/判滿queue底層定長(zhǎng)數(shù)組make([]int, k)left隊(duì)首元素的下標(biāo)Front直接讀它right下一個(gè)可寫入位置的下標(biāo)EnQueue寫它構(gòu)造器 Constructorfunc Constructor(k int) MyCircularQueue { return MyCircularQueue{cap: k, size: 0, left: 0, right: 0, queue: make([]int, k)} }一次性分配長(zhǎng)度為k的底層數(shù)組四個(gè)指針/計(jì)數(shù)全部初始化為0。對(duì)應(yīng)源碼見 Constructor 實(shí)現(xiàn)。入隊(duì) EnQueuefunc (this *MyCircularQueue) EnQueue(value int) bool { if this.size this.cap { return false } this.size this.queue[this.right] value this.right this.right % this.cap return true }入隊(duì)分四步先判滿size cap直接返回falsesize自增把value寫入right指向的位置right前進(jìn)并對(duì)cap取模實(shí)現(xiàn)環(huán)繞。例如容量為 3 時(shí)right從 2 走到 3 后3 % 3 0自動(dòng)回到數(shù)組頭部。對(duì)應(yīng)源碼見 EnQueue 實(shí)現(xiàn)。出隊(duì) DeQueuefunc (this *MyCircularQueue) DeQueue() bool { if this.size 0 { return false } this.size-- this.left this.left % this.cap return true }出隊(duì)同樣先判空size 0返回falsesize自減left前進(jìn)并取模。注意這里無需清空或搬移元素被彈出的位置會(huì)在后續(xù)入隊(duì)時(shí)被覆蓋寫入這正是環(huán)形緩沖復(fù)用空間的體現(xiàn)。對(duì)應(yīng)源碼見 DeQueue 實(shí)現(xiàn)。隊(duì)首 Frontfunc (this *MyCircularQueue) Front() int { if this.size 0 { return -1 } return this.queue[this.left] }隊(duì)列非空時(shí)直接返回this.queue[this.left]空隊(duì)列按題目約定返回-1。對(duì)應(yīng)源碼見 Front 實(shí)現(xiàn)。隊(duì)尾 Rearfunc (this *MyCircularQueue) Rear() int { if this.size 0 { return -1 } if this.right 0 { return this.queue[this.cap-1] } return this.queue[this.right-1] }Rear是本實(shí)現(xiàn)中唯一需要特殊分支的方法隊(duì)尾元素位于right - 1但當(dāng)right恰好取模回到0時(shí)right - 1為-1此時(shí)真正的隊(duì)尾在數(shù)組末尾queue[cap-1]。對(duì)應(yīng)源碼見 Rear 實(shí)現(xiàn)。判空與判滿func (this *MyCircularQueue) IsEmpty() bool { return this.size 0 } func (this *MyCircularQueue) IsFull() bool { return this.size this.cap }兩個(gè)方法都直接基于size計(jì)數(shù)判斷邏輯極簡(jiǎn)且無歧義。對(duì)應(yīng)源碼見 IsEmpty / IsFull 實(shí)現(xiàn)。復(fù)雜度分析時(shí)間復(fù)雜度構(gòu)造、入隊(duì)、出隊(duì)、取隊(duì)首、取隊(duì)尾、判空、判滿全部為O(1)空間復(fù)雜度O(k)僅存儲(chǔ)定長(zhǎng)數(shù)組和幾個(gè)標(biāo)量不隨調(diào)用次數(shù)增長(zhǎng)。官方示例逐步推演以容量k 3為例跟蹤left、right、size三個(gè)游標(biāo)的變化初始left0, right0, size0操作結(jié)果sizeleftright數(shù)組內(nèi)容僅展示有效區(qū)EnQueue(1)true101[1]EnQueue(2)true202[1, 2]EnQueue(3)true300[1, 2, 3]滿EnQueue(4)false300已滿拒絕Rear()3300走right 0分支讀queue[2]isFull()true300size capDeQueue()true210彈出隊(duì)首1EnQueue(4)true311復(fù)用下標(biāo) 0 的空間寫入4Rear()4311讀queue[0]可以看到第 8 步中right在寫入后由0前進(jìn)到1元素4恰好寫入之前被彈出的1所在的下標(biāo) 0 位置——這就是循環(huán)隊(duì)列利用隊(duì)列前面空間的直觀體現(xiàn)。倉(cāng)庫(kù)測(cè)試用例驗(yàn)證倉(cāng)庫(kù)在 622. Design Circular Queue_test.go 中提供了針對(duì)本題的單元測(cè)試覆蓋了若干關(guān)鍵邊界場(chǎng)景空隊(duì)列邊界對(duì)空隊(duì)列執(zhí)行DeQueue應(yīng)返回falseFront、Rear應(yīng)返回-1正常填充與判滿連續(xù)入隊(duì) 3 個(gè)元素后EnQueue(40)應(yīng)返回false隊(duì)首隊(duì)尾取值Front()返回最先入隊(duì)的10Rear()返回最后入隊(duì)的30環(huán)繞分支覆蓋先DeQueue騰出空間再EnQueue(40)讓right取模回到0隨后驗(yàn)證Rear()命中right 0分支返回40——該用例專門用于覆蓋Rear中與普通分支不同的取模回繞路徑。本地運(yùn)行測(cè)試倉(cāng)庫(kù)根目錄的 gotest.sh 使用如下命令一次性跑完所有題目并生成覆蓋率報(bào)告go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想驗(yàn)證本題可單獨(dú)執(zhí)行g(shù)o test -v ./leetcode/0622.Design-Circular-Queue/由于Test_Problem622中所有分支包括right 0的特例都被顯式斷言覆蓋該目錄的 Go 代碼在本倉(cāng)庫(kù)的測(cè)試體系中可達(dá)到完整的分支覆蓋。拓展環(huán)形緩沖區(qū)與工程實(shí)踐與倉(cāng)庫(kù)通用 Queue 的對(duì)比本倉(cāng)庫(kù)在 structures/Queue.go 中提供了一個(gè)通用的Queue結(jié)構(gòu)其實(shí)現(xiàn)是切片 append 頭部裁剪的普通隊(duì)列Push通過append追加到尾部Pop通過q.nums q.nums[1:]移除頭部元素。這種實(shí)現(xiàn)簡(jiǎn)單直接但存在兩點(diǎn)差異空間復(fù)用普通隊(duì)列每次Pop都會(huì)丟棄切片頭部無法回頭利用已彈出的空間而循環(huán)隊(duì)列通過指針回繞固定復(fù)用底層數(shù)組容量上限structures.Queue可隨append動(dòng)態(tài)擴(kuò)容而MyCircularQueue容量固定為k適合對(duì)內(nèi)存占用有硬性上限的場(chǎng)景。數(shù)組雙端實(shí)現(xiàn)的其他變體本題常見的另一種寫法是不維護(hù)size而是額外預(yù)留一個(gè)空位讓left指向隊(duì)首、right指向隊(duì)尾元素本身以(right 1) % cap left判滿、left right判空代價(jià)是容量為k的數(shù)組實(shí)際只能存儲(chǔ)k-1個(gè)元素。本倉(cāng)庫(kù)采用獨(dú)立的size計(jì)數(shù)器犧牲一個(gè)int的空間換取滿容量可用與更直觀的判斷邏輯是一種更實(shí)用的工程選擇。現(xiàn)實(shí)世界的 Ring Buffer循環(huán)隊(duì)列的工程原型環(huán)形緩沖區(qū)廣泛用于生產(chǎn)者-消費(fèi)者模型、內(nèi)核/驅(qū)動(dòng)中的 DMA 數(shù)據(jù)緩存、網(wǎng)絡(luò)收發(fā)緩沖、日志環(huán)形記錄等場(chǎng)景。其核心價(jià)值在于讀寫雙方只需各自維護(hù)一個(gè)游標(biāo)互不搬移數(shù)據(jù)就能在固定大小的內(nèi)存上以 O(1) 代價(jià)持續(xù)流轉(zhuǎn)數(shù)據(jù)。理解了本題的left/right取模回繞也就掌握了這一類工業(yè)級(jí)數(shù)據(jù)結(jié)構(gòu)的基本盤。小結(jié)LeetCode 622 是一道簡(jiǎn)單但經(jīng)典的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題。LeetCode-Go 倉(cāng)庫(kù)給出的解法用定長(zhǎng)數(shù)組 left/right雙游標(biāo) 對(duì)容量取模三件套實(shí)現(xiàn)了全部 O(1) 操作且不依賴任何內(nèi)置隊(duì)列正面回答了題目的 Follow-up。配合倉(cāng)庫(kù)內(nèi)針對(duì)空隊(duì)列、滿隊(duì)列、指針回繞分支的完整單測(cè)題目文檔、源碼實(shí)現(xiàn) 與 單元測(cè)試 三者互為印證可以作為理解環(huán)形緩沖區(qū)的首選參考資料。【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考