golang 数据结构 栈的pop与push

数据实现类似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.RWMutex
    head   *Node
    rear   *Node
    length int32
}

func NewPool() *Stack {
    return &Stack{}
}
// 出栈，取出链表中的第一个节点， （先进后出）
func (sel *Stack) Pop() *Node {
    sel.RLock()
    defer sel.RUnlock()
    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