关于算法:手撸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

队列的接口

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}

迭代器接口

package queue

type IListIterator interface {More() bool
    Next() (error,interface{})
}

以数组 + 读写双指针为根底的 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, ","))
}

免拷贝的队列迭代器, 通过版本号检测迭代中的 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-基本数据结构与算法-队列

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

缘起

队列

指标

设计

单元测试

测试输入

IQueue.go

IListIterator.go

tArrayQueue.go

tQueueIterator.go

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

缘起

队列

指标

设计

单元测试

测试输入

IQueue.go

IListIterator.go

tArrayQueue.go

tQueueIterator.go

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