golang 容器數據類型

container 包實現(xiàn)了三個復雜的數據結構：堆，鏈表，環(huán)（heap、list 和 ring）啦逆。當我們需要使用這些數據結構時可以直接使用而不必自己去實現(xiàn)一遍相關算法。

1. 堆

堆使用的數據結構是最小二叉樹笛洛，即根節(jié)點比左邊子樹和右邊子樹的所有值都小夏志。 go的堆包只是實現(xiàn)了一個接口，看下它的定義：

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

可以看出苛让，這個堆組合了 sort 包的 sort.Interface, 回顧下 sort.Interface沟蔑，它需要實現(xiàn)三個方法

Len() int
Less(i, j int) bool
Swap(i, j int)

加上堆接口定義的兩個方法

Push(x interface{})
Pop() interface{}

就是說你定義了一個堆，就要實現(xiàn)五個方法狱杰，直接拿 package doc 中的example 做例子：

type IntHeap []int

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 = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

那么 IntHeap 就實現(xiàn)了這個堆結構瘦材，我們就可以使用堆的方法來對它進行操作：

h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
heap.Pop(h)

具體說下內部實現(xiàn)，是使用最小堆浦旱，索引排序從根節(jié)點開始宇色，然后左子樹九杂，右子樹的順序方式颁湖。內部實現(xiàn)了down和up分別表示對堆中的某個元素向下保證最小堆和向上保證最小堆。

當往堆中插入一個元素的時候例隆，這個元素插入到最右子樹的最后一個節(jié)點中甥捺，然后調用up向上保證最小堆。

當要從堆中推出一個元素的時候镀层，先吧這個元素和右子樹最后一個節(jié)點兌換镰禾，然后彈出最后一個節(jié)點，然后對root調用down唱逢，向下保證最小堆吴侦。

鏈表

鏈表就是一個有 prev和 next指針的數組了。它維護兩個type坞古，(注意备韧，這里不是interface)

type Element struct {
    next, prev *Element  // 上一個元素和下一個元素
    list *List  // 元素所在鏈表
    Value interface{}  // 元素
}

type List struct {
    root Element  // 鏈表的根元素
    len  int      // 鏈表的長度
}

基本使用是先創(chuàng)建list，然后往list中插入值痪枫，list就內部創(chuàng)建一個Element织堂，并內部設置好Element的next,prev等叠艳。具體可以看下例子：

// This example demonstrates an integer heap built using the heap interface.
package main

import (
    "container/list"
    "fmt"
)

func main() {
    list := list.New()
    list.PushBack(1)
    list.PushBack(2)

    fmt.Printf("len: %v\n", list.Len());
    fmt.Printf("first: %#v\n", list.Front());
    fmt.Printf("second: %#v\n", list.Front().Next());
}

output:
len: 2
first: &list.Element{next:(*list.Element)(0x2081be1b0), prev:(*list.Element)(0x2081be150), list:(*list.List)(0x2081be150), Value:1}
second: &list.Element{next:(*list.Element)(0x2081be150), prev:(*list.Element)(0x2081be180), list:(*list.List)(0x2081be150), Value:2}

list對應的方法有：

type Element
    func (e *Element) Next() *Element
    func (e *Element) Prev() *Element
type List
    func New() *List
    func (l *List) Back() *Element   // 最后一個元素
    func (l *List) Front() *Element  // 第一個元素
    func (l *List) Init() *List  // 鏈表初始化
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某個元素后插入
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在某個元素前插入
    func (l *List) Len() int // 在鏈表長度
    func (l *List) MoveAfter(e, mark *Element)  // 把e元素移動到mark之后
    func (l *List) MoveBefore(e, mark *Element)  // 把e元素移動到mark之前
    func (l *List) MoveToBack(e *Element) // 把e元素移動到隊列最后
    func (l *List) MoveToFront(e *Element) // 把e元素移動到隊列最頭部
    func (l *List) PushBack(v interface{}) *Element  // 在隊列最后插入元素
    func (l *List) PushBackList(other *List)  // 在隊列最后插入接上新隊列
    func (l *List) PushFront(v interface{}) *Element  // 在隊列頭部插入元素
    func (l *List) PushFrontList(other *List) // 在隊列頭部插入接上新隊列
    func (l *List) Remove(e *Element) interface{} // 刪除某個元素

環(huán)

環(huán)的結構有點特殊，環(huán)的尾部就是頭部易阳，所以每個元素實際上就可以代表自身的這個環(huán)附较。它不需要像 list 一樣保持 list 和 element 兩個結構，只需要保持一個結構就行潦俺。

type Ring struct {
    next, prev *Ring
    Value      interface{}
}

我們初始化環(huán)的時候拒课，需要定義好環(huán)的大小，然后對環(huán)的每個元素進行賦值黑竞。環(huán)還提供一個 Do 方法捕发，能便利一遍環(huán)，對每個元素執(zhí)行一個function很魂。看下面的例子：

// This example demonstrates an integer heap built using the heap interface.
package main

import (
    "container/ring"
    "fmt"
)

func main() {
    ring := ring.New(3)

    for i := 1; i <= 3; i++ {
        ring.Value = i
        ring = ring.Next()
    }

    // 計算1+2+3
    s := 0
    ring.Do(func(p interface{}){
        s += p.(int)
    })
    fmt.Println("sum is", s)
}

output:
sum is 6

ring提供的方法有

type Ring
    func New(n int) *Ring  // 初始化環(huán)
    func (r *Ring) Do(f func(interface{}))  // 循環(huán)環(huán)進行操作
    func (r *Ring) Len() int // 環(huán)長度
    func (r *Ring) Link(s *Ring) *Ring // 連接兩個環(huán)
    func (r *Ring) Move(n int) *Ring // 指針從當前元素開始向后移動或者向前（n可以為負數）
    func (r *Ring) Next() *Ring // 當前元素的下個元素
    func (r *Ring) Prev() *Ring // 當前元素的上個元素
    func (r *Ring) Unlink(n int) *Ring // 從當前元素開始扎酷，刪除n個元素