Golang实现数据结构“栈”的三种实现，性能对比及应用示例

前言

本文主要讲一讲栈这种非常基础的数据结构，以及其如何用Golang来实现的3种方式，简单用golang bench做一个性能比对，以字符串括号匹配的一个例子来看其一个简单的应用场景。

栈的特性

栈是一种FILO类型的数据结构，FILO 即 Fisrt In Last Out，也就是先进后出，也可以说是后进先出。它很像一个只有一个出口的站立的杯子，后边进入杯子的东西，会被最先取出来。

栈实现的三种方式

首先，实现栈，远非只有这三种方式，这里，只是举例3种相对比较典型的方式。每一种实现方式都很简单，也没什么需要太费周章讲的必要。

1、利用Golang的slice

package main

import (
	"fmt"
	"sync"
)

// Item the type of the stack
type Item interface{}

// ItemStack the stack of Items
type ItemStack struct {
	items []Item
	lock  sync.RWMutex
}

// New creates a new ItemStack
func NewStack() *ItemStack {
	s := &ItemStack{}
	s.items = []Item{}
	return s
}

// Pirnt prints all the elements
func (s *ItemStack) Print() {
	fmt.Println(s.items)
}

// Push adds an Item to the top of the stack
func (s *ItemStack) Push(t Item) {
	s.lock.Lock()
	s.lock.Unlock()
	s.items = append(s.items, t)
}

// Pop removes an Item from the top of the stack
func (s *ItemStack) Pop() Item {
	s.lock.Lock()
	defer s.lock.Unlock()
	if len(s.items) == 0 {
		return nil
	}
	item := s.items[len(s.items)-1]
	s.items = s.items[0 : len(s.items)-1]
	return item
}

此方式特点：

1. 利用Golang的Slice，足够简单。
2. 允许添加任意类型的元素。
3. Push和Pop有加锁处理，线程安全。
4. 在一些文章里（Reddit）提到，使用slice作为Stack的底层支持，速度更快。但是，slice最大的问题其实是存在一个共用底层数组的的问题，哪怕你不断的Pop，但可能对于Golang来说，其占用的内存，并不一定减少。

性能测试如下：

package main

import (
	"testing"
)

var stack *ItemStack

func init() {
	stack = NewStack()
}

func Benchmark_Push(b *testing.B) {
	for i := 0; i < b.N; i++ { //use b.N for looping
		stack.Push("test")
	}
}

func Benchmark_Pop(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ { //use b.N for looping
		stack.Push("test")
	}
	b.StartTimer()
	for i := 0; i < b.N; i++ { //use b.N for looping
		stack.Pop()
	}
}

$ go test -test.bench=".*" -benchmem -v
goos: darwin
goarch: amd64
pkg: test/test8
Benchmark_Push-4   	10000000	         222 ns/op	      94 B/op	       0 allocs/op
Benchmark_Pop-4    	20000000	        65.0 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	test/test8	7.644s

2、利用Golang的container/list内置包

package main

import (
	"container/list"
	"sync"
)

type Stack struct {
	list *list.List
	lock *sync.RWMutex
}

func NewStack() *Stack {
	list := list.New()
	l := &sync.RWMutex{}
	return &Stack{list, l}
}

func (stack *Stack) Push(value interface{}) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	stack.list.PushBack(value)
}

func (stack *Stack) Pop() interface{} {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	e := stack.list.Back()
	if e != nil {
		stack.list.Remove(e)
		return e.Value
	}
	return nil
}

func (stack *Stack) Peak() interface{} {
	e := stack.list.Back()
	if e != nil {
		return e.Value
	}

	return nil
}

func (stack *Stack) Len() int {
	return stack.list.Len()
}

func (stack *Stack) Empty() bool {
	return stack.list.Len() == 0
}

简单来说，container/list 是一个链表。用链表模拟栈，要么都向链表的最后做push和pop，要么都向链表的起点做push和pop，这种方法也非常简单。

性能测试如下：

