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

栈的特性

栈是一种FILO类型的数据结构，FILO 即 Fisrt In Last Out，也就是先进后出，也可以说是后进先出。

栈实现的三种方式

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()
    }
}

1. 利用Golang的container/list内置包 ```go 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
3. godoc的实现参考（自定义数据结构实现）
<br />
```go
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是线程安全的。