General Stack in Golang
背景
业务中需要用到 Golang 解析自定义的协议，类似于 { 和 } 这样的开启和闭合的符号需要用到栈来暂存开启符号以确定作用域的范围，当作用域结束时（遇到另一个匹配的闭合符号）再一一处理作用域中的内容，注意要支持递归的作用域。
需求
简单提取需求，栈需要有支持以下的方法：
- Size: 获知当前栈的长度；
- Push: 入栈元素，当栈满时要报错，当送入的元素类型不一致要
panic； - Pop: 弹栈元素，当栈空时要报错或告知用户返回的值是无效的；
- Clear: 重置各个字段和底层的数据结构（Array）
由此我们可以确定数据结构的对外接口：
// Stack implements Push & Pop
type Stack interface {
Push(interface{}) error
Pop() (interface{}, bool)
Clear()
Size() int
}实现篇
Stack
先定义栈的结构体
// stack is our internal implementation of a Stack. It is concurrent and type safe
type stack struct {
l *sync.Mutex
// slice to hold the data
s []interface{}
pos uint // current position
max uint // max size(0: unlimited; 1>: limited max size)
t reflect.Type // current type
}l: 用于保障结构的并发访问安全性s：底层数组。使用interface{}来表示栈能接收任意类型的元素pos: 记录当前的数组的索引max: 限定栈的最大深度或长度（0: 表示没有限制；> 1: 则施加限制）
t：在s的基础上进一步限定栈中只能有一种统一的类型
Size
首先实现最简单的 Size 方法，即直接代理到数组的 len 调用，加上简单的锁机制即可
// Size implements Seq
func (s *stack) Size() int {
s.l.Lock()
defer s.l.Unlock()
// return the size
return len(s.s)
}Clear
接着实现清空数组的方法：
- 清空数组，直接将原来的数组指向
nil，让 golang 的 GC 机制自动回收。注意不能用s.s = s.s[:0]这样相当于创建了切片，但是切片只是对数组的指针封装——原来的数组依然被引用着。 - 重置索引
- 重置元素类型
// Clear remove all elements
func (s *stack) Clear() {
s.l.Lock()
defer s.l.Unlock()
s.s = nil
s.t = nil
s.pos = 0
}Push
下一步，就是关键的入栈方法。
- 在方法体中，我们优先处理边界情况，如值为
nil或超过了长度限制（若启用了限制）。 - 检查栈元素的类型，这是为了防止栈中存在不同类型的元素。很明显，若是类型不统一，那么在 Pop 出来时，无法强制类型转换成想要的目标类型。（仅在栈中有多于 1 个元素时触发）
- 设置栈元素的类型。
- 将元素追加写到底层数组
- 更新索引
// Push implements Stack. It panics if v is nil or does not match the type
// of the value currently on the stack
func (s *stack) Push(v interface{}) (err error) {
if v == nil {
return errors.New("cannot push nil onto stack")
}
if s.max > 0 && s.pos == s.max {
return errors.New("stack is full")
}
// lock/unlock
s.l.Lock()
defer s.l.Unlock()
// type check
s.pushTypeCheck(v)
// type set
defer s.setType()
// push
s.s = append(s.s, v)
s.pos++
return
}
func (s *stack) pushTypeCheck(v interface{}) {
typ := reflect.TypeOf(v)
if s.t != nil && typ.PkgPath()+"#"+typ.Name() != s.t.PkgPath()+"#"+s.t.Name() {
panic("pushing different type onto stack")
}
}
func (s *stack) setType() {
switch s.pos {
case 0:
s.t = nil
case 1:
s.t = reflect.TypeOf(s.s[0])
}
}Pop
最后实现与 Push 对应的 Pop 方法。
// Pop implements Stack. It panics if the stack size is 0
func (s *stack) Pop() (v interface{}, ok bool) {
if len(s.s) == 0 {
return nil, false
}
// lock/unlock
s.l.Lock()
defer s.l.Unlock()
defer s.setType()
// pop
n := s.pos - 1
v, s.s = s.s[n], s.s[:n]
s.pos--
return v, true
}- 先判断临界条件，当栈空了，无法再弹出，返回状态标识告知用户。而且与前面相呼应的是，
Pop返回的值是不能Push入栈的值nil - 更新索引
- 获取当前值
- 更新底层数组的切片
- 更新索引
- 返回值和状态
总结
本文实现了一个通用类型的栈，无需为每一种元素类型实现一遍栈数据结构和方法。
在对外方法上，可 Push 任意元素到栈中，但是又不能混杂不同类型元素入栈，保障类型安全。
在初始化结构时，既可以设置无限入栈，也可以限制入栈次数，适合更多的场景。
