Go標準容器之Ring的使用說明
更新時間：2021年05月04日 13:00:46 作者：Cynhard85
這篇文章主要介紹了Go標準容器之Ring的使用說明，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
簡介
Go的標準包Container中包含了常用的容器類型，包括conatiner/list，container/heap，container/ring，本篇講解container/ring的使用。
ring包
ring包提供了環(huán)形鏈表的操作。它僅導出了一個類型，Ring：
// Ring表示環(huán)形鏈表中的元素。
type Ring struct {
Value interface{} // Value類型為interface{}，因此可以接受任意類型
}
// 創(chuàng)建一個長度為n的環(huán)形鏈表
func New(n int) *Ring
// 針對環(huán)形鏈表中的每一個元素x進行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 獲取環(huán)形鏈表長度
func (r *Ring) Len() int
// 如果r和s在同一環(huán)形鏈表中，則刪除r和s之間的元素，
// 被刪除的元素組成一個新的環(huán)形鏈表，返回值為該環(huán)形鏈表的指針（即刪除前，r->Next()表示的元素）
// 如果r和s不在同一個環(huán)形鏈表中，則將s插入到r后面，返回值為
// 插入s后，s最后一個元素的下一個元素（即插入前，r->Next()表示的元素）
func (r *Ring) Link(s *Ring) *Ring
// 移動 n % r.Len() 個位置，n正負均可
func (r *Ring) Move(n int) *Ring
// 返回下一個元素
func (r *Ring) Next() *Ring
// 返回前一個元素
func (r *Ring) Prev() *Ring
// 刪除r后面的 n % r.Len() 個元素
func (r *Ring) Unlink(n int) *Ring示例
Ring的用法
package main
import (
"container/ring"
"fmt"
)
func main() {
const rLen = 3
// 創(chuàng)建新的Ring
r := ring.New(rLen)
for i := 0; i < rLen; i++ {
r.Value = i
r = r.Next()
}
fmt.Printf("Length of ring: %d\n", r.Len()) // Length of ring: 3
// 該匿名函數用來打印Ring中的數據
printRing := func(v interface{}) {
fmt.Print(v, " ")
}
r.Do(printRing) // 0 1 2
fmt.Println()
// 將r之后的第二個元素的值乘以2
r.Move(2).Value = r.Move(2).Value.(int) * 2
r.Do(printRing) // 0 1 4
fmt.Println()
// 刪除 r 與 r+2 之間的元素，即刪除 r+1
// 返回刪除的元素組成的Ring的指針
result := r.Link(r.Move(2))
r.Do(printRing) // 0 4
fmt.Println()
result.Do(printRing) // 1
fmt.Println()
another := ring.New(rLen)
another.Value = 7
another.Next().Value = 8 // 給 another + 1 表示的元素賦值，即第二個元素
another.Prev().Value = 9 // 給 another - 1 表示的元素賦值，即第三個元素
another.Do(printRing) // 7 8 9
fmt.Println()
// 插入another到r后面，返回插入前r的下一個元素
result = r.Link(another)
r.Do(printRing) // 0 7 8 9 4
fmt.Println()
result.Do(printRing) // 4 0 7 8 9
fmt.Println()
// 刪除r之后的三個元素，返回被刪除元素組成的Ring的指針
result = r.Unlink(3)
r.Do(printRing) // 0 4
fmt.Println()
result.Do(printRing) // 7 8 9
fmt.Println()
}模擬約瑟夫問題
環(huán)形列表可以模擬約瑟夫問題。約瑟夫問題描述如下：
來自百度：
據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自/殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自/殺，然后再由下一個重新報數，直到所有人都自/殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
用代碼模擬如下：
package main
import (
"container/ring"
"fmt"
)
type Player struct {
position int // 位置
alive bool // 是否存活
}
func main() {
const (
playerCount = 41 // 玩家人數
startPos = 1 // 開始報數位置
)
deadline := 3
r := ring.New(playerCount)
// 設置所有玩家初始值
for i := 1; i <= playerCount; i++ {
r.Value = &Player{i, true}
r = r.Next()
}
// 如果開始報數的位置不為1，則設置開始位置
if startPos > 1 {
r = r.Move(startPos - 1)
}
counter := 1 // 報數從1開始，因為下面的循環(huán)從第二個開始計算
deadCount := 0 // 死亡人數，初始值為0
for deadCount < playerCount { // 直到所有人都死亡，否則循環(huán)一直執(zhí)行
r = r.Next() // 跳到下一個人
// 如果是活著的人，則報數
if r.Value.(*Player).alive {
counter++
}
// 如果報數為deadline，則此人淘汰出局
if counter == deadline {
r.Value.(*Player).alive = false
fmt.Printf("Player %d died!\n", r.Value.(*Player).position)
deadCount++
counter = 0 // 報數置成0
}
}
}輸出如下，可以看到16和31是最后兩個出隊列的，因此Josephus將他的朋友與自己安排在第16個與第31個位置是安全的。
Player 3 died!
Player 6 died!
Player 9 died!
Player 12 died!
Player 15 died!
Player 18 died!
Player 21 died!
Player 24 died!
Player 27 died!
Player 30 died!
Player 33 died!
Player 36 died!
Player 39 died!
Player 1 died!
Player 5 died!
Player 10 died!
Player 14 died!
Player 19 died!
Player 23 died!
Player 28 died!
Player 32 died!
Player 37 died!
Player 41 died!
Player 7 died!
Player 13 died!
Player 20 died!
Player 26 died!
Player 34 died!
Player 40 died!
Player 8 died!
Player 17 died!
Player 29 died!
Player 38 died!
Player 11 died!
Player 25 died!
Player 2 died!
Player 22 died!
Player 4 died!
Player 35 died!
Player 16 died!
Player 31 died!
補充：go語言中container容器數據結構heap、list、ring
heap堆的使用：
package main
import (
"container/heap"
"fmt"
)
type IntHeap []int
//我們自定義一個堆需要實現5個接口
//Len(),Less(),Swap()這是繼承自sort.Interface
//Push()和Pop()是堆自已的接口
//返回長度
func (h *IntHeap) Len() int {
return len(*h);
}
//比較大小(實現最小堆)
func (h *IntHeap) Less(i, j int) bool {
return (*h)[i] < (*h)[j];
}
//交換值
func (h *IntHeap) Swap(i, j int) {
(*h)[i], (*h)[j] = (*h)[j], (*h)[i];
}
//壓入數據
func (h *IntHeap) Push(x interface{}) {
//將數據追加到h中
*h = append(*h, x.(int))
}
//彈出數據
func (h *IntHeap) Pop() interface{} {
old := *h;
n := len(old);
x := old[n-1];
//讓h指向新的slice
*h = old[0: n-1];
//返回最后一個元素
return x;
}
//打印堆
func (h *IntHeap) PrintHeap() {
//元素的索引號
i := 0
//層級的元素個數
levelCount := 1
for i+1 <= h.Len() {
fmt.Println((*h)[i: i+levelCount])
i += levelCount
if (i + levelCount*2) <= h.Len() {
levelCount *= 2
} else {
levelCount = h.Len() - i
}
}
}
func main() {
a := IntHeap{6, 2, 3, 1, 5, 4};
//初始化堆
heap.Init(&a);
a.PrintHeap();
//彈出數據，保證每次操作都是規(guī)范的堆結構
fmt.Println(heap.Pop(&a));
a.PrintHeap();
fmt.Println(heap.Pop(&a));
a.PrintHeap();
heap.Push(&a, 0);
heap.Push(&a, 8);
a.PrintHeap();
}list鏈表的使用：
package main;
import (
"container/list"
"fmt"
)
func printList(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ");
}
fmt.Println();
}
func main() {
//創(chuàng)建一個鏈表
l := list.New();
//鏈表最后插入元素
a1 := l.PushBack(1);
b2 := l.PushBack(2);
//鏈表頭部插入元素
l.PushFront(3);
l.PushFront(4);
printList(l);
//取第一個元素
f := l.Front();
fmt.Println(f.Value);
//取最后一個元素
b := l.Back();
fmt.Println(b.Value);
//獲取鏈表長度
fmt.Println(l.Len());
//在某元素之后插入
l.InsertAfter(66, a1);
//在某元素之前插入
l.InsertBefore(88, a1);
printList(l);
l2 := list.New();
l2.PushBack(11);
l2.PushBack(22);
//鏈表最后插入新鏈表
l.PushBackList(l2);
printList(l);
//鏈表頭部插入新鏈表
l.PushFrontList(l2);
printList(l);
//移動元素到最后
l.MoveToBack(a1);
printList(l);
//移動元素到頭部
l.MoveToFront(a1);
printList(l);
//移動元素在某元素之后
l.MoveAfter(b2, a1);
printList(l);
//移動元素在某元素之前
l.MoveBefore(b2, a1);
printList(l);
//刪除某元素
l.Remove(a1);
printList(l);
}ring環(huán)的使用：
package main;
import (
"container/ring"
"fmt"
)
func printRing(r *ring.Ring) {
r.Do(func(v interface{}) {
fmt.Print(v.(int), " ");
});
fmt.Println();
}
func main() {
//創(chuàng)建環(huán)形鏈表
r := ring.New(5);
//循環(huán)賦值
for i := 0; i < 5; i++ {
r.Value = i;
//取得下一個元素
r = r.Next();
}
printRing(r);
//環(huán)的長度
fmt.Println(r.Len());
//移動環(huán)的指針
r.Move(2);
//從當前指針刪除n個元素
r.Unlink(2);
printRing(r);
//連接兩個環(huán)
r2 := ring.New(3);
for i := 0; i < 3; i++ {
r2.Value = i + 10;
//取得下一個元素
r2 = r2.Next();
}
printRing(r2);
r.Link(r2);
printRing(r);
}以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。如有錯誤或未考慮完全的地方，望不吝賜教。
相關文章
這篇文章主要介紹了GO函數(func)的聲明與使用,包括了GO語言函數聲明與使用,GO語言遞歸函數,GO語言內置函數,GO語言函數defer應用,GO語言函數可變長度參數需要的朋友可以參考下2022-12-12
go語言執(zhí)行等待直到后臺goroutine執(zhí)行完成實例分析
這篇文章主要介紹了go語言執(zhí)行等待直到后臺goroutine執(zhí)行完成的方法,實例分析了Go語言中WaitGroup的使用技巧,需要的朋友可以參考下2015-03-03
這篇文章主要為大家介紹了go新工具gonew生成模板工具鏈使用詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-08-08
協程之間的通信只能夠通過通道。但是我們習慣于共享變量，而且很多時候使用共享變量能讓代碼更簡潔。那么Golang共享變量如何解決問題，感興趣的可以了解一下2021-12-12
淺析Golang開發(fā)中goroutine的正確使用姿勢
很多初級的Gopher在學習了goroutine之后,在項目中其實使用率不高,所以這篇文章小編主要來帶大家深入了解一下goroutine的常見使用方法,希望對大家有所幫助2024-03-03
這篇文章主要介紹了Go語言操作redis用法,實例分析了Go語言操作redis的技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-02-02
gRPC是由Google主導開發(fā)的RPC框架，使用HTTP/2協議并用ProtoBuf作為序列化工具。這篇文章主要介紹了go grpc安裝使用教程,需要的朋友可以參考下2018-02-02
這篇文章主要介紹了在Go程序中實現服務器重啟的方法,由于很多人盲目崇拜谷歌"親爹",Go語言在國內有著不尋常的人氣,需要的朋友可以參考下2015-06-06
Go中Map是一個KV對集合,下面這篇文章主要給大家介紹了關于Golang中map探究的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2022-12-12
這篇文章主要為大家詳細介紹了Go語言中一些常見的文件操作，文中的示例代碼講解詳細，對我們學習Go語言有一定的幫助，需要的可以參考一下2022-04-04