内容简介：本文主要讲一讲栈这种非常基础的数据结构，以及其如何用Golang来实现的3种方式，简单用golang bench做一个性能比对，以字符串括号匹配的一个例子来看其一个简单的应用场景。栈是一种FILO类型的数据结构，FILO 即 Fisrt In Last Out，也就是先进后出，也可以说是后进先出。它很像一个只有一个出口的站立的杯子，后边进入杯子的东西，会被最先取出来。首先，实现栈，远非只有这三种方式，这里，只是举例3种相对比较典型的方式。每一种实现方式都很简单，也没什么需要太费周章讲的必要。
本文主要讲一讲栈这种非常基础的数据结构，以及其如何用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
}
此方式特点：
- 利用Golang的Slice，足够简单。
- 允许添加任意类型的元素。
- Push和Pop有加锁处理，线程安全。
- 在一些文章里（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++
}
此方式特点：
- 实现比较精巧，唯一需要理解的地方就是 node 结构体中，prev 的部分，它指向的是前一个node成员。
- 允许添加任意类型的元素。
- 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：
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
}
参考
以上所述就是小编给大家介绍的《Golang实现数据结构“栈”的三种实现，性能对比及应用示例》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
