手撸golang 根本数据结构与算法 队列
缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
队列
队列中的数据也呈线性排列。队列中增加和删除数据的操作别离是在两端进行的。就和“队列”这个名字一样，把它设想成排成一队的人更容易了解。在队列中，解决总是从第一名开始往后进行，而新来的人只能排在队尾。像队列这种最先进去的数据最先被取来，即“先进先出”的构造，咱们称为First In First Out，简称FIFO。摘自 <<我的第一本算法书>>(【日】石田保辉；宫崎修一)指标
- 以数组+读写双指针为根底, 实现一个FIFO队列
- 能够初始指定冀望容量大小
- 当元素数量超过容量/2时, 主动以2倍率速度扩容
- 提供免拷贝的迭代器, 并能检测迭代版本谬误(Concurrent Modification Error)
设计
- IQueue: 队列的接口
- IListIterator: 迭代器接口
- tArrayQueue: 以数组+读写双指针为根底的FIFO队列, 实现IQueue接口.
- tQueueIterator: 免拷贝的队列迭代器, 通过版本号检测迭代中的Concurrent Modification Error
单元测试
queue_test.go
package data_structureimport ( "fmt" qu "learning/gooop/data_structure/queue" "strings" "testing")func Test_Queue(t *testing.T) { fnAssertTrue := func(b bool, msg string) { if !b { t.Fatal(msg) } } queue := qu.NewArrayQueue(1) state := queue.String() t.Log(state) fnAssertTrue(state == "c=2,r=0,w=0,s=0,v=0 []", "expecting []") fnAssertTrue(queue.IsEmpty(), "expecting IsEmpty()") queue.Push(10) state = queue.String() t.Log(state) fnAssertTrue(state == "c=2,r=0,w=1,s=1,v=1 [10]", "expecting [10]") fnAssertTrue(queue.IsNotEmpty(), "expecting IsNotEmpty()") queue.Push(20) state = queue.String() t.Log(state) fnAssertTrue(state == "c=2,r=0,w=2,s=2,v=2 [10,20]", "expecting [10,20]") queue.Push(30) state = queue.String() t.Log(state) fnAssertTrue(state == "c=4,r=0,w=3,s=3,v=3 [10,20,30]", "expecting [10,20,30]") e,v := queue.Peek() fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(v == 10, "expecting Peek() = 10") e,v = queue.Poll() fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(v == 10, "expecting Peek() = 10") state = queue.String() t.Log(state) fnAssertTrue(state == "c=4,r=1,w=3,s=2,v=4 [20,30]", "expecting [20,30]") e,v = queue.Poll() fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(v == 20, "expecting Peek() = 20") state = queue.String() t.Log(state) fnAssertTrue(state == "c=4,r=0,w=1,s=1,v=5 [30]", "expecting [30]") e,v = queue.Poll() fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(v == 30, "expecting Peek() = 30") state = queue.String() t.Log(state) fnAssertTrue(state == "c=4,r=1,w=1,s=0,v=6 []", "expecting []") queue.Push(40) queue.Push(50) queue.Push(60) queue.Push(70) queue.Push(80) queue.Push(90) e,v = queue.Poll() fnAssertTrue(e == nil, "expecting e == nil") fnAssertTrue(v == 40, "expecting Peek() = 40") state = queue.String() t.Log(state) fnAssertTrue(state == "c=8,r=1,w=6,s=5,v=13 [50,60,70,80,90]", "expecting [50,60,70,80,90]") items := make([]string, 0) for iter := queue.Iterator();iter.More(); { e,v := iter.Next() fnAssertTrue(e == nil, "expecting e == nil") items = append(items, fmt.Sprintf("%v", v)) } itemString := strings.Join(items, ",") t.Log(itemString) fnAssertTrue(itemString == "50,60,70,80,90", "expecting [50,60,70,80,90]")}测试输入
$ go test -v queue_test.go === RUN Test_Queue queue_test.go:19: c=2,r=0,w=0,s=0,v=0 [] queue_test.go:25: c=2,r=0,w=1,s=1,v=1 [10] queue_test.go:31: c=2,r=0,w=2,s=2,v=2 [10,20] queue_test.go:36: c=4,r=0,w=3,s=3,v=3 [10,20,30] queue_test.go:47: c=4,r=1,w=3,s=2,v=4 [20,30] queue_test.go:54: c=4,r=0,w=1,s=1,v=5 [30] queue_test.go:61: c=4,r=1,w=1,s=0,v=6 [] queue_test.go:74: c=8,r=1,w=6,s=5,v=13 [50,60,70,80,90] queue_test.go:84: 50,60,70,80,90--- PASS: Test_Queue (0.00s)PASSok command-line-arguments 0.003sIQueue.go
队列的接口
package queuetype IQueue interface { Size() int IsEmpty() bool IsNotEmpty() bool Push(value interface{}) Poll() (error, interface{}) Peek() (error, interface{}) Clear() Iterator() IListIterator String() string}IListIterator.go
迭代器接口
package queuetype IListIterator interface { More() bool Next() (error,interface{})}tArrayQueue.go
以数组+读写双指针为根底的FIFO队列, 实现IQueue接口.
package queueimport ( "errors" "fmt" "strings")type tArrayQueue struct { items []interface{} capacity int rindex int windex int version int64}var gEmptyQueueError = errors.New("empty queue")func NewArrayQueue(initSpace int) IQueue { if initSpace < 0 { initSpace = 0 } c := initSpace*2 return &tArrayQueue{ items: make([]interface{}, c), capacity: c, rindex: 0, windex: 0, version: 0, }}func (me *tArrayQueue) Size() int { return me.windex - me.rindex}func (me *tArrayQueue) IsEmpty() bool { return me.Size() <= 0}func (me *tArrayQueue) IsNotEmpty() bool { return !me.IsEmpty()}func (me *tArrayQueue) Push(value interface{}) { me.ensureSpace(1) me.items[me.windex] = value me.windex++ me.version++}func (me *tArrayQueue) ensureSpace(space int) { if me.remainingSpace() >= space { return } for ;me.remainingSpace()<space; { me.capacity = maxInt(me.capacity*2, me.capacity + 1) } newItems := make([]interface{}, me.capacity) p := 0 for i := me.rindex;i < me.windex;i++ { newItems[p] = me.items[i] p++ } me.items = newItems me.windex -= me.rindex me.rindex = 0}func maxInt(x,y int) int { if x >= y { return x } return y}func (me *tArrayQueue) remainingSpace() int { return me.capacity - me.windex}func (me *tArrayQueue) Poll() (error, interface{}) { if me.IsEmpty() { return gEmptyQueueError, nil } it := me.items[me.rindex] me.items[me.rindex] = nil me.rindex++ if me.rindex >= me.capacity / 2 { p := 0 for i := me.rindex;i < me.windex;i++ { me.items[p] = me.items[i] me.items[i] = nil p++ } me.windex -= me.rindex me.rindex = 0 } me.version++ return nil, it}func (me *tArrayQueue) Peek() (error, interface{}) { if me.IsEmpty() { return gEmptyQueueError, nil } return nil, me.items[me.rindex]}func (me *tArrayQueue) Clear() { for i := me.rindex;i < me.windex;i++ { me.items[i] = nil } me.rindex = 0 me.windex = 0 me.version++}func (me *tArrayQueue) Iterator() IListIterator { return newArrayQueueIterator(me)}func (me *tArrayQueue) String() string { itemStrings := make([]string, me.Size()) p := 0 for i := me.rindex;i < me.windex;i++ { itemStrings[p] = fmt.Sprintf("%v", me.items[i]) p++ } 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, ","))}tQueueIterator.go
免拷贝的队列迭代器, 通过版本号检测迭代中的Concurrent Modification Error
package queueimport "errors"type tQueueIterator struct { queue *tArrayQueue pos int version int64}var gConcurrentModificationError = errors.New("concurrent modification error")var gNoMoreElementsError = errors.New("no more elements")func newArrayQueueIterator(queue *tArrayQueue) IListIterator { return &tQueueIterator{ queue: queue, pos : queue.rindex, version: queue.version, }}func (me *tQueueIterator) More() bool { q := me.queue if q == nil { return false } if q.version != me.version { return false } return me.pos < q.windex}func (me *tQueueIterator) Next() (error, interface{}) { q := me.queue if q == nil { return gEmptyQueueError, nil } if q.version != me.version { return gConcurrentModificationError, nil } if me.pos >= q.windex { return gNoMoreElementsError, nil } it := q.items[me.pos] me.pos++ return nil, it}(end)