list
栈和队列
- 栈的实现
  - 使用 list 实现栈
  - 使用切片实现栈
- 队列的实现
  - 使用 list 实现队列
  - 使用切片实现队列
ring
heap

Go 语言提供了 3 种容器双向链表 list，双向循环链表 ring 和堆 heap。
list 和 ring 的基本结构都是双向循环链表，但它们有一些区别，详见后文。

list

Go 语言中 list 是双向链表，其数据结构定义如下：

// 节点
type Element struct {
     next, prev *Element    // 后指针和前指针
    list *List            // 归属于哪个链表
    Value interface{}    // 值
}
// 双向链表
type List struct {
     root Element    // 根节点
    len int            // 链表长度
}

其图示结构如下：

可以看到，其结构非常巧妙：

链表的总体类型为 List，节点类型为 Element。
通过一个 *List 类型的变量指明每一个 Element 归属于那一条链表。
节点的值 Value 的类型为空接口类型 interface{}，这表明它可以存储任何类型的值，int, string 等都可以，因此一条链表的元素类型是可以不相同的。

此外，虽然从结构上看 list 是一个双向循环链表，但如下遍历过程却不会循环输出：

for e := L.front(); e != nil; e = e.Next() {    // L 是一条 list 链表
    fmt.Println(e.Value)
}

原因是 Next() 的实现：

func (e *Element) Next() *Element {
    if p := e.next; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}

可以看到如果 e.next == &e.list.root 的话，返回一个 nil，就避免了最后一个元素重新访问 root 节点。

提供的 API 如下：

// 属于 Element 的方法
func (e *Element) Next() *Element    // 返回当前节点的下一个节点的地址
func (e *Element) Prev() *Element    // 返回当前节点的前一个节点的地址
// 属于 List 的方法
func (l *List) Init() *List            // 初始化一个链表，返回指向该链表的指针
func (l *List) Len() int            // 返回节点个数
func (l *List) Front() *Element        // 取链表的第一个节点
func (l *List) Back() *Element         // 去链表的最后一个节点
func (l *List) PushFront(v interface{}) *Element     // 往表头插入一个节点，返回该节点的地址
func (l *List) PushBack(v interface{}) *Element        // 往表尾插入一个节点，返回该节点的地址
func (l *List) Remove(e *Element) interface{}         // 删除 e 所指向的节点
func (l *List) MoveToFront(e *Element)                // 把节点 e 移到表头，e 必须属于该链表
func (l *List) MoveToBack(e *Element)                // 把节点 e 移到表尾，e 必须属于该链表
func (l *List) PushBackList(other *List)            // 把另一条链表 other 拼接到当前链表末尾
func (l *List) PushFrontList(other *List)            // 把另一条链表 other 拼接到当前链表表头
func (l *List) MoveBefore(e, mark *Element)    // 往 mark 节点前面插入一个节点 e，e 必须属于该链表
func (l *List) MoveAfter(e, mark *Element)    // 往 mark 节点后面插入一个节点 e，e 必须属于该链表
func (l *List) InsertBefore(v interface{}, mark *Element) *Element    // 往 mark 节点之前插入一个节点
func (l *List) InsertAfter(v interface{}, mark *Element) *Element    // 往 mark 节点之后插入一个节点
// 包外访问方法
func New() *List                     // 初始化一个链表，返回指向该链表的指针，对 Init() 的封装

栈和队列

在 Go 语言中没有专门封装栈和队列这两种数据结构，但是两者在实际应用中频繁且广泛，那么 Go 语言是如何解决这个问题的呢？
答案就是：使用 list 来实现。

栈的实现

使用 list 实现栈

stack := list.New()    // 声明
stack.PushBack(1)    // 入栈
e := stack.Back()    // 取栈顶
stack.Remove(e)        // 出栈
size := stack.Len()    // 栈大小

使用切片实现栈

stack := make([]int, 0, 10)        // 声明
stack = append(stack, 1)        // 入栈
top := stack[0]                    // 取栈顶
stack = stack[:len(stack)-1]    // 出栈
size := len(stack)                // 获取栈的元素个数

这种方法有一个致命缺点：内存泄漏！
内存泄漏：向操作系统申请的内存空间，使用后却不归还，进行某些操作后，连自己都无法在访问它们，操作系统也不能对它们进行回收再利用。
比如像上述出栈操作 stack = stack[:len(stack)-1] 如果之前没有保存栈顶的地址（或其他访问它的方式），以后都无法再访问它，而它又属于切片 stack 的底层数组，因为还要用到这个底层数组的一部分，操作系统又不能回收掉这个底层数组。

队列的实现

使用 list 实现队列

// var queue list.List
// queue.Init()
queue := list.New()    // 声明
queue.PushBack(2)    // 入队
e := queue.Front()    // 取队头
queue.Remove(e)        // 出队
e = queue.Back()    // 取队尾
size := queue.Len()    // 获取队列元素个数

使用切片实现队列

queue := make([]int, 0, 10)    // 声明
queue = append(queue, 1)    // 入队
front := queue[0]            // 取队首
back := queue[len(queue)-1]    // 取队尾
queue = queue[1:]            // 出队
size := len(queue)            // 获取队列元素个数

同样存在内存泄漏的问题。

ring

heap

heap 包里定义了一组关于堆的接口，而且有关堆操作的方法的参数都必须是该接口类型的。

package heap
// heap.Interface
type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}
func Init(h Interface)
func Push(h Interface, x interface{})
func Pop(h Interface) interface{}
func Remove(h Interface, i int) interface{}
func Fix(h Interface, i int)

package sort
type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

因此根据“接口即约定”，若一个具体类型想使用接口中的方法，则必须实现该接口中的所有方法，让该具体类型具有该接口类型。

因此，我们先实现 heap.Interface，下面直接贴官方例子，打些注释

package main
import (
    "container/heap"
    "fmt"
)
// 整型最小堆
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
}
func main() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h)
    heap.Push(h, 3)
    fmt.Printf("minimum: %d\n", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

再看官方的一个经典例子：


package main
import (
    "container/heap"
    "fmt"
)
// 优先队列中的元素
type Item struct {
    value    string
    priority int
    // The index is needed by update and is maintained by the heap.Interface methods.
    // 下标在 update 操作时需要，由 heap.Interface 中的方法维护
    index int // The index of the item in the heap.
}
// 实现 heap.Interface 并保存元素
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority        // 根据优先级建立最大堆
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    // 仔细思考一下为什么下标要换回来
    pq[i].index = i
    pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil      // 避免内存泄漏
    item.index = -1     // 确保安全
    *pq = old[0 : n-1]
    return item
}
// 修改了 priority 或 value 后会破坏堆的性质，该方法用于调整堆以恢复堆性质
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}
func main() {
    items := map[string]int{
        "banana": 3, "apple": 2, "pear": 4,
    }
    pq := make(PriorityQueue, len(items))
    i := 0
    for value, priority := range items {
        pq[i] = &Item{
            value:    value,
            priority: priority,
            index:    i,
        }
        i++
    }
    heap.Init(&pq)    // 建堆
    item := &Item{
        value:    "orange",
        priority: 1,
    }
    heap.Push(&pq, item)            // 添加一个元素
    pq.update(item, item.value, 5)    // 修改一下优先级
    // 依次出堆
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("%.2d:%s ", item.priority, item.value)
    }
}

Golang

container 包