美文网首页程序员设计模式
手撸golang 基本数据结构与算法 栈

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

作者: 老罗话编程 | 来源:发表于2021-02-16 08:19 被阅读0次

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

    缘起

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

    栈(也叫堆栈)也是一种数据呈线性排列的数据结构,
    不过在这种结构中,
    我们只能访问最新添加的数据。
    
    栈就像是一摞书,
    拿到新书时我们会把它放在书堆的最上面,
    取书时也只能从最上面的新书开始取。
    
    像栈这种最后添加的数据最先被取出,
    即“后进先出”的结构,
    我们称为Last In First Out,简称LIFO。
    
    摘自 <<我的第一本算法书>>(【日】石田保辉;宫崎修一)
    

    目标

    • 以数组为基础实现一个LIFO栈
    • 可以指定数组的初始容量大小
    • 当元素数量超过容量时, 自动以2倍率速度扩容
    • 提供免拷贝的迭代器, 以遍历堆栈, 并能检测迭代版本错误(Concurrent Modification Error)

    设计

    • IStack: 堆栈的接口
    • IStackIterator: 堆栈迭代器的接口
    • tArrayStack: 基于自扩容数组的堆栈, 实现IStack接口
    • tStackIterator: 免拷贝的堆栈迭代器, 实现IStackIterator接口

    单元测试

    stack_test.go

    package data_structure
    
    import (
        st "learning/gooop/data_structure/stack"
        "testing"
    )
    
    func Test_Stack(t *testing.T) {
        fnAssertTrue := func(b bool, msg string) {
            if !b {
                panic(msg)
            }
        }
    
        stack := st.NewArrayStack(2)
        state := stack.String()
        t.Log(state)
        fnAssertTrue(state == "c=2,t=-1,v=0,items:", "state error")
    
        stack.Push(0)
        state = stack.String()
        t.Log(state)
        fnAssertTrue(state == "c=2,t=0,v=1,items:0", "state error")
    
        stack.Push(1)
        state = stack.String()
        t.Log(state)
        fnAssertTrue(state == "c=2,t=1,v=2,items:0,1", "state error")
    
        stack.Push(2)
        state = stack.String()
        t.Log(state)
        fnAssertTrue(state == "c=4,t=2,v=3,items:0,1,2", "state error")
    
        e,v := stack.Peek()
        fnAssertTrue(e == nil, "expecting e == nil")
        fnAssertTrue(v == 2, "expecting value 2")
    
        e,v = stack.Pop()
        state = stack.String()
        t.Log(state)
        fnAssertTrue(e == nil, "expecting e == nil")
        fnAssertTrue(v == 2, "expecting value 2")
        fnAssertTrue(state == "c=4,t=1,v=4,items:0,1", "state error")
    
        e,v = stack.Pop()
        state = stack.String()
        t.Log(state)
        fnAssertTrue(e == nil, "expecting e == nil")
        fnAssertTrue(v == 1, "expecting value 1")
        fnAssertTrue(state == "c=4,t=0,v=5,items:0", "state error")
    
        e,v = stack.Pop()
        state = stack.String()
        t.Log(state)
        fnAssertTrue(e == nil, "expecting e == nil")
        fnAssertTrue(v == 0, "expecting value 0")
        fnAssertTrue(state == "c=4,t=-1,v=6,items:", "state error")
    
        e,v = stack.Pop()
        fnAssertTrue(e != nil, "expecting e != nil")
    
        iter := stack.Iterator()
        fnAssertTrue(iter.More() == false, "expecting More() == false")
        e,v = iter.Next()
        fnAssertTrue(e != nil, "expecting e != nil")
    
        stack.Push(0)
        state = stack.String()
        t.Log(state)
        fnAssertTrue(state == "c=4,t=0,v=7,items:0", "state error")
        fnAssertTrue(iter.More() == false, "expecting More() == false")
        e,v = iter.Next()
        fnAssertTrue(e != nil, "expecting e != nil")
    
        stack.Push(1)
        state = stack.String()
        t.Log(state)
        fnAssertTrue(state == "c=4,t=1,v=8,items:0,1", "state error")
        iter = stack.Iterator()
        fnAssertTrue(iter.More() == true, "expecting More() == true")
        e,v = iter.Next()
        fnAssertTrue(e == nil && v  == 0, "expecting v == 0")
        e,v = iter.Next()
        fnAssertTrue(e == nil && v  == 1, "expecting v == 1")
    }
    

    测试输出

    $ go test -v stack_test.go 
    === RUN   Test_Stack
        stack_test.go:17: c=2,t=-1,v=0,items:
        stack_test.go:22: c=2,t=0,v=1,items:0
        stack_test.go:27: c=2,t=1,v=2,items:0,1
        stack_test.go:32: c=4,t=2,v=3,items:0,1,2
        stack_test.go:41: c=4,t=1,v=4,items:0,1
        stack_test.go:48: c=4,t=0,v=5,items:0
        stack_test.go:55: c=4,t=-1,v=6,items:
        stack_test.go:70: c=4,t=0,v=7,items:0
        stack_test.go:78: c=4,t=1,v=8,items:0,1
    --- PASS: Test_Stack (0.00s)
    PASS
    ok      command-line-arguments  0.003s
    
    

    IStack.go

    堆栈的接口

    package stack
    
    type IStack interface {
        Size() int
        IsEmpty() bool
        IsNotEmpty() bool
    
        Push(value interface{})
        Pop() (error, interface{})
        Peek() (error, interface{})
    
        Iterator() IStackIterator
        String() string
    }
    

    IStackIterator.go

    堆栈迭代器的接口

    package stack
    
    type IStackIterator interface {
        More() bool
        Next() (error,interface{})
    }
    

    tArrayStack.go

    基于自扩容数组的堆栈, 实现IStack接口

    package stack
    
    import (
        "errors"
        "fmt"
        "strings"
    )
    
    type tArrayStack struct {
        items []interface{}
        capacity int
        top int
        version int64
    }
    
    var gEmptyStackError = errors.New("empty stack")
    
    func NewArrayStack(capacity int) IStack {
        if capacity < 0 {
            capacity = 0
        }
    
        return &tArrayStack{
            items: make([]interface{}, capacity),
            capacity: capacity,
            top: -1,
        }
    }
    
    func (me *tArrayStack) Size() int {
        return me.top + 1
    }
    
    func (me *tArrayStack) IsEmpty() bool {
        return me.Size() <= 0
    }
    
    func (me *tArrayStack) IsNotEmpty() bool {
        return !me.IsEmpty()
    }
    
    func (me *tArrayStack) Push(value interface{}) {
        me.ensureCapacity(me.Size() + 1)
        me.top++
        me.items[me.top] = value
        me.version++
    }
    
    func (me *tArrayStack) ensureCapacity(size int) {
        if me.capacity >= size {
            return
        }
    
        for ;me.capacity<size; {
            me.capacity = maxInt(me.capacity*2, me.capacity+1)
        }
    
        newItems := make([]interface{}, me.capacity)
        copy(newItems, me.items)
        me.items = newItems
    }
    
    func maxInt(x, y int) int {
        if x >= y {
            return x
        }
        return y
    }
    
    func (me *tArrayStack) Pop() (error, interface{}) {
        if me.IsEmpty() {
            return gEmptyStackError, nil
        }
    
        it := me.items[me.top]
        me.items[me.top] = nil
        me.top--
    
        me.version++
        return nil, it
    }
    
    func (me *tArrayStack) Peek() (error, interface{}) {
        if me.IsEmpty() {
            return gEmptyStackError, nil
        }
    
        return nil, me.items[me.top]
    }
    
    func (me *tArrayStack) Iterator() IStackIterator {
        return newStackIterator(me)
    }
    
    func (me *tArrayStack) String() string {
        itemStrings := make([]string, me.Size())
        for i:=0;i<me.Size();i++ {
            itemStrings[i] = fmt.Sprintf("%v", me.items[i])
        }
    
        return fmt.Sprintf("c=%v,t=%v,v=%v,items:%s", me.capacity, me.top, me.version, strings.Join(itemStrings, ","))
    }
    

    tStackIterator.go

    免拷贝的堆栈迭代器, 实现IStackIterator接口

    package stack
    
    import "errors"
    
    type tStackIterator struct {
        stack *tArrayStack
        pos int
        version int64
    }
    
    var gNullStackError = errors.New("stack is null")
    var gNoMoreElementError = errors.New("no more element")
    var gConcurrentModificationError = errors.New("concurrent modification error")
    
    func newStackIterator(stack *tArrayStack) IStackIterator {
        return &tStackIterator{
            stack: stack,
            pos: -1,
            version: stack.version,
        }
    }
    
    func (me *tStackIterator) More() bool {
        if me.stack == nil {
            return false
        }
        if me.version != me.stack.version {
            return false
        }
        return me.pos < me.stack.top
    }
    
    func (me *tStackIterator) Next() (error, interface{}) {
        if me.stack == nil {
            return gNullStackError, nil
        }
        if me.version != me.stack.version {
            return gConcurrentModificationError, nil
        }
        if me.pos >= me.stack.top {
            return gNoMoreElementError, nil
        }
    
        me.pos++
        return nil, me.stack.items[me.pos]
    }
    

    (end)

    相关文章

      网友评论

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

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