Go语言数据结构与算法-栈
2022/2/18 1:12:51
本文主要是介绍Go语言数据结构与算法-栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
栈
先进后出
应用
示例代码:
container/list标准库实现
package main import ( "container/list" "fmt" "sync" ) type Stack struct { l *list.List lock *sync.RWMutex } // NewStack 初始化 func NewStack() *Stack { l := list.New() lock := &sync.RWMutex{} return &Stack{l: l, lock: lock} } // Push 向栈内添加元素 func (s *Stack) Push(value interface{}) { s.lock.Lock() defer s.lock.Unlock() s.l.PushBack(value) } // Pop 删除栈顶元素 func (s *Stack) Pop() interface{} { s.lock.Lock() defer s.lock.Unlock() back := s.l.Back() if back == nil { return nil } return s.l.Remove(back) } // Peak 获取栈顶元素 func (s *Stack) Peak() interface{} { s.lock.RLock() defer s.lock.RUnlock() back := s.l.Back() if back == nil { return nil } return back.Value } // Len 获取栈长度 func (s *Stack) Len() int { s.lock.RLock() defer s.lock.RUnlock() return s.l.Len() } // Empty 栈是否为空 func (s *Stack) Empty() bool { s.lock.RLock() defer s.lock.RUnlock() return s.l.Len() == 0 } // TraversList 展开栈元素 func (s *Stack) TraversList() { s.lock.RLock() defer s.lock.RUnlock() tail := s.l.Back() for tail != nil { fmt.Printf("%v ", tail.Value) tail = tail.Prev() } fmt.Println() } func main() { l := NewStack() l.Push(1) l.Push(2) l.Push(3) l.TraversList() l.Pop() l.TraversList() } >>>>>> 3 2 1 2 1
自己动手实现
package main import ( "fmt" "sync" ) type ( node struct { value interface{} prev *node } MyStack struct { top *node lock *sync.RWMutex length int } ) func NewMyStack() *MyStack { return &MyStack{nil, &sync.RWMutex{}, 0} } func (s *MyStack) Push(value interface{}) { s.lock.Lock() defer s.lock.Unlock() n := &node{value, s.top} s.top = n s.length++ } func (s *MyStack) Pop() interface{} { s.lock.Lock() defer s.lock.Unlock() if s.length == 0 { return nil } n := s.top s.top = n.prev s.length-- return n.value } func (s *MyStack) Peak() interface{} { s.lock.RLock() defer s.lock.RUnlock() if s.length == 0 { return nil } return s.top.value } func (s *MyStack) Len() int { return s.length } func (s *MyStack) Empty() bool { return s.length == 0 } func (s *MyStack) Traverse() { s.lock.RLock() defer s.lock.RUnlock() prev := s.top for prev != nil { fmt.Printf("%v ", prev.value) prev = prev.prev } fmt.Println() } func main() { l := NewMyStack() l.Push(1) l.Push(2) l.Push(3) l.Traverse() l.Pop() l.Traverse() } >>>>>> 3 2 1 2 1
基准性能测试
package main import "testing" func BenchmarkStackPush(b *testing.B) { stack := NewStack() b.ResetTimer() for i := 0; i < b.N; i++ { stack.Push(i) } } func BenchmarkStackPop(b *testing.B) { stack := NewStack() for i := 0; i < b.N; i++ { stack.Push(i) } b.ResetTimer() for i := 0; i < b.N; i++ { stack.Pop() } } func BenchmarkMyStackPush(b *testing.B) { stack := NewMyStack() b.ResetTimer() for i := 0; i < b.N; i++ { stack.Push(i) } } func BenchmarkMyStackPop(b *testing.B) { stack := NewMyStack() for i := 0; i < b.N; i++ { stack.Push(i) } b.ResetTimer() for i := 0; i < b.N; i++ { stack.Pop() } } >>>>>>>go test -bench=. goos: windows goarch: amd64 pkg: stack cpu: Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz BenchmarkStackPush-8 4805720 262.1 ns/op BenchmarkStackPop-8 32913938 79.80 ns/op BenchmarkMyStackPush-8 8849811 152.2 ns/op BenchmarkMyStackPop-8 36459424 32.58 ns/op PASS ok stack 24.069s
通过上述性能测试可以看出自己实现性能更优
这篇关于Go语言数据结构与算法-栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21MongoDB资料:新手入门与初级应用指南
- 2024-09-20MongoDB教程:初学者必备指南
- 2024-09-05MongoDB入门:快速掌握NoSQL数据库基础
- 2024-08-28go 项目中怎么打印调试-icode9专业技术文章分享
- 2024-08-21swoole未来的发展前景与golang对比哪个更好-icode9专业技术文章分享
- 2024-08-16goland 已经下了中文插件了, 怎么设置成中文-icode9专业技术文章分享
- 2024-07-26使用 SendGrid 的 Go 客户端库能同时给多个邮箱发吗-icode9专业技术文章分享
- 2024-07-26使用 SendGrid 的 Go 客户端库时怎么设置header 和 标签tag 呢-icode9专业技术文章分享
- 2024-07-26SendGrid 对邮件的类别(Categories)和标签的数量有限制吗?-icode9专业技术文章分享
- 2024-07-17课程推荐《高性能GO企业级APM监控系统实战》