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

国南之境 · · 1210 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

前言

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

栈的特性

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

栈实现的三种方式

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

1、利用Golang的slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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来说,其占用的内存,并不一定减少。

性能测试如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
2
3
4
5
6
7
8
$ 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内置包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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,这种方法也非常简单。

性能测试如下:

1
2
3
4
5
6
7
8
$ 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的实现参考(自定义数据结构实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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是线程安全的。

性能测试如下:

1
2
3
4
5
6
7
8
$ 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:

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

示例2:

1
2
Input: "([)]"
Output: false

参考实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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/

有疑问加站长微信联系(非本文作者)

本文来自:国南之境

感谢作者:国南之境

查看原文:Golang实现数据结构“栈”的三种实现,性能对比及应用示例

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1210 次点击  
加入收藏 微博
1 回复  |  直到 2020-06-13 09:44:17
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传