缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

队列

  1. 队列中的数据也呈线性排列。
  2. 队列中添加和删除数据的操作分别是在两端进行的。
  4. 就和“队列”这个名字一样，
  5. 把它想象成排成一队的人更容易理解。
  6. 在队列中，
  7. 处理总是从第一名开始往后进行，
  8. 而新来的人只能排在队尾。
  10. 像队列这种最先进去的数据最先被取来，
  11. 即“先进先出”的结构，
  12. 我们称为First In First Out，简称FIFO。
  14. 摘自 <<我的第一本算法书>>(【日】石田保辉；宫崎修一)

目标

  • 以数组+读写双指针为基础, 实现一个FIFO队列
  • 可以初始指定期望容量大小
  • 当元素数量超过容量/2时, 自动以2倍率速度扩容
  • 提供免拷贝的迭代器, 并能检测迭代版本错误(Concurrent Modification Error)

设计

  • IQueue: 队列的接口
  • IListIterator: 迭代器接口
  • tArrayQueue: 以数组+读写双指针为基础的FIFO队列, 实现IQueue接口.
  • tQueueIterator: 免拷贝的队列迭代器, 通过版本号检测迭代中的Concurrent Modification Error

单元测试

queue_test.go

  1. package data_structure
  3. import (
  4.     "fmt"
  5.     qu "learning/gooop/data_structure/queue"
  6.     "strings"
  7.     "testing"
  8. )
  10. func Test_Queue(t *testing.T) {
  11.     fnAssertTrue := func(b bool, msg string) {
  12.         if !b {
  13.             t.Fatal(msg)
  14.         }
  15.     }
  17.     queue := qu.NewArrayQueue(1)
  18.     state := queue.String()
  19.     t.Log(state)
  20.     fnAssertTrue(state == "c=2,r=0,w=0,s=0,v=0 []", "expecting []")
  21.     fnAssertTrue(queue.IsEmpty(), "expecting IsEmpty()")
  23.     queue.Push(10)
  24.     state = queue.String()
  25.     t.Log(state)
  26.     fnAssertTrue(state == "c=2,r=0,w=1,s=1,v=1 [10]", "expecting [10]")
  27.     fnAssertTrue(queue.IsNotEmpty(), "expecting IsNotEmpty()")
  29.     queue.Push(20)
  30.     state = queue.String()
  31.     t.Log(state)
  32.     fnAssertTrue(state == "c=2,r=0,w=2,s=2,v=2 [10,20]", "expecting [10,20]")
  34.     queue.Push(30)
  35.     state = queue.String()
  36.     t.Log(state)
  37.     fnAssertTrue(state == "c=4,r=0,w=3,s=3,v=3 [10,20,30]", "expecting [10,20,30]")
  39.     e,v := queue.Peek()
  40.     fnAssertTrue(e == nil, "expecting e == nil")
  41.     fnAssertTrue(v == 10, "expecting Peek() = 10")
  43.     e,v = queue.Poll()
  44.     fnAssertTrue(e == nil, "expecting e == nil")
  45.     fnAssertTrue(v == 10, "expecting Peek() = 10")
  46.     state = queue.String()
  47.     t.Log(state)
  48.     fnAssertTrue(state == "c=4,r=1,w=3,s=2,v=4 [20,30]", "expecting [20,30]")
  50.     e,v = queue.Poll()
  51.     fnAssertTrue(e == nil, "expecting e == nil")
  52.     fnAssertTrue(v == 20, "expecting Peek() = 20")
  53.     state = queue.String()
  54.     t.Log(state)
  55.     fnAssertTrue(state == "c=4,r=0,w=1,s=1,v=5 [30]", "expecting [30]")
  57.     e,v = queue.Poll()
  58.     fnAssertTrue(e == nil, "expecting e == nil")
  59.     fnAssertTrue(v == 30, "expecting Peek() = 30")
  60.     state = queue.String()
  61.     t.Log(state)
  62.     fnAssertTrue(state == "c=4,r=1,w=1,s=0,v=6 []", "expecting []")
  64.     queue.Push(40)
  65.     queue.Push(50)
  66.     queue.Push(60)
  67.     queue.Push(70)
  68.     queue.Push(80)
  69.     queue.Push(90)
  70.     e,v = queue.Poll()
  71.     fnAssertTrue(e == nil, "expecting e == nil")
  72.     fnAssertTrue(v == 40, "expecting Peek() = 40")
  73.     state = queue.String()
  74.     t.Log(state)
  75.     fnAssertTrue(state == "c=8,r=1,w=6,s=5,v=13 [50,60,70,80,90]", "expecting [50,60,70,80,90]")
  77.     items := make([]string, 0)
  78.     for iter := queue.Iterator();iter.More(); {
  79.         e,v := iter.Next()
  80.         fnAssertTrue(e == nil, "expecting e == nil")
  81.         items = append(items, fmt.Sprintf("%v", v))
  82.     }
  83.     itemString := strings.Join(items, ",")
  84.     t.Log(itemString)
  85.     fnAssertTrue(itemString == "50,60,70,80,90", "expecting [50,60,70,80,90]")
  86. }

