数据结构

在用 Go 实现算法时，了解和使用适合的 数据结构 是高效编程的基础。以下是 Go 中常见的数据结构及其实现和应用场景：

---

1. 数组和切片 (Array & Slice)

Go 中数组是定长的，而切片是动态大小的数组。切片是最常用的数据结构之一。

示例：动态数组操作

package main

import "fmt"

func main() {
    arr := []int{1, 2, 3}
    arr = append(arr, 4) // 动态添加元素
    fmt.Println(arr)     // 输出: [1, 2, 3, 4]
}

应用场景：

• 顺序访问元素。
• 实现其他复杂数据结构，如栈、队列。

---

2. 栈 (Stack)

栈是一种 后进先出 (LIFO) 的数据结构，切片可轻松实现。

示例：栈的实现

package main

import "fmt"

type Stack struct {
    elements []int
}

func (s *Stack) Push(value int) {
    s.elements = append(s.elements, value)
}

func (s *Stack) Pop() (int, bool) {
    if len(s.elements) == 0 {
        return 0, false
    }
    val := s.elements[len(s.elements)-1]
    s.elements = s.elements[:len(s.elements)-1]
    return val, true
}

func main() {
    stack := &Stack{}
    stack.Push(1)
    stack.Push(2)
    fmt.Println(stack.Pop()) // 输出: 2, true
    fmt.Println(stack.Pop()) // 输出: 1, true
}

---

3. 队列 (Queue)

队列是一种 先进先出 (FIFO) 的数据结构，切片也可实现。

示例：队列的实现

package main

import "fmt"

type Queue struct {
    elements []int
}

func (q *Queue) Enqueue(value int) {
    q.elements = append(q.elements, value)
}

func (q *Queue) Dequeue() (int, bool) {
    if len(q.elements) == 0 {
        return 0, false
    }
    val := q.elements[0]
    q.elements = q.elements[1:]
    return val, true
}

func main() {
    queue := &Queue{}
    queue.Enqueue(1)
    queue.Enqueue(2)
    fmt.Println(queue.Dequeue()) // 输出: 1, true
    fmt.Println(queue.Dequeue()) // 输出: 2, true
}

---

4. 链表 (Linked List)

Go 没有内置链表，但可以通过结构体和指针实现。

示例：单链表

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type LinkedList struct {
    head *Node
}

func (l *LinkedList) Add(value int) {
    newNode := &Node{value: value}
    if l.head == nil {
        l.head = newNode
    } else {
        current := l.head
        for current.next != nil {
            current = current.next
        }
        current.next = newNode
    }
}

func (l *LinkedList) Display() {
    current := l.head
    for current != nil {
        fmt.Print(current.value, " -> ")
        current = current.next
    }
    fmt.Println("nil")
}

func main() {
    list := &LinkedList{}
    list.Add(1)
    list.Add(2)
    list.Add(3)
    list.Display() // 输出: 1 -> 2 -> 3 -> nil
}

---

5. 哈希表 (Hash Map)

Go 的内置 map 提供了高效的键值对存储。

示例：基本操作

package main

import "fmt"

func main() {
    hashMap := make(map[string]int)
    hashMap["a"] = 1
    hashMap["b"] = 2
    fmt.Println(hashMap["a"]) // 输出: 1
    fmt.Println(hashMap["c"]) // 输出: 0 (键不存在)
}

应用场景：

• 统计频率、快速查找。

---

6. 二叉树 (Binary Tree)

使用结构体和指针可以实现树结构。

示例：二叉树

package main

import "fmt"

type TreeNode struct {
    value int
    left  *TreeNode
    right *TreeNode
}

func (t *TreeNode) Insert(value int) {
    if value < t.value {
        if t.left == nil {
            t.left = &TreeNode{value: value}
        } else {
            t.left.Insert(value)
        }
    } else {
        if t.right == nil {
            t.right = &TreeNode{value: value}
        } else {
            t.right.Insert(value)
        }
    }
}

func InOrderTraversal(node *TreeNode) {
    if node != nil {
        InOrderTraversal(node.left)
        fmt.Print(node.value, " ")
        InOrderTraversal(node.right)
    }
}

func main() {
    root := &TreeNode{value: 5}
    root.Insert(3)
    root.Insert(7)
    root.Insert(4)
    root.Insert(6)

    InOrderTraversal(root) // 输出: 3 4 5 6 7
}

---

7. 图 (Graph)

图可以用 邻接表 或 邻接矩阵 实现。

示例：邻接表

package main

import "fmt"

type Graph struct {
    adjacencyList map[int][]int
}

func NewGraph() *Graph {
    return &Graph{adjacencyList: make(map[int][]int)}
}

func (g *Graph) AddEdge(from, to int) {
    g.adjacencyList[from] = append(g.adjacencyList[from], to)
}

func (g *Graph) Display() {
    for node, edges := range g.adjacencyList {
        fmt.Printf("%d -> %v\n", node, edges)
    }
}

func main() {
    graph := NewGraph()
    graph.AddEdge(1, 2)
    graph.AddEdge(1, 3)
    graph.AddEdge(2, 4)

    graph.Display()
    // 输出:
    // 1 -> [2 3]
    // 2 -> [4]
}

---

总结

以上涵盖了常用的数据结构实现。根据算法需求，可以选择合适的数据结构来优化性能，例如：

• 数组/切片：顺序存储。
• 栈/队列：临时存储、深度优先搜索、广度优先搜索。
• 链表：插入/删除频繁场景。
• 哈希表：快速查找。
• 树/图：递归和复杂关系建模。

如需更高效的实现，可结合 Go 的并发特性或第三方库扩展功能。