$ go test -test.bench=".*" -benchmem -v  -count=1
goos: darwin
goarch: amd64
pkg: test/test10
Benchmark_Push-4   	 5000000	       222 ns/op	      48 B/op	       1 allocs/op
Benchmark_Pop-4    	20000000	        73.5 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	test/test10	10.837s

3、godoc的实现参考（自定义数据结构实现）

package main

import (
	"sync"
)

type (
	Stack struct {
		top    *node
		length int
		lock   *sync.RWMutex
	}
	node struct {
		value interface{}
		prev  *node
	}
)

// Create a new stack
func NewStack() *Stack {
	return &Stack{nil, 0, &sync.RWMutex{}}
}

// Return the number of items in the stack
func (this *Stack) Len() int {
	return this.length
}

// View the top item on the stack
func (this *Stack) Peek() interface{} {
	if this.length == 0 {
		return nil
	}
	return this.top.value
}

// Pop the top item of the stack and return it
func (this *Stack) Pop() interface{} {
	this.lock.Lock()
	defer this.lock.Unlock()
	if this.length == 0 {
		return nil
	}
	n := this.top
	this.top = n.prev
	this.length--
	return n.value
}

// Push a value onto the top of the stack
func (this *Stack) Push(value interface{}) {
	this.lock.Lock()
	defer this.lock.Unlock()
	n := &node{value, this.top}
	this.top = n
	this.length++
}

此方式特点：

1. 实现比较精巧，唯一需要理解的地方就是 node 结构体中，prev 的部分，它指向的是前一个node成员。
2. 允许添加任意类型的元素。
3. Push和Pop是线程安全的。

性能测试如下：

$ go test -test.bench=".*" -benchmem -v
goos: darwin
goarch: amd64
pkg: test/test9
Benchmark_Push-4   	10000000	         178 ns/op	      32 B/op	       1 allocs/op
Benchmark_Pop-4    	20000000	        75.5 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	test/test9	9.776s

对比

三种方式，总的来看，第三种基于自定义数据结构的实现方式，在push上效率最高，而且实现也比较精巧。个人其实是推荐使用这种方式的。其次，是基于 container/list 实现的方式。

特性对比	push速度	pop速度	push内存分配	pop内存分配
基于slice	222ns/op	65ns/op	94B/op	0B/op
container/list链表	222ns/op	73.5ns/op	48B/op	0B/op
自定义数据结构	178ns/op	75ns/op	32B/op	0B/op

栈数据结构的用途

栈这种数据结构通途很多。典型的应用，比如编辑器的撤销（undo）操作，以及校验字符匹配问题。下面主要举一个校验字符匹配的例子：

题目：给定一个包含了右侧三种字符的字符串， ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’，判断字符串是否合法。合法的判断条件如下：

1. 必须使用相同类型的括号关闭左括号。
2. 必须以正确的顺序关闭打开括号。

示例1：

Input: "()[]{}"
Output: true

示例2：

Input: "([)]"
Output: false

参考实现：

func isValid(s string) bool {
    // 括号对字典
    bracketsMap := map[uint8]uint8{'{': '}', '[': ']', '(': ')'}
    // 传入字符串为空则返回false（leetcode认为空字符串应该返回true，这里注意）
    if s == "" {
        return false
    }
    // 初始化栈
    stack := NewStack()
    for i := 0; i < len(s); i++ {
        // 如果栈中有数据，则进行比对，如果栈顶元素和当前元素匹配，则弹出，其他情况向栈中压入元素
        if stack.Len() > 0 {
            if c, ok := bracketsMap[stack.Peek().(uint8)]; ok && c == s[i] {
                stack.Pop()
                continue
            }
        }
        stack.Push(s[i])
    }
    // 到最后如果栈不为空，则说明未完全匹配掉（完全匹配的话，栈只能为空）
    return stack.Len() == 0
}

参考

1. https://flaviocopes.com/golang-data-structure-stack/
2. https://github.com/hishboy/gocommons/tree/master/lang
3. https://www.reddit.com/r/golang/comments/25aeof/building_a_stack_in_go_slices_vs_linked_list/