# README
Go Stack
一、这是什么?为什么选它?优势是啥?
这个项目是各种类型的栈的Go语言实现版本。
- 支持泛型,API使用更方便,避免类型强转
- 对每种类型的栈都提供了线程安全版本,使用的时候可以专注业务不需要再考虑锁的问题了
- 支持的栈类型更丰富,如果有更多有意思的栈,请提issues call me实现
二、安装
go get github.com/golang-infrastructure/go-stack
三、目前实现的栈
- ArrayStack[T any]
- SyncArrayStack[T any]
- LinkedStack[T any]
- SyncLinkedStack[T any]
- MinStack[T any]
- SyncMinStack[T any]
- MaxStack[T any]
- SyncMaxStack [T any]
一览表
Struct名称 | 线程安全性 | 阻塞性 | 特有特性 |
---|---|---|---|
ArrayStack[T any] | × | × | |
SyncArrayStack[T any] | √ | × | |
LinkedStack[T any] | × | × | |
SyncLinkedStack[T any] | √ | × | |
MinStack[T any] | × | × | O(1)获取栈中最小值 |
SyncMinStack[T any] | √ | × | O(1)获取栈中最小值 |
MaxStack[T any] | × | × | O(1)获取栈中最大值 |
SyncMaxStack [T any] | √ | × | O(1)获取栈中最大值 |
四、Interface: Stack
接口Stack[T any]
定义了一些所有的栈都会有的API。
入栈
Push(values ...T)
Example:
stack := NewArrayStack[int]()
stack.Push(1)
出栈
Pop() T
PopE() (T, error)
Pop Example:
type User struct {
}
stack := NewArrayStack[*User]()
fmt.Println(stack.Pop())
u := &User{}
stack.Push(u)
fmt.Println(stack.Pop())
// Output:
// <nil>
// &{}
PopE Example:
stack := NewArrayStack[int]()
element, err := stack.PopE()
if errors.Is(err, ErrStackEmpty) {
fmt.Println("stack empty!")
}
stack.Push(1)
element, err = stack.PopE()
if err != nil {
fmt.Println(err.Error())
return
}
fmt.Println(element)
// Output:
// stack empty!
// 1
查看栈顶元素
Peek() T
PeekE() (T, error)
Peek Example:
type User struct {
}
stack := NewArrayStack[*User]()
fmt.Println(stack.Peek())
u := &User{}
stack.Push(u)
fmt.Println(stack.Peek())
// Output:
// <nil>
// &{}
PeekE Example:
stack := NewArrayStack[int]()
element, err := stack.PeekE()
if errors.Is(err, ErrStackEmpty) {
fmt.Println("stack empty!")
}
stack.Push(1)
element, err = stack.PeekE()
if err != nil {
fmt.Println(err.Error())
return
}
fmt.Println(element)
// Output:
// stack empty!
// 1
判断栈是否空
IsEmpty() bool
IsNotEmpty() bool
IsEmpty Example:
stack := NewArrayStack[int]()
fmt.Println(stack.IsEmpty())
stack.Push(1)
fmt.Println(stack.IsEmpty())
// Output:
// true
// false
IsNotEmpty Example:
stack := NewArrayStack[int]()
fmt.Println(stack.IsNotEmpty())
stack.Push(1)
fmt.Println(stack.IsNotEmpty())
// Output:
// false
// true
栈中元素个数
Size() int
Example:
stack := NewArrayStack[int]()
stack.Push(1)
fmt.Println(stack.Size())
// Output:
// 1
清空栈
Clear()
Example:
stack := NewArrayStack[int]()
stack.Push(1)
fmt.Println(stack.Size())
stack.Clear()
fmt.Println(stack.Size())
// Output:
// 1
// 0
String
把栈转为String,一般用于debug之类的把栈中所有元素可视化。
Example:
stack := NewArrayStack[int]()
stack.Push(1)
fmt.Println(stack.String())
// Output:
// [1]
ArrayStack
基于数组实现的栈。
Example:
stack := NewArrayStack[int]()
fmt.Println(stack.String())
// Output:
// []
LinkedStack
基于链表实现的栈。
Example:
stack := NewLinkedStack[int]()
fmt.Println(stack.String())
// Output:
// []
五、最大栈 & 最小栈
MinStack & SyncMinStack
相较于Stack接口增加了两个方法用于O(1)获取栈中所有元素的最小值:
GetMin() T
GetMinE() (T, error)
GetMin Example:
stack := NewSyncMinStack[int](func(a, b int) int { return a - b })
_, err := stack.GetMinE()
assert.ErrorIs(t, err, ErrStackEmpty)
stack.Push(10)
stack.Push(7)
stack.Push(9)
element, err := stack.GetMinE()
assert.Nil(t, err)
assert.Equal(t, 7, element)
GetMinE Example:
stack := NewSyncMinStack[int](func(a, b int) int { return a - b })
_, err := stack.GetMinE()
if errors.Is(err, ErrStackEmpty) {
fmt.Println("stack empty!")
}
stack.Push(10)
stack.Push(7)
stack.Push(9)
element, err := stack.GetMinE()
if err != nil {
fmt.Println(err.Error())
return
}
fmt.Println(element)
// Output:
// stack empty!
// 7
MaxStack & SyncMaxStack
相较于Stack接口增加了两个方法用于O(1)获取栈中所有元素的最小值:
GetMax() T
GetMaxE() (T, error)
GetMax Example:
stack := NewSyncMaxStack[int](func(a, b int) int { return a - b })
_, err := stack.GetMaxE()
assert.ErrorIs(t, err, ErrStackEmpty)
stack.Push(10)
stack.Push(7)
stack.Push(9)
element, err := stack.GetMaxE()
assert.Nil(t, err)
assert.Equal(t, 10, element)
GetMaxE Example:
stack := NewSyncMaxStack[int](func(a, b int) int { return a - b })
_, err := stack.GetMaxE()
if errors.Is(err, ErrStackEmpty) {
fmt.Println("stack empty!")
}
stack.Push(10)
stack.Push(7)
stack.Push(9)
element, err := stack.GetMaxE()
if err != nil {
fmt.Println(err.Error())
return
}
fmt.Println(element)
// Output:
// stack empty!
// 10
TODO
- 为Stack实现JSON序列化接口
- 实现阻塞栈,因为仅当多个协程操作同一个栈时才需要考虑阻塞的情况,所以阻塞栈都是线程安全的。
# Functions
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
NewStack 默认是用数组实现的栈.
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
# Constants
EmptyStackTopIndex 当栈为空的时候栈顶的指针指向的下标位置.
# Variables
No description provided by the author
# Structs
ArrayStack 数组实现的栈.
LinkedStack 基于链表实现的栈.
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
Node 用于持有栈中元素的节点.
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
# Interfaces
Stack 定义栈的API.
# Type aliases
No description provided by the author