#471
Golang container 包
Golang GoStdLib
2021-02-09
堆 Heap (container/heap)
- 最小堆
- 完全二叉树
- 父节点的值小于其子节点的值
type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
func Fix(h Interface, i int)
func Init(h Interface)
func Pop(h Interface) any
func Push(h Interface, x any)
func Remove(h Interface, i int) any
- 接口：
heap.Interface：定义了操作堆的基本方法，包括获取堆中元素数量、比较元素优先级、交换元素位置、添加元素到堆中、从堆中取出元素等。- 函数：
heap.Init(h Interface)：对一个实现了heap.Interface的堆进行初始化操作。heap.Push(h Interface, x interface{})：将元素x添加到堆h中。heap.Pop(h Interface) interface{}：从堆h中取出具有最高优先级的元素并返回。heap.Remove(h Interface, i int) interface{}：从堆h中移除指定索引i处的元素并返回。
使用方法：
- 定义一个用户自定义的类型，表示要存储在堆中的元素，并为该类型实现
heap.Interface接口的方法。 - 使用
heap.Init()对堆进行初始化，或者使用make()创建一个空的堆。 - 使用
heap.Push()将元素添加到堆中。 - 使用
heap.Pop()从堆中取出具有最高优先级的元素。 - 可选地，使用
heap.Remove()移除堆中的特定元素。
container/heap 包提供了一种方便而高效的方式来管理具有优先级的元素。它在各种场景中都有应用，例如任务调度、事件处理、优先级队列等。通过实现自定义的 heap.Interface 接口方法，可以根据具体需求定义元素的优先级比较方式，使堆适应不同的应用场景。
List (container/list)
type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element
func (l *List) Front() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v any, mark *Element) *Element
func (l *List) InsertBefore(v any, mark *Element) *Element
func (l *List) Len() int
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) PushBack(v any) *Element
func (l *List) PushBackList(other *List)
func (l *List) PushFront(v any) *Element
func (l *List) PushFrontList(other *List)
func (l *List) Remove(e *Element) any
container/list 包是 Go 语言标准库中的一个包，提供了双向链表（doubly linked list）的实现。双向链表是一种数据结构，其中每个节点都包含对前一个节点和后一个节点的引用。
container/list 包提供了 List 类型，该类型代表了一个双向链表。List 类型的对象可以用来存储和操作任意类型的元素。它支持在链表的前部和后部添加和删除元素，以及在链表中搜索、遍历和修改元素。
container/list 包的主要功能和方法包括：
List类型的方法：PushFront(v interface{}) *Element：在链表的前部插入一个值为v的元素，并返回该元素的指针。PushBack(v interface{}) *Element：在链表的后部插入一个值为v的元素，并返回该元素的指针。Remove(e *Element) interface{}：从链表中移除指定元素e，并返回该元素的值。Front() *Element：返回链表的第一个元素。Back() *Element：返回链表的最后一个元素。Len() int：返回链表中元素的数量。Element类型的方法：Next() *Element：返回当前元素的下一个元素。Prev() *Element：返回当前元素的前一个元素。Value() interface{}：返回当前元素的值。
使用 container/list 包的步骤通常是：
- 导入
container/list包。 - 创建一个新的链表对象：
myList := list.New() - 使用
PushFront()或PushBack()方法向链表中添加元素。 - 使用
Front()或Back()方法获取链表的第一个或最后一个元素。 - 使用
Next()或Prev()方法遍历链表中的元素。 - 使用
Remove()方法从链表中移除特定的元素。
container/list 包提供了一种简单而灵活的方式来管理和操作链表。它适用于需要频繁进行元素插入、删除和遍历的场景。然而，由于链表是一种指针结构，因此在随机访问和索引元素方面的性能较差。如果需要更高效的随机访问和索引操作，可以考虑使用切片（slice）或其他数据结构。
Ring (container/ring)
type Ring
func New(n int) *Ring
func (r *Ring) Do(f func(any))
func (r *Ring) Len() int
func (r *Ring) Link(s *Ring) *Ring
func (r *Ring) Move(n int) *Ring
func (r *Ring) Next() *Ring
func (r *Ring) Prev() *Ring
func (r *Ring) Unlink(n int) *Ring
container/ring 包是 Go 语言标准库中的一个包，提供了环形链表（circular list）的实现。环形链表是一种特殊的链表，其中最后一个节点的下一个节点是第一个节点，形成一个环状结构。
container/ring 包提供了 Ring 类型，该类型代表了一个环形链表。Ring 类型的对象可以用来存储和操作任意类型的元素。它支持在环形链表中向前和向后遍历、插入和删除元素，以及计算环形链表的长度。
container/ring 包的主要功能和方法包括：
Ring类型的方法：New(n int) *Ring：创建一个具有n个节点的新环形链表，并返回指向第一个节点的指针。Next() *Ring：返回下一个节点的指针。Prev() *Ring：返回上一个节点的指针。Move(n int) *Ring：将当前指针向前（负值）或向后（正值）移动n步，并返回新的指针。Link(s *Ring) *Ring：将当前环形链表连接到另一个环形链表s的前面，并返回连接后的环形链表。Unlink(n int) *Ring：从当前环形链表中移除下一个n个节点，并返回剩余的环形链表。Ring类型的属性：Len() int：返回环形链表中节点的数量。Value() interface{}：返回当前节点的值。
使用 container/ring 包的步骤通常是：
- 导入
container/ring包。 - 使用
New()方法创建一个新的环形链表，并指定节点的数量。 - 使用
Next()或Prev()方法在环形链表中遍历节点。 - 使用
Value()方法获取当前节点的值。 - 使用
Move()方法向前或向后移动指针。 - 使用
Link()方法将两个环形链表连接起来，或使用Unlink()方法移除节点。
container/ring 包提供了一种简单而灵活的方式来处理环形链表。它适用于需要在环形结构中进行元素遍历和操作的场景。可以使用环形链表来实现循环队列、轮转算法等应用。但是，与普通链表相比，环形链表的插入和删除操作相对较慢，因此如果需要频繁进行插入和删除操作，可能有更适合的数据结构选择。
