继上文基于的slice实现的栈式操作后，本文给出栈的链式存储结构的实现方式。

首先我们要定义结点，处于通用性考虑，我们希望每个结点能存储不同的数据类型，于是我们使用interface{}，它相当于一个包装，兼容不同的数据类型，解包的时候（拆解出具体的类型）使用如下的方式(interface{}).(*Node)。

结点定义

1
2
3
4
type Node struct {
    value interface{}
    next *Node
}

栈结构定义

1
2
3
4
type Stack struct {
    top    *Node
    length int
}

栈的初始化

初始化的栈是个空栈，top指向栈底，即nil。Go语言中，int初始化默认为0。

1
2
3
4
5
6
7
func NewStack() *Stack {
    stack := &Stack{
        top:    nil,
        length: 0,
    }
    return stack
}

Empty、Top、Len

这个三个操作都和Stack结构的熟悉直接相关，不难实现。在空栈中操作Top并不会出错，而是返回nil表明栈是空。

1
2
3
4
5
6
7
8
9
10
11
func (s *Stack) Empty() bool {
    return s.top == nil
}

func (s *Stack) Len() int {
    return s.length
}

func (s *Stack) Top() interface{} {
    return s.top
}

Push、Pop

Push和Pop的原理相似。Push操作把新结点的next指针指向栈顶结点，修改top指针为新结点。Pop需要对空栈进行检测，因为空栈情况top值为nil，不存在next指针。在栈非空的情况，把top指针指向栈顶结点的next指针指向的结点（允许nil），然后返回栈顶元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (s *Stack) Push(value interface{}) {
    node := &Node{
        value: value,
        next:  s.top,
    }

    s.top = node
}

func (s *Stack) Pop() interface{} {
    if s.Empty() {
        return nil
    }
    item := s.top
    s.top = s.top.next
    return item
}

我们编写简单的测试用例。

1
2
3
4
5
6
7
8
9
func main() {
    stack := NewStack()
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Println(stack.Pop().(*Node).value)
    fmt.Println(stack.Pop().(*Node).value)
    fmt.Println(stack.Pop().(*Node).value)
}

以上就是栈的链式结构实现。相比slice结构的实现，链式结构实现更消耗空间，但免去了slice底层数组因容量有限而reslice过程。如果我们已经知道栈的大小上限，优先使用slice方式，否则使用链式结构绕开reslice过程。

完。