2.3 泛型数据结构

泛型最常见的应用场景是数据结构。用泛型实现的容器类型安全、无装箱开销、代码复用度高。

Stack（栈）

package main

import "fmt"

type Stack[T any] struct {
    items []T
}

func NewStack[T any]() *Stack[T] {
    return &Stack[T]{items: make([]T, 0)}
}

func (s *Stack[T]) Push(v T) {
    s.items = append(s.items, v)
}

func (s *Stack[T]) Pop() (T, bool) {
    if len(s.items) == 0 {
        var zero T
        return zero, false
    }
    idx := len(s.items) - 1
    v := s.items[idx]
    s.items = s.items[:idx]
    return v, true
}

func (s *Stack[T]) Peek() (T, bool) {
    if len(s.items) == 0 {
        var zero T
        return zero, false
    }
    return s.items[len(s.items)-1], true
}

func (s *Stack[T]) Len() int     { return len(s.items) }
func (s *Stack[T]) IsEmpty() bool { return len(s.items) == 0 }

func main() {
    s := NewStack[int]()
    s.Push(1)
    s.Push(2)
    s.Push(3)

    for !s.IsEmpty() {
        v, _ := s.Pop()
        fmt.Println(v) // 3, 2, 1
    }
}

Queue（队列）

type Queue[T any] struct {
    items []T
}

func NewQueue[T any]() *Queue[T] {
    return &Queue[T]{}
}

func (q *Queue[T]) Enqueue(v T) {
    q.items = append(q.items, v)
}

func (q *Queue[T]) Dequeue() (T, bool) {
    if len(q.items) == 0 {
        var zero T
        return zero, false
    }
    v := q.items[0]
    q.items = q.items[1:]
    return v, true
}

func (q *Queue[T]) Len() int     { return len(q.items) }
func (q *Queue[T]) IsEmpty() bool { return len(q.items) == 0 }

// 避免内存泄漏的 Dequeue
func (q *Queue[T]) DequeueClean() (T, bool) {
    if len(q.items) == 0 {
        var zero T
        return zero, false
    }
    v := q.items[0]
    q.items[0] = *new(T) // 清除引用，帮助 GC
    q.items = q.items[1:]
    return v, true
}

LinkedList（链表）

type Node[T any] struct {
    Value T
    Next  *Node[T]
}

type LinkedList[T any] struct {
    head *Node[T]
    tail *Node[T]
    size int
}

func NewLinkedList[T any]() *LinkedList[T] {
    return &LinkedList[T]{}
}

func (l *LinkedList[T]) Append(v T) {
    node := &Node[T]{Value: v}
    if l.tail == nil {
        l.head = node
        l.tail = node
    } else {
        l.tail.Next = node
        l.tail = node
    }
    l.size++
}

func (l *LinkedList[T]) Prepend(v T) {
    node := &Node[T]{Value: v, Next: l.head}
    l.head = node
    if l.tail == nil {
        l.tail = node
    }
    l.size++
}

func (l *LinkedList[T]) RemoveFirst() (T, bool) {
    if l.head == nil {
        var zero T
        return zero, false
    }
    v := l.head.Value
    l.head = l.head.Next
    if l.head == nil {
        l.tail = nil
    }
    l.size--
    return v, true
}

func (l *LinkedList[T]) ForEach(fn func(T)) {
    for cur := l.head; cur != nil; cur = cur.Next {
        fn(cur.Value)
    }
}

func (l *LinkedList[T]) Len() int { return l.size }

// 泛型切片转换
func (l *LinkedList[T]) ToSlice() []T {
    result := make([]T, 0, l.size)
    for cur := l.head; cur != nil; cur = cur.Next {
        result = append(result, cur.Value)
    }
    return result
}

RingBuffer（环形缓冲区）

type RingBuffer[T any] struct {
    buf    []T
    head   int
    tail   int
    size   int
    cap    int
}

func NewRingBuffer[T any](capacity int) *RingBuffer[T] {
    return &RingBuffer[T]{
        buf: make([]T, capacity),
        cap: capacity,
    }
}

func (r *RingBuffer[T]) Push(v T) bool {
    if r.size == r.cap {
        return false // 满
    }
    r.buf[r.tail] = v
    r.tail = (r.tail + 1) % r.cap
    r.size++
    return true
}

func (r *RingBuffer[T]) Pop() (T, bool) {
    if r.size == 0 {
        var zero T
        return zero, false
    }
    v := r.buf[r.head]
    r.head = (r.head + 1) % r.cap
    r.size--
    return v, true
}

func (r *RingBuffer[T]) Peek() (T, bool) {
    if r.size == 0 {
        var zero T
        return zero, false
    }
    return r.buf[r.head], true
}

