手撸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_structure
import (
"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)
PASS
ok command-line-arguments 0.003s
IQueue.go
队列的接口
package queue
type 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 queue
type IListIterator interface {
More() bool
Next() (error,interface{})
}
tArrayQueue.go
以数组+读写双指针为基础的FIFO队列, 实现IQueue接口.
package queue
import (
"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 queue
import "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)
网友评论