内容简介：本文主要讲一讲栈这种非常基础的数据结构，以及其如何用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实现数据结构“栈”的三种实现，性能对比及应用示例》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Web Anatomy
Robert Hoekman Jr.、Jared Spool / New Riders / 2009-12-11 / USD 39.99
At the start of every web design project, the ongoing struggles reappear. We want to design highly usable and self-evident applications, but we also want to devise innovative, compelling, and exciting......一起来看看 《Web Anatomy》 这本书的介绍吧!
