container

heap

  1. import (
  2.     "container/heap"
  3.     "fmt"
  4. )
  6. // An IntHeap is a min-heap of ints.
  7. type IntHeap []int
  9. func (h IntHeap) Len() int           { return len(h) }
  10. func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
  11. func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
  13. // 末尾添加元素
  14. func (h *IntHeap) Push(x interface{}) { 
  15.     *h = append(*h, x.(int))
  16. }
  18. // 末尾删除元素
  19. func (h *IntHeap) Pop() interface{} { 
  20.     old := *h
  21.     n := len(old)
  22.     x := old[n-1]
  23.     *h = old[0 : n-1]
  24.     return x
  25. }
  27. func main() {
  28.     h := &IntHeap{2, 1, 5}
  29.     heap.Init(h)
  30.     heap.Push(h, 3)
  31.     fmt.Printf("minimum: %d\n", (*h)[0]) // 小根堆
  32.     for h.Len() > 0 {
  33.         fmt.Printf("%d ", heap.Pop(h))
  34.     }
  35. }

list

  1. import (
  2.     "container/list"
  3.     "fmt"
  4. )
  6. func main() {
  7.     // 创建一个新的链表
  8.     l := list.New() 
  9.     e2 := l.PushBack(2)
  10.     e5 := l.PushBack(5)
  11.     l.InsertBefore(3, e2)
  12.     l.InsertAfter(19, e5)
  13.     for e := l.Front(); e != nil; e = e.Next() {
  14.         fmt.Println(e.Value)   
  15.     }
  16. }

list 构建 queue/stack

  1. // queue 
  2. queue := list.New()
  3. // queue push
  4. queue.pushBack()
  5. // queue pop
  6. front := queue.Front()
  7. queue.Remove(front)
  9. // stack
  10. stack := list.New()
  11. // stack push
  12. stack.pushBack()
  13. // stack pop
  14. back := stack.Back()
  15. stack.Remove(back)

由于 stack 是在一端进行增加删除，所以使用切片来模拟 stack 会更加方便。

  1. // stack
  2. stack := []int{}
  3. // stack push
  4. stack = append(stack, elm)
  5. // stack pop
  6. stack = stack[:len(stack)-1]

LRU

  1. package lru
  3. type LRU struct {
  4.     cap  int
  5.     pos  map[int]*Element
  6.     root Element // root.next = first, root.pre = last
  7. }
  9. // Element a list element
  10. type Element struct {
  11.     Value     int
  12.     next, pre *Element
  13. }
  15. // New returns an initialized list
  16. func New(cap int) *LRU {
  17.     return new(LRU).Init(cap)
  18. }
  20. // Init initializes the lru list
  21. func (lru *LRU) Init(cap int) *LRU {
  22.     lru.root.next = &lru.root
  23.     lru.root.pre = &lru.root
  24.     lru.cap = cap
  25.     lru.pos = make(map[int]*Element)
  26.     return lru
  27. }
  29. // Query visit a value
  30. func (lru *LRU) Query(v int) {
  31.     if lru.pos[v] != nil {
  32.         lru.toLast(lru.pos[v])
  33.     } else {
  34.         if len(lru.pos) == lru.cap {
  35.             lru.pop()
  36.         }
  37.         lru.push(v)
  38.     }
  39. }
  41. func (lru *LRU) toLast(elm *Element) {
  42.     elmPre, elmNext := elm.pre, elm.next
  43.     elmPre.next = elmNext
  44.     elmNext.pre = elmPre
  46.     curLast := lru.root.pre
  47.     curLast.next = elm
  48.     elm.pre = curLast
  50.     elm.next = &lru.root
  51.     lru.root.pre = elm
  52. }
  54. // remove least visit element, which is the head of the list
  55. func (lru *LRU) pop() int {
  56.     head := lru.root.next
  57.     lru.root.next = head.next
  58.     head.next.pre = &lru.root
  59.     delete(lru.pos, head.Value)
  60.     return head.Value
  61. }
  63. func (lru *LRU) push(v int) {
  64.     elm := &Element{
  65.         Value: v,
  66.     }
  67.     curLast := lru.root.pre
  68.     curLast.next = elm
  69.     lru.root.pre = elm
  71.     elm.next = &lru.root
  72.     elm.pre = curLast
  73.     lru.pos[v] = elm
  74. }