美文网首页设计模式
手撸golang 基本数据结构与算法 队列

手撸golang 基本数据结构与算法 队列

作者: 老罗话编程 | 来源:发表于2021-02-17 07:23 被阅读0次

    手撸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)

    相关文章

      网友评论

        本文标题:手撸golang 基本数据结构与算法 队列

        本文链接:https://www.haomeiwen.com/subject/sgqixltx.html