实现栈结构的常规思路是采用链式结构，用过指针和栈有关的属性值实现、控制栈的接口和规范。另外一种思路是采用数据组，把栈操作的数据保存在数组中。但采用数据的一个特点是，数组的大小是确定的，当需要改变数据的存储容量时需要重新分配内存和拷贝数据。

基于go内置的数据结构slice，可以实现灵活的栈结构。类实地，实现队列、堆、优先队列都可以使用Slice结构存储元素。下面给出栈的实现。

定义栈结构

1
2
3
4
5
type Stack struct {
    s      []int
    top    int
    length int
}

初始化栈结构

1
2
3
4
5
6
func NewStack() *Stack {
    stack := &Stack{
        s: make([]int, 0, 10),
    }
    return stack
}

栈操作

为了简洁，如果遇到空栈，Pop和Top默认返回0值，改为弹出异常也不难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func (s *Stack) Push(item int) {
    s.s = append(s.s, item)
    s.top = item
    s.length += 1
}

func (s *Stack) Empty() bool {
    return s.length == 0
}

func (s *Stack) Pop() int {
    if s.Empty() {
        return 0
    }
    item := s.s[s.length-1]
    s.s = s.s[:s.length-1]
    s.length -= 1
    return item
}

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

func (s *Stack) Top() int {
    if s.Empty() {
        return 0
    } else {
        return s.top
    }
}

测试栈

1
2
3
4
5
6
7
8
9
10
func TestStack() {
    stack := NewStack()
    for i := 0; i <= 10; i++ {
        stack.Push(i)
    }

    for !stack.Empty() {
        fmt.Println(stack.Pop())
    }
}

结语

实现栈结构确实不难，但需要分析使用场景和实现的储存结构。这里采用了Slice实现，本质上就是数组，一篇连续的内存空间，在存储上更紧凑。关于栈的链式结构实现见栈的链式结构实现（Go语言版）。