数据实现类似C语言的实现方式。我这里使用两种方式实现 栈的 pop 和 push。
第一种使用 struct 实现
type Node struct {
value interface{}
previous *Node // 前一个节点
Next *Node // 下一个节点
}
func (sel *Node) Value() interface{} {
return sel.value
}
func newNode(val interface{}) *Node {
return &Node{value: val}
}
type Stack struct {
sync.Mutex
head *Node
rear *Node
length int32
}
func NewPool() *Stack {
return &Stack{}
}
// 出栈，取出链表中的第一个节点， （先进后出）
func (sel *Stack) Pop() *Node {
sel.Lock()
defer sel.Unlock()
val := &Node{
value: sel.head.value,
}
// 头节点指向当前节点的下一个节点
sel.head = sel.head.Next
// 这里使用了 lock 可以不使用 atomic 原子操作
atomic.AddInt32(&sel.length, -1)
return val
}
func (sel *Stack) Push(v interface{}) {
sel.Lock()
defer sel.Unlock()
sel.push(v)
}
// 插入新节点到头部
func (sel *Stack) push(v interface{}) {
top := newNode(v)
if sel.length == 0 {
sel.head = top
sel.rear = sel.head
}
// 新节点指向当前头节点
top.Next = sel.head
// 当前头节点的前一个节点指向新节点
sel.head.previous = top
// 改变当前头节点地址为新节点地址
sel.head = top
atomic.AddInt32(&sel.length, 1)
}
// 取出链表中最早的节点（先进先出）
func (sel *Stack) Shift() *Node {
val := sel.rear
sel.rear = sel.rear.previous
sel.rear.Next = nil
val.Next = nil
val.previous = nil
return val
}
func (sel *Stack) Length() int32 {
return sel.length
}
测试代码：
func TestPool_Push(t *testing.T) {
po := NewPool()
num := 100000000
start := time.Now().UnixNano()
for i := 0; i < num; i++ {
po.Push(i)
}
end := time.Now().UnixNano()
fmt.Println("入栈时间：", (end-start)/1e6)
fmt.Println("长度：", po.Length())
start = time.Now().UnixNano()
for i := 0; i < num; i++ {
po.Pop()
}
end = time.Now().UnixNano()
fmt.Println("出栈时间：", (end-start)/1e6)
}
测试结果：
=== RUN TestPool_Push
入栈时间： 14638
长度： 100000000
出栈时间： 10500
--- PASS: TestPool_Push (25.14s)
PASS
第二种方法使用 slice 实现 pop 和 push
实现代码如下：
type ItemNode []interface{}
type StackSlice struct {
items ItemNode
length int
capacity int
sync.RWMutex
}
func NewStackSlice(cp int) *StackSlice {
return &StackSlice{
items: make(ItemNode, 0, cp),
capacity: cp,
}
}
func (sel *StackSlice) Pop() interface{} {
sel.Lock()
defer sel.Unlock()
length := len(sel.items)
if length == 0 {
return nil
}
item := sel.items[length-1]
sel.items = sel.items[:length-1]
return item
}
func (sel *StackSlice) Push(val interface{}) {
sel.Lock()
defer sel.Unlock()
sel.items = append(sel.items, val)
}
func (sel *StackSlice) Shift() interface{} {
sel.Lock()
defer sel.Unlock()
length := len(sel.items)
if length == 0 {
return nil
}
item := sel.items[0]
if length > 1 {
sel.items = sel.items[1:length]
} else {
sel.items = make([]interface{}, 0, sel.capacity)
}
return item
}
测试代码：
func TestStackSlice_Push2(t *testing.T) {
num := 100000000
po := NewStackSlice(100000000)
start := time.Now().UnixNano()
for i := 0; i < num; i++ {
po.Push(i)
}
end := time.Now().UnixNano()
fmt.Println("入栈时间：", (end-start)/1e6)
start = time.Now().UnixNano()
for i := 0; i < num; i++ {
po.Pop()
}
end = time.Now().UnixNano()
fmt.Println("出栈时间：", (end-start)/1e6)
}
测试结果：
=== RUN TestStackSlice_Push2
入栈时间： 7312
出栈时间： 4828
--- PASS: TestStackSlice_Push2 (12.28s)
PASS
对于第二种方法，把 capacity 缩短或者改为 0
func TestStackSlice_Push2(t *testing.T) {
num := 100000000
// 这里修改 capacity 为 0
po := NewStackSlice(0)
start := time.Now().UnixNano()
for i := 0; i < num; i++ {
po.Push(i)
}
end := time.Now().UnixNano()
fmt.Println("入栈时间：", (end-start)/1e6)
start = time.Now().UnixNano()
for i := 0; i < num; i++ {
//fmt.Println(po.Shift())
po.Pop()
}
end = time.Now().UnixNano()
fmt.Println("出栈时间：", (end-start)/1e6)
}
测试结果：
=== RUN TestStackSlice_Push2
入栈时间： 18999
出栈时间： 4835
--- PASS: TestStackSlice_Push2 (23.83s)
PASS
如果slice 的容量缩短了，时间就会慢很多，因为 slice 容量不够的情况下，会自动扩展容量，并且会有数据拷贝。
总结
性能测试代码如下
var po = NewPool()
var poSlice = NewStackSlice(100000000)
func BenchmarkStack_Push(b *testing.B) {
for i := 0; i < b.N; i++ {
po.Push(i)
}
}
func BenchmarkStack_Pop(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
po.Push(i)
}
b.StartTimer()
for i := 0; i < b.N; i++ {
po.Pop()
}
}
func BenchmarkStackSlice_Pop(b *testing.B) {
for i := 0; i < b.N; i++ {
poSlice.Push(i)
}
}
func BenchmarkStackSlice_Push(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
poSlice.Push(i)
}
b.StartTimer()
for i := 0; i < b.N; i++ {
poSlice.Pop()
}
}
测试结果： go test -bench=".*" -run=None -benchmem
BenchmarkStack_Push-4 20000000 103 ns/op 40 B/op 1 allocs/op
BenchmarkStack_Pop-4 20000000 132 ns/op 32 B/op 1 allocs/op
BenchmarkStackSlice_Pop-4 20000000 68.9 ns/op 8 B/op 0 allocs/op
BenchmarkStackSlice_Push-4 30000000 49.1 ns/op 0 B/op 0 allocs/op
- 第一种使用struct实现 pop 和 push,是可以自动扩展且不需要关心容量，但是数据较慢。
- 第二种使用slice 实现 pop 和 push, 在容量足够的情况下速度是比第一种快了很多，但是如果容量不足会降低入栈的速度。slice 方法实现的出栈速度是不受容量影响的，比struct实现的要快很多。
但是也有网友给出不同的测试结果 https://studygolang.com/articles/19828?fr=sidebar
网友评论