func (r *RingBuffer[T]) Len() int  { return r.size }
func (r *RingBuffer[T]) Cap() int  { return r.cap }
func (r *RingBuffer[T]) IsFull() bool  { return r.size == r.cap }
func (r *RingBuffer[T]) IsEmpty() bool { return r.size == 0 }

Set（集合）

type Set[T comparable] struct {
    items map[T]struct{}
}

func NewSet[T comparable]() *Set[T] {
    return &Set[T]{items: make(map[T]struct{})}
}

func NewSetFrom[T comparable](items []T) *Set[T] {
    s := NewSet[T]()
    for _, item := range items {
        s.Add(item)
    }
    return s
}

func (s *Set[T]) Add(v T) bool {
    if s.Has(v) {
        return false
    }
    s.items[v] = struct{}{}
    return true
}

func (s *Set[T]) Remove(v T) bool {
    if !s.Has(v) {
        return false
    }
    delete(s.items, v)
    return true
}

func (s *Set[T]) Has(v T) bool {
    _, ok := s.items[v]
    return ok
}

func (s *Set[T]) Len() int { return len(s.items) }

func (s *Set[T]) ToSlice() []T {
    result := make([]T, 0, len(s.items))
    for v := range s.items {
        result = append(result, v)
    }
    return result
}

func (s *Set[T]) ForEach(fn func(T)) {
    for v := range s.items {
        fn(v)
    }
}

// 集合运算
func (s *Set[T]) Union(other *Set[T]) *Set[T] {
    result := NewSet[T]()
    s.ForEach(func(v T) { result.Add(v) })
    other.ForEach(func(v T) { result.Add(v) })
    return result
}

func (s *Set[T]) Intersect(other *Set[T]) *Set[T] {
    result := NewSet[T]()
    s.ForEach(func(v T) {
        if other.Has(v) {
            result.Add(v)
        }
    })
    return result
}

func (s *Set[T]) Diff(other *Set[T]) *Set[T] {
    result := NewSet[T]()
    s.ForEach(func(v T) {
        if !other.Has(v) {
            result.Add(v)
        }
    })
    return result
}

LRU Cache（最近最少使用缓存）

import "container/list"

type CacheItem[K comparable, V any] struct {
    Key   K
    Value V
}

type LRUCache[K comparable, V any] struct {
    cap   int
    items map[K]*list.Element
    order *list.List
}

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
    return &LRUCache[K, V]{
        cap:   capacity,
        items: make(map[K]*list.Element),
        order: list.New(),
    }
}

func (c *LRUCache[K, V]) Get(key K) (V, bool) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.(*CacheItem[K, V]).Value, true
    }
    var zero V
    return zero, false
}

func (c *LRUCache[K, V]) Put(key K, value V) {
    if elem, ok := c.items[key]; ok {
        elem.Value.(*CacheItem[K, V]).Value = value
        c.order.MoveToFront(elem)
        return
    }

    if c.order.Len() >= c.cap {
        oldest := c.order.Back()
        if oldest != nil {
            c.order.Remove(oldest)
            delete(c.items, oldest.Value.(*CacheItem[K, V]).Key)
        }
    }

    item := &CacheItem[K, V]{Key: key, Value: value}
    elem := c.order.PushFront(item)
    c.items[key] = elem
}

func (c *LRUCache[K, V]) Len() int { return c.order.Len() }

数据结构选型指南

数据结构	适用场景	时间复杂度
Stack	DFS、括号匹配、撤销操作	Push/Pop O(1)
Queue	BFS、任务调度、消息缓冲	Enqueue/Dequeue O(1)
LinkedList	频繁插入/删除、大对象移动	插入/删除 O(1)
RingBuffer	固定容量流式处理、滑动窗口	Push/Pop O(1)
Set	去重、成员检查、集合运算	Add/Has O(1)
LRU Cache	缓存淘汰、热数据保留	Get/Put O(1)

要点总结

泛型数据结构 = 零成本抽象，编译后与手写特定类型代码性能一致
T any 用于容器类型（不对元素做任何操作）
T comparable 用于需要比较/查找的场景（Set、Map key）
多类型参数 [K comparable, V any] 用于 key-value 结构
零值用 var zero T 获取，适用于任何类型

2.3 泛型数据结构 ​

Stack（栈） ​

Queue（队列） ​

LinkedList（链表） ​

RingBuffer（环形缓冲区） ​

Set（集合） ​

LRU Cache（最近最少使用缓存） ​

数据结构选型指南 ​

要点总结 ​

2.3 泛型数据结构

Stack（栈）

Queue（队列）

LinkedList（链表）

RingBuffer（环形缓冲区）

Set（集合）

LRU Cache（最近最少使用缓存）

数据结构选型指南

要点总结