缘起

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

栈

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

目标

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

设计

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

单元测试

stack_test.go

  1. package data_structure
  3. import (
  4.     st "learning/gooop/data_structure/stack"
  5.     "testing"
  6. )
  8. func Test_Stack(t *testing.T) {
  9.     fnAssertTrue := func(b bool, msg string) {
  10.         if !b {
  11.             panic(msg)
  12.         }
  13.     }
  15.     stack := st.NewArrayStack(2)
  16.     state := stack.String()
  17.     t.Log(state)
  18.     fnAssertTrue(state == "c=2,t=-1,v=0,items:", "state error")
  20.     stack.Push(0)
  21.     state = stack.String()
  22.     t.Log(state)
  23.     fnAssertTrue(state == "c=2,t=0,v=1,items:0", "state error")
  25.     stack.Push(1)
  26.     state = stack.String()
  27.     t.Log(state)
  28.     fnAssertTrue(state == "c=2,t=1,v=2,items:0,1", "state error")
  30.     stack.Push(2)
  31.     state = stack.String()
  32.     t.Log(state)
  33.     fnAssertTrue(state == "c=4,t=2,v=3,items:0,1,2", "state error")
  35.     e,v := stack.Peek()
  36.     fnAssertTrue(e == nil, "expecting e == nil")
  37.     fnAssertTrue(v == 2, "expecting value 2")
  39.     e,v = stack.Pop()
  40.     state = stack.String()
  41.     t.Log(state)
  42.     fnAssertTrue(e == nil, "expecting e == nil")
  43.     fnAssertTrue(v == 2, "expecting value 2")
  44.     fnAssertTrue(state == "c=4,t=1,v=4,items:0,1", "state error")
  46.     e,v = stack.Pop()
  47.     state = stack.String()
  48.     t.Log(state)
  49.     fnAssertTrue(e == nil, "expecting e == nil")
  50.     fnAssertTrue(v == 1, "expecting value 1")
  51.     fnAssertTrue(state == "c=4,t=0,v=5,items:0", "state error")
  53.     e,v = stack.Pop()
  54.     state = stack.String()
  55.     t.Log(state)
  56.     fnAssertTrue(e == nil, "expecting e == nil")
  57.     fnAssertTrue(v == 0, "expecting value 0")
  58.     fnAssertTrue(state == "c=4,t=-1,v=6,items:", "state error")
  60.     e,v = stack.Pop()
  61.     fnAssertTrue(e != nil, "expecting e != nil")
  63.     iter := stack.Iterator()
  64.     fnAssertTrue(iter.More() == false, "expecting More() == false")
  65.     e,v = iter.Next()
  66.     fnAssertTrue(e != nil, "expecting e != nil")
  68.     stack.Push(0)
  69.     state = stack.String()
  70.     t.Log(state)
  71.     fnAssertTrue(state == "c=4,t=0,v=7,items:0", "state error")
  72.     fnAssertTrue(iter.More() == false, "expecting More() == false")
  73.     e,v = iter.Next()
  74.     fnAssertTrue(e != nil, "expecting e != nil")
  76.     stack.Push(1)
  77.     state = stack.String()
  78.     t.Log(state)
  79.     fnAssertTrue(state == "c=4,t=1,v=8,items:0,1", "state error")
  80.     iter = stack.Iterator()
  81.     fnAssertTrue(iter.More() == true, "expecting More() == true")
  82.     e,v = iter.Next()
  83.     fnAssertTrue(e == nil && v  == 0, "expecting v == 0")
  84.     e,v = iter.Next()
  85.     fnAssertTrue(e == nil && v  == 1, "expecting v == 1")
  86. }

测试输出

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

IStack.go

堆栈的接口

  1. package stack
  3. type IStack interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Push(value interface{})
  9.     Pop() (error, interface{})
  10.     Peek() (error, interface{})
  12.     Iterator() IStackIterator
  13.     String() string
  14. }

IStackIterator.go

堆栈迭代器的接口

  1. package stack
  3. type IStackIterator interface {
  4.     More() bool
  5.     Next() (error,interface{})
  6. }

