手撸golang 基本数据结构与算法 栈
手撸golang 基本数据结构与算法 栈
缘起
最近阅读<<我的第一本算法书>>(【日】石田保辉;宫崎修一)
本系列笔记拟采用golang练习之
栈
栈(也叫堆栈)也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新增的数据。栈就像是一摞书,拿到新书时我们会把它放在书堆的最上面,取书时也只能从最上面的新书开始取。像栈这种最后增加的数据最先被取出,即“后进先出”的结构,我们称为Last In First Out,简称LIFO。摘自 <<我的第一本算法书>>(【日】石田保辉;宫崎修一)目标
- 以数组为基础实现一个LIFO栈
- 可以指定数组的初始容量大小
- 当元素数量超过容量时, 自动以2倍率速度扩容
- 提供免拷贝的迭代器, 以遍历堆栈, 并能检测迭代版本错误(Concurrent Modification Error)
设计
- IStack: 堆栈的接口
- IStackIterator: 堆栈迭代器的接口
- tArrayStack: 基于自扩容数组的堆栈, 实现IStack接口
- tStackIterator: 免拷贝的堆栈迭代器, 实现IStackIterator接口
单元测试
stack_test.go
package data_structureimport ( 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)PASSok command-line-arguments 0.003sIStack.go
堆栈的接口
package stacktype IStack interface { Size() int IsEmpty() bool IsNotEmpty() bool Push(value interface{}) Pop() (error, interface{}) Peek() (error, interface{}) Iterator() IStackIterator String() string}IStackIterator.go
堆栈迭代器的接口
package stacktype IStackIterator interface { More() bool Next() (error,interface{})}tArrayStack.go
基于自扩容数组的堆栈, 实现IStack接口
package stackimport ( "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 stackimport "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)
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 手撸golang 基本数据结构与算法 栈
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 手撸golang 基本数据结构与算法 栈