测试输出

  1. $ go test -v queue_test.go 
  2. === RUN   Test_Queue
  3.     queue_test.go:19: c=2,r=0,w=0,s=0,v=0 []
  4.     queue_test.go:25: c=2,r=0,w=1,s=1,v=1 [10]
  5.     queue_test.go:31: c=2,r=0,w=2,s=2,v=2 [10,20]
  6.     queue_test.go:36: c=4,r=0,w=3,s=3,v=3 [10,20,30]
  7.     queue_test.go:47: c=4,r=1,w=3,s=2,v=4 [20,30]
  8.     queue_test.go:54: c=4,r=0,w=1,s=1,v=5 [30]
  9.     queue_test.go:61: c=4,r=1,w=1,s=0,v=6 []
  10.     queue_test.go:74: c=8,r=1,w=6,s=5,v=13 [50,60,70,80,90]
  11.     queue_test.go:84: 50,60,70,80,90
  12. --- PASS: Test_Queue (0.00s)
  13. PASS
  14. ok      command-line-arguments  0.003s

IQueue.go

队列的接口

  1. package queue
  3. type IQueue interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Push(value interface{})
  9.     Poll() (error, interface{})
  10.     Peek() (error, interface{})
  11.     Clear()
  13.     Iterator() IListIterator
  14.     String() string
  15. }

IListIterator.go

迭代器接口

  1. package queue
  3. type IListIterator interface {
  4.     More() bool
  5.     Next() (error,interface{})
  6. }

tArrayQueue.go

