内容简介:本文主要讲一讲栈这种非常基础的数据结构,以及其如何用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实现数据结构“栈”的三种实现,性能对比及应用示例》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
C#图解教程
索利斯 (Daniel M.Solis) / 姚琪琳、苏林、朱晔 / 人民邮电出版社 / 2013-7-1 / CNY 89.00
本书是广受赞誉的C# 图解教程的最新版本。作者在本书中创造了一种全新的可视化叙述方式,以图文并茂的形式、朴实简洁的文字,并辅以大量表格和代码示例,全面、直观地阐述了C# 语言的各种特性。新版本除了精心修订旧版内容外,还全面涵盖了C# 5.0 的新增特性,比如异步编程、调用者信息、case 表达式、带参数的泛型构造函数、支持null 类型运算等。通过本书,读者能够快速、深入理解C#,为自己的编程生涯......一起来看看 《C#图解教程》 这本书的介绍吧!