乐趣区

关于算法:手撸golang-基本数据结构与算法-栈

jiezi

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

    i := me.top
    me.top--
    me.version++
    return nil, me.items[i]
}

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)

退出移动版