golang環(huán)形隊(duì)列實(shí)現(xiàn)代碼示例
Summary
- 什么是環(huán)形隊(duì)列
- 實(shí)現(xiàn)環(huán)形隊(duì)列圖示過程
- golang版本代碼實(shí)現(xiàn)過程
- 參考全部代碼
什么是環(huán)形隊(duì)列
在一個(gè)指定大小的數(shù)組里循環(huán)寫入數(shù)據(jù),借用二個(gè)指針分別實(shí)現(xiàn)入隊(duì)標(biāo)記與出隊(duì)標(biāo)記.也體現(xiàn)了指針的大好用處,請深入體會.大有裨益.
如圖所示,一個(gè)環(huán)形隊(duì)列.含有二個(gè)指針: 隊(duì)列頭指針,隊(duì)列尾指針.
實(shí)現(xiàn)環(huán)形隊(duì)列圖示過程
初始化一個(gè)數(shù)組大小為6的環(huán)形隊(duì)列, 頭指針front=0, 尾指針rear=0, 剛好front=rear =0的狀態(tài),表示環(huán)形隊(duì)列為空.
2.向環(huán)形隊(duì)列里插入1個(gè)元素,則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時(shí),rear指針發(fā)生溢出.我們使用一個(gè)小技巧,當(dāng)rear=6時(shí)與數(shù)組大小6進(jìn)行取模, (rear+1) % maxLen,讓rear指針回到開始處rear=0,問題來了,我們無法判斷數(shù)組是否滿?因?yàn)槌跏蓟瘯r(shí)front=rear=0, 現(xiàn)在數(shù)組滿也是front=rear=0
6.解決以上問題有三種辦法,我們采用第3種方法實(shí)現(xiàn).
使用第3種方法: 即當(dāng)(rear+1) % maxLen == front時(shí),判斷環(huán)形數(shù)組滿,則無法添加元素
golang版代碼實(shí)現(xiàn)過程
a. 定義環(huán)形數(shù)據(jù)結(jié)構(gòu)
type CycleQueue struct {
data []interface{} //存儲空間
front int //前指針,前指針負(fù)責(zé)彈出數(shù)據(jù)移動
rear int //尾指針,后指針負(fù)責(zé)添加數(shù)據(jù)移動
cap int //設(shè)置切片最大容量
}
b.初始化環(huán)形隊(duì)列
func NewCycleQueue(cap int) *CycleQueue {
return &CycleQueue{
data: make([]interface{}, cap),
cap: cap,
front: 0,
rear: 0,
}
}
c. 入隊(duì)操作
//入隊(duì)操作
//判斷隊(duì)列是否隊(duì)滿,隊(duì)滿則不允許添加數(shù)據(jù)
func (q *CycleQueue) Push(data interface{}) bool {
//check queue is full
if (q.rear+1)%q.cap == q.front { //隊(duì)列已滿時(shí)，不執(zhí)行入隊(duì)操作
return false
}
q.data[q.rear] = data //將元素放入隊(duì)列尾部
q.rear = (q.rear + 1) % q.cap //尾部元素指向下一個(gè)空間位置,取模運(yùn)算保證了索引不越界（余數(shù)一定小于除數(shù)）
return true
}
d.出隊(duì)操作
//出隊(duì)操作
//需要考慮: 隊(duì)隊(duì)為空沒有數(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:求當(dāng)前的環(huán)形隊(duì)列長度
//因?yàn)槭茄h(huán)隊(duì)列, 后指針減去前指針 加上最大值, 然后與最大值 取余
func (q *CycleQueue) QueueLength() int {
return (q.rear - q.front + q.cap) % q.cap
}
參考全部代碼
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
SingleFlight模式的Go并發(fā)編程學(xué)習(xí)
這篇文章主要為大家介紹了SingleFlight模式的Go并發(fā)編程學(xué)習(xí)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-04-04
在Golang中，互斥鎖是一種基本的同步原語，用于實(shí)現(xiàn)對共享資源的互斥訪問，讀寫互斥鎖是一種特殊類型的互斥鎖，它允許多個(gè)協(xié)程同時(shí)讀取某個(gè)共享資源，本文將通過過示例代碼詳細(xì)介紹Golang中互斥鎖和讀寫互斥鎖,需要的朋友可以參考下2023-05-05
golang?channel多協(xié)程通信常用方法底層原理全面解析
channel?是?goroutine?與?goroutine?之間通信的重要橋梁,借助?channel,我們能很輕易的寫出一個(gè)多協(xié)程通信程序,今天,我們就來看看這個(gè)?channel?的常用用法以及底層原理2023-09-09
本文主要介紹了Golang有類型常量和無類型常量的區(qū)別，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
這篇文章主要介紹了Goland的設(shè)置與配置全過程，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要為大家詳細(xì)介紹了Go語言中的方法集合與選擇receiver類型的相關(guān)知識,文中的示例代碼講解詳細(xì),對我們深入學(xué)習(xí)go語言有一定的幫助,需要的可以參考下2023-11-11
Golang?中的?strconv?包常用函數(shù)及用法詳解
strconv是Golang中一個(gè)非常常用的包，主要用于字符串和基本數(shù)據(jù)類型之間的相互轉(zhuǎn)換，這篇文章主要介紹了Golang中的strconv包,需要的朋友可以參考下2023-06-06
本文給大家匯總介紹了go語言中的文件操作的代碼，包括文件的讀寫，文件的新建打開和刪除等，希望對大家學(xué)習(xí)go語言能夠有所幫助2018-10-10
關(guān)于Go語言中特有的設(shè)計(jì)模式與實(shí)現(xiàn)方式講解
雖然Go語言沒有像其他語言那樣明確的設(shè)計(jì)模式，但在實(shí)踐中，開發(fā)者們?nèi)匀话l(fā)現(xiàn)了一些在Go語言中特別適用的設(shè)計(jì)模式和實(shí)現(xiàn)方式，本文就來和大家一一進(jìn)行講解2023-05-05
Go并發(fā):使用sync.WaitGroup實(shí)現(xiàn)協(xié)程同步方式
這篇文章主要介紹了Go并發(fā):使用sync.WaitGroup實(shí)現(xiàn)協(xié)程同步方式，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05