以数组+读写双指针为基础的FIFO队列, 实现IQueue接口. 

  1. package queue
  3. import (
  4.     "errors"
  5.     "fmt"
  6.     "strings"
  7. )
  9. type tArrayQueue struct {
  10.     items []interface{}
  11.     capacity int
  12.     rindex int
  13.     windex int
  14.     version int64
  15. }
  17. var gEmptyQueueError = errors.New("empty queue")
  19. func NewArrayQueue(initSpace int) IQueue {
  20.     if initSpace < 0 {
  21.         initSpace = 0
  22.     }
  23.     c := initSpace*2
  25.     return &tArrayQueue{
  26.         items: make([]interface{}, c),
  27.         capacity: c,
  28.         rindex: 0,
  29.         windex: 0,
  30.         version: 0,
  31.     }
  32. }
  34. func (me *tArrayQueue) Size() int {
  35.     return me.windex - me.rindex
  36. }
  38. func (me *tArrayQueue) IsEmpty() bool {
  39.     return me.Size() <= 0
  40. }
  42. func (me *tArrayQueue) IsNotEmpty() bool {
  43.     return !me.IsEmpty()
  44. }
  46. func (me *tArrayQueue) Push(value interface{}) {
  47.     me.ensureSpace(1)
  48.     me.items[me.windex] = value
  49.     me.windex++
  50.     me.version++
  51. }
  53. func (me *tArrayQueue) ensureSpace(space int) {
  54.     if me.remainingSpace() >= space {
  55.         return
  56.     }
  58.     for ;me.remainingSpace()<space; {
  59.         me.capacity = maxInt(me.capacity*2, me.capacity + 1)
  60.     }
  62.     newItems := make([]interface{}, me.capacity)
  63.     p := 0
  64.     for i := me.rindex;i < me.windex;i++ {
  65.         newItems[p] = me.items[i]
  66.         p++
  67.     }
  69.     me.items = newItems
  70.     me.windex -= me.rindex
  71.     me.rindex = 0
  72. }
  74. func maxInt(x,y int) int {
  75.     if x >= y {
  76.         return x
  77.     }
  78.     return y
  79. }
  81. func (me *tArrayQueue) remainingSpace() int {
  82.     return me.capacity - me.windex
  83. }
  85. func (me *tArrayQueue) Poll() (error, interface{}) {
  86.     if me.IsEmpty() {
  87.         return gEmptyQueueError, nil
  88.     }
  90.     it := me.items[me.rindex]
  91.     me.items[me.rindex] = nil
  92.     me.rindex++
  94.     if me.rindex >= me.capacity / 2 {
  95.         p := 0
  96.         for i := me.rindex;i < me.windex;i++ {
  97.             me.items[p] = me.items[i]
  98.             me.items[i] = nil
  99.             p++
  100.         }
  101.         me.windex -= me.rindex
  102.         me.rindex = 0
  103.     }
  105.     me.version++
  106.     return nil, it
  107. }
  110. func (me *tArrayQueue) Peek() (error, interface{}) {
  111.     if me.IsEmpty() {
  112.         return gEmptyQueueError, nil
  113.     }
  115.     return nil, me.items[me.rindex]
  116. }
  118. func (me *tArrayQueue) Clear() {
  119.     for i := me.rindex;i < me.windex;i++ {
  120.         me.items[i] = nil
  121.     }
  123.     me.rindex = 0
  124.     me.windex = 0
  125.     me.version++
  126. }
  128. func (me *tArrayQueue) Iterator() IListIterator {
  129.     return newArrayQueueIterator(me)
  130. }
  132. func (me *tArrayQueue) String() string {
  133.     itemStrings := make([]string, me.Size())
  134.     p := 0
  135.     for i := me.rindex;i < me.windex;i++ {
  136.         itemStrings[p] = fmt.Sprintf("%v", me.items[i])
  137.         p++
  138.     }
  140.     return fmt.Sprintf("c=%v,r=%v,w=%v,s=%v,v=%v [%s]", me.capacity, me.rindex, me.windex, me.Size(), me.version, strings.Join(itemStrings, ","))
  141. }

tQueueIterator.go

免拷贝的队列迭代器, 通过版本号检测迭代中的Concurrent Modification Error

  1. package queue
  3. import "errors"
  5. type tQueueIterator struct {
  6.     queue *tArrayQueue
  7.     pos int
  8.     version int64
  9. }
  11. var gConcurrentModificationError = errors.New("concurrent modification error")
  12. var gNoMoreElementsError = errors.New("no more elements")
  14. func newArrayQueueIterator(queue *tArrayQueue) IListIterator {
  15.     return &tQueueIterator{
  16.         queue: queue,
  17.         pos : queue.rindex,
  18.         version: queue.version,
  19.     }
  20. }
  22. func (me *tQueueIterator) More() bool {
  23.     q := me.queue
  24.     if q == nil {
  25.         return false
  26.     }
  28.     if q.version != me.version {
  29.         return false
  30.     }
  32.     return me.pos < q.windex
  33. }
  35. func (me *tQueueIterator) Next() (error, interface{}) {
  36.     q := me.queue
  37.     if q == nil {
  38.         return gEmptyQueueError, nil
  39.     }
  41.     if q.version != me.version {
  42.         return gConcurrentModificationError, nil
  43.     }
  45.     if me.pos >= q.windex {
  46.         return gNoMoreElementsError, nil
  47.     }
  49.     it := q.items[me.pos]
  50.     me.pos++
  51.     return nil, it
  52. }

(end)