tArrayStack.go

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

  1. package stack
  3. import (
  4.     "errors"
  5.     "fmt"
  6.     "strings"
  7. )
  9. type tArrayStack struct {
  10.     items []interface{}
  11.     capacity int
  12.     top int
  13.     version int64
  14. }
  16. var gEmptyStackError = errors.New("empty stack")
  18. func NewArrayStack(capacity int) IStack {
  19.     if capacity < 0 {
  20.         capacity = 0
  21.     }
  23.     return &tArrayStack{
  24.         items: make([]interface{}, capacity),
  25.         capacity: capacity,
  26.         top: -1,
  27.     }
  28. }
  30. func (me *tArrayStack) Size() int {
  31.     return me.top + 1
  32. }
  34. func (me *tArrayStack) IsEmpty() bool {
  35.     return me.Size() <= 0
  36. }
  38. func (me *tArrayStack) IsNotEmpty() bool {
  39.     return !me.IsEmpty()
  40. }
  42. func (me *tArrayStack) Push(value interface{}) {
  43.     me.ensureCapacity(me.Size() + 1)
  44.     me.top++
  45.     me.items[me.top] = value
  46.     me.version++
  47. }
  49. func (me *tArrayStack) ensureCapacity(size int) {
  50.     if me.capacity >= size {
  51.         return
  52.     }
  54.     for ;me.capacity<size; {
  55.         me.capacity = maxInt(me.capacity*2, me.capacity+1)
  56.     }
  58.     newItems := make([]interface{}, me.capacity)
  59.     copy(newItems, me.items)
  60.     me.items = newItems
  61. }
  63. func maxInt(x, y int) int {
  64.     if x >= y {
  65.         return x
  66.     }
  67.     return y
  68. }
  70. func (me *tArrayStack) Pop() (error, interface{}) {
  71.     if me.IsEmpty() {
  72.         return gEmptyStackError, nil
  73.     }
  75.     i := me.top
  76.     me.top--
  77.     me.version++
  78.     return nil, me.items[i]
  79. }
  81. func (me *tArrayStack) Peek() (error, interface{}) {
  82.     if me.IsEmpty() {
  83.         return gEmptyStackError, nil
  84.     }
  86.     return nil, me.items[me.top]
  87. }
  89. func (me *tArrayStack) Iterator() IStackIterator {
  90.     return newStackIterator(me)
  91. }
  93. func (me *tArrayStack) String() string {
  94.     itemStrings := make([]string, me.Size())
  95.     for i:=0;i<me.Size();i++ {
  96.         itemStrings[i] = fmt.Sprintf("%v", me.items[i])
  97.     }
  99.     return fmt.Sprintf("c=%v,t=%v,v=%v,items:%s", me.capacity, me.top, me.version, strings.Join(itemStrings, ","))
  100. }

tStackIterator.go

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

  1. package stack
  3. import "errors"
  5. type tStackIterator struct {
  6.     stack *tArrayStack
  7.     pos int
  8.     version int64
  9. }
  11. var gNullStackError = errors.New("stack is null")
  12. var gNoMoreElementError = errors.New("no more element")
  13. var gConcurrentModificationError = errors.New("concurrent modification error")
  15. func newStackIterator(stack *tArrayStack) IStackIterator {
  16.     return &tStackIterator{
  17.         stack: stack,
  18.         pos: -1,
  19.         version: stack.version,
  20.     }
  21. }
  23. func (me *tStackIterator) More() bool {
  24.     if me.stack == nil {
  25.         return false
  26.     }
  27.     if me.version != me.stack.version {
  28.         return false
  29.     }
  30.     return me.pos < me.stack.top
  31. }
  33. func (me *tStackIterator) Next() (error, interface{}) {
  34.     if me.stack == nil {
  35.         return gNullStackError, nil
  36.     }
  37.     if me.version != me.stack.version {
  38.         return gConcurrentModificationError, nil
  39.     }
  40.     if me.pos >= me.stack.top {
  41.         return gNoMoreElementError, nil
  42.     }
  44.     me.pos++
  45.     return nil, me.stack.items[me.pos]
  46. }

(end)