golang 数据结构 栈的pop与push

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

数据实现类似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

本文来自:简书

感谢作者:VIL凌霄

查看原文:golang 数据结构 栈的pop与push

入群交流(和以上内容无关):Go中文网 QQ 交流群:729884609 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

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