用Go语言实现栈

自定义栈的功能

本文旨在通过Go语言来实现一个自定义的栈，其功能包括入栈、出栈、栈容量查询、栈内元素个数查询、栈顶元素查询、是否空栈查询。

栈的初始化

首先创建一个能保存数据的结构体：

1	type Stack []interface{}

这里声明Stack为空接口类型的切片（Go语言之中的切片可以理解为一个长度可变的数组）。由于Go语言所有类型都实现了空接口，因此任意类型的值都可以存储在Stack之中。

栈的长度及容量

由于Stack的底层数据类型是一个切片，我们可以为其实现Len()和Cap()方法用来获取其长度和容量（Go语言之中首字母大写的方法为包外可访问的，类似于Java或者C++之中类的public方法）。

func (stack Stack) Len() int {  // 栈的长度
  return len(stack)
}

func (stack Stack) Cap() int {  // 栈的容量
  return cap(stack)
}

查询是否是空栈

1
2
3

func (stack Stack) IsEmpty() bool {
  return len(stack) == 0
}

栈的关键方法的实现（Push()、Pop()、Top()）

Push()方法的接收器为一个Stack类型的指针（Go指针的写法与C/C++类似，类型前面加上*号）。Go语言的所有方法参数都是值传递，接收器实际也是作为方法的一个参数传递进入方法的。如果传递一切片或者数组进方法，实际是将切片或数组的值拷贝了一份传入了方法之中，此时在方法之中对该切片或数组做的操作都不会影响方法之外的原始值。如果想要方法之中的操作影响到方法外的原始值，则应该使用指针作为参数，对指针的操作会直接反应到内存之中的原始值上去。在这里我们希望更改原始值（往原始的stack之中添加数据），所以接收器是一个指针。方法的参数是一个interface{}类型的值，也就是说该方法可以接受任意类型作为参数。方法的实现使用了内建函数append()，往切片对尾部中添加新值。

1
2
3

func (stack *Stack) Push(value interface{}) {
  *stack = append(*stack, value)
}

Top()方法返回一个任意类型的值以及一个error（是的没错，Go语言的方法可以返回多个值）。当stack为空时，返回一个空值和一个error类型的值（这里使用errors包的New()函数创建）。当stack不为空时，返回底层切片的最后一个值和一个空的error。

func (stack Stack) Top() (interface{},error) {
  if len(stack) == 0 {
        return nil, errors.New("Out of index, len is 0")
    }
    return stack[len(stack) - 1], nil
}

Pop()方法的接收器同样是一个Stack的指针。其中theStack[:len(theStack) - 1]这种写法，是Go中取子切片的方法，:两边是起始index和结束index。起始index为0时可以省略。结束的index也可以省略，省略时结束index为切片的len()值。

func (stack *Stack) Pop() (interface{},error) {
  theStack := *stack
  if len(theStack == 0) {
    return nil, error.New("Out of index, len is 0")
  }
  value := theStack[len(theStack)-1]
  *stack = theStack[:len(theStack)-1]
  return value, nil
}