参考:

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



方法1: 利用Golang的slice


1.go

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
58
59
60
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()
defer 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
}

func main() {

s := NewStack()

s.Push([]int{1, 4, 7})
s.Push([]int{5, 8, 9})
//fmt.Println(s)
s.Print()

s.Pop()
//fmt.Println(s)
s.Print()
}


1_test.go

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
package main

import (
"strconv"
"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
now := strconv.Itoa(i)
stack.Push("test" + now)
}

//fmt.Println(stack)
}

func Benchmark_Pop(b *testing.B) {
b.StopTimer() //类似时间锁,在StopTimer()和StartTimer()之见的代码,不计入测量
for i := 0; i < b.N; i++ { //use b.N for looping
now := strconv.Itoa(i)
stack.Push("test" + now)
}
b.StartTimer()
for i := 0; i < b.N; i++ { //use b.N for looping
stack.Pop()
}
}


关于基准测试,参考:

Go测试


go test -test.bench=".*" -benchmem -v

结果如下:

1
2
3
4
5
6
7
goos: darwin
goarch: amd64
pkg: 上级目录/当前目录
Benchmark_Push-4 3611212 379 ns/op 130 B/op 2 allocs/op
Benchmark_Pop-4 20186299 52.2 ns/op 0 B/op 0 allocs/op
PASS
ok 上级目录/当前目录 12.202s




方法2: 利用Golang的container/list内置包


关于Go的list,参见golang中list的源码


2.go

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package main

import (
"container/list"
"fmt"
"sync"
)

type Stack struct {
list *list.List
lock *sync.RWMutex
}

func NewStack() *Stack {
aList := list.New()
l := &sync.RWMutex{}
return &Stack{aList, 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
}


func main() {

s := NewStack()

s.Push([]int{1, 4, 7})
s.Push([]int{5, 8})
s.Push([]string{"a","d","f","g","w"})

fmt.Println(s)
fmt.Println(s.Len())

fmt.Println(s.list.Front().Value)
fmt.Println(s.list.Back().Value)

s.list.InsertBefore([]string{"cuishuang, dashen"},s.list.Back())

fmt.Println(s.Len())

fmt.Println(s.list.Back().Value)
fmt.Println(s.list.Back().Prev())
fmt.Println(s.list.Back().Next())

fmt.Println(s.Len())
s.Pop()
fmt.Println(s.Len())
fmt.Println(s.list.Front().Value)

}

输出为:

1
2
3
4
5
6
7
8
9
10
11
&{0xc00006a180 0xc000092000}
3
[1 4 7]
[a d f g w]
4
[a d f g w]
&{0xc00006a210 0xc00006a1e0 0xc00006a180 [cuishuang, dashen]}
<nil>
4
3
[1 4 7]


2_test.go

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
package main

import (
"strconv"
"testing"
)

var stack *Stack

func init() {
stack = NewStack()
}

func Benchmark_Push(b *testing.B) {
for i := 0; i < b.N; i++ { //use b.N for looping
now := strconv.Itoa(i)
stack.Push("test" + now)
}

//fmt.Println(stack)
}

func Benchmark_Pop(b *testing.B) {
b.StopTimer() //类似时间锁,在StopTimer()和StartTimer()之见的代码,不计入测量
for i := 0; i < b.N; i++ { //use b.N for looping
now := strconv.Itoa(i)
stack.Push("test" + now)
}
b.StartTimer()
for i := 0; i < b.N; i++ { //use b.N for looping
stack.Pop()
}
}

go test -test.bench=".*" -benchmem -v

结果如下:

1
2
3
4
5
6
7
goos: darwin
goarch: amd64
pkg: 上级目录/当前目录
Benchmark_Push-4 3439525 409 ns/op 85 B/op 3 allocs/op
Benchmark_Pop-4 20381214 54.8 ns/op 0 B/op 0 allocs/op
PASS
ok 上级目录/当前目录 14.733s




方法3: godoc的实现(自定义数据结构)


3.go

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package main

import (
"fmt"
"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++
}

func main() {

s := NewStack()

s.Push([]int{1, 4, 7, 0, 11, -3, 9})
s.Push([]int{5})
s.Push([]string{"a", "d", "f", "g", "w"})

fmt.Println(s.Peek())
fmt.Println(s.Len())

s.Pop()

fmt.Println(s.Peek())
fmt.Println(s.Len())

}

输出为:

1
2
3
4
[a d f g w]
3
[5]
2


3_test.go2_test.go

go test -test.bench=".*" -benchmem -v

结果如下:

1
2
3
4
5
6
7
goos: darwin
goarch: amd64
pkg: l上级目录/当前目录
Benchmark_Push-4 3468397 361 ns/op 69 B/op 3 allocs/op
Benchmark_Pop-4 24239797 52.3 ns/op 0 B/op 0 allocs/op
PASS
ok 上级目录/当前目录 16.249s




性能对比:


实现方式 push速度 pop速度 push内存分配 pop内存分配
基于slice 379 ns/op 52.2 ns/op 130 B/op 0 B/op
container/list链表 409 ns/op 54.8 ns/op 85 B/op 0 B/op
自定义数据结构 361 ns/op 52.3 ns/op 68 B/op 0 B/op


更多:

【golang】用container/list实现栈(Stack)

Google结果