golang環(huán)形隊列實現(xiàn)代碼示例
Summary
- 什么是環(huán)形隊列
- 實現(xiàn)環(huán)形隊列圖示過程
- golang版本代碼實現(xiàn)過程
- 參考全部代碼
什么是環(huán)形隊列
在一個指定大小的數(shù)組里循環(huán)寫入數(shù)據(jù),借用二個指針分別實現(xiàn)入隊標記與出隊標記.也體現(xiàn)了指針的大好用處,請深入體會.大有裨益.
如圖所示,一個環(huán)形隊列.含有二個指針: 隊列頭指針,隊列尾指針.
實現(xiàn)環(huán)形隊列圖示過程
初始化一個數(shù)組大小為6的環(huán)形隊列, 頭指針front=0, 尾指針rear=0, 剛好front=rear =0的狀態(tài),表示環(huán)形隊列為空.
2.向環(huán)形隊列里插入1個元素,則rear指針移動一格,front=0,rear=1
3.繼續(xù)添加a2,a3,a4,a5元素,rear指針指到末尾處,front=0, reat=5
4.如果再繼續(xù)添加a6元素,則rear=6,大于數(shù)組大小,發(fā)生數(shù)組溢出.
5.如上圖所示添加a6時,rear指針發(fā)生溢出.我們使用一個小技巧,當rear=6時與數(shù)組大小6進行取模, (rear+1) % maxLen,讓rear指針回到開始處rear=0,問題來了,我們無法判斷數(shù)組是否滿?因為初始化時front=rear=0, 現(xiàn)在數(shù)組滿也是front=rear=0
6.解決以上問題有三種辦法,我們采用第3種方法實現(xiàn).
使用第3種方法: 即當(rear+1) % maxLen == front時,判斷環(huán)形數(shù)組滿,則無法添加元素
golang版代碼實現(xiàn)過程
a. 定義環(huán)形數(shù)據(jù)結(jié)構(gòu)
type CycleQueue struct {
data []interface{} //存儲空間
front int //前指針,前指針負責彈出數(shù)據(jù)移動
rear int //尾指針,后指針負責添加數(shù)據(jù)移動
cap int //設(shè)置切片最大容量
}
b.初始化環(huán)形隊列
func NewCycleQueue(cap int) *CycleQueue {
return &CycleQueue{
data: make([]interface{}, cap),
cap: cap,
front: 0,
rear: 0,
}
}
c. 入隊操作
//入隊操作
//判斷隊列是否隊滿,隊滿則不允許添加數(shù)據(jù)
func (q *CycleQueue) Push(data interface{}) bool {
//check queue is full
if (q.rear+1)%q.cap == q.front { //隊列已滿時，不執(zhí)行入隊操作
return false
}
q.data[q.rear] = data //將元素放入隊列尾部
q.rear = (q.rear + 1) % q.cap //尾部元素指向下一個空間位置,取模運算保證了索引不越界（余數(shù)一定小于除數(shù)）
return true
}
d.出隊操作
//出隊操作
//需要考慮: 隊隊為空沒有數(shù)據(jù)返回了
func (q *CycleQueue) Pop() interface{} {
if q.rear == q.front {
return nil
}
data := q.data[q.front]
q.data[q.front] = nil
q.front = (q.front + 1) % q.cap
return data
}
e:求當前的環(huán)形隊列長度
//因為是循環(huán)隊列, 后指針減去前指針 加上最大值, 然后與最大值 取余
func (q *CycleQueue) QueueLength() int {
return (q.rear - q.front + q.cap) % q.cap
}
參考全部代碼
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本文主要介紹了淺談GO中的Channel以及死鎖的造成，文中根據(jù)實例編碼詳細介紹的十分詳盡，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
Go語言切片前或中間插入項與內(nèi)置copy()函數(shù)詳解
這篇文章主要介紹了Go語言切片前或中間插入項與內(nèi)置copy()函數(shù)詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
在Go語言中，將interface設(shè)計為引用類型是為了實現(xiàn)更靈活、更動態(tài)的類型系統(tǒng)，這篇文章主要介紹了深度解析Golang中為什么interface是引用類型,需要的朋友可以參考下2024-01-01
在Go語言中，切片作為一種引用類型數(shù)據(jù)，相對數(shù)組而言是一種動態(tài)長度的數(shù)據(jù)類型，使用的場景也是非常多，所以本文主要來和大家聊聊切片的底層原理，需要的可以參考一下2023-06-06
這篇文章主要為大家介紹了Go?Java?算法之字符串解碼示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
這篇文章主要介紹了創(chuàng)建Go工程化項目布局詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
golang分配內(nèi)存主要有內(nèi)置函數(shù)new和make,下面這篇文章主要給大家介紹了關(guān)于go中make用法及常見的一些坑,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2022-12-12
參數(shù)傳遞是指在程序的傳遞過程中,實際參數(shù)就會將參數(shù)值傳遞給相應的形式參數(shù),然后在函數(shù)中實現(xiàn)對數(shù)據(jù)處理和返回的過程，下面這篇文章主要給大家介紹了關(guān)于Golang中參數(shù)傳遞的相關(guān)資料，需要的朋友可以參考下。2017-09-09
這篇文章主要介紹了go等待一組協(xié)程結(jié)束的操作方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05
Golang 實現(xiàn)分片讀取http超大文件流和并發(fā)控制
這篇文章主要介紹了Golang 實現(xiàn)分片讀取http超大文件流和并發(fā)控制，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12