算法-算法与方法论

这里将从实际问题和方法论两者结合来分析下列问题：

• 大文件小内存排序（分支+败者树+多路归并）
• 10万单词，找出重复最高的几个（map，频次，堆排序）
• 一个非常大的数组，让其中两个数想加等于1000怎么算
• 10万个数，从小到大输出（分治法、内存排序、多路归并）
• 10亿个数，找出最大的10个（大小为10的小根堆，分治法与多路归并）
• 给每个组分配不同的IP段，怎么设计一种结构使的快速得知IP是哪个组的（redis的zset）

以及基础知识：

• 二分查找法
• 滑动窗口双指针法
• 编码中一般会用到哪些数据结构
• 常用的基本排序算法，比如快速排序
• 单链表和数组相比, 有什么优缺点
• 单链表、双向链表、循环链表的设计和区别
• 如何判断两个无环单链表有没有交叉点
• 如何判断一个单链表有没有环, 并找出入环点

以及基础数据结构的实现：

• 栈、后入先出
• 队列、先入先出
• 集合、与map关系
• 单链表、双向链表、环
• 堆、堆排序
• 树、二叉树、平衡树、红黑树
• 环形缓冲区（有界数组）、首尾指针
• lru cache（双向链表）、淘汰策略
• 图、邻接表、邻接矩阵、最短路径
• 哈希（散列）、链地址、rehash
• 跳表、分层
• Channel信道
• 等

基础概念

时间复杂度，省略常数时：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，「但我们统一说 logn，也就是忽略底数的描述」。

基本排序算法

基本排序算法可见：十大排序算法，但是有些算法已经被淘汰，这里只说关键的快速排序（及其衍生算法冒泡排序）、堆排序、多路归并

冒泡排序（用来引出快速排序）

将无序表中的所有记录，通过两两比较关键字并交换位置，得出升序序列或者降序序列。

在每一轮的逐个两两比较结束后，将一个最大或最小的数字放到排序完的位置。

通过一趟趟的比较，一个个的最大或最小值被找到并移动到相应位置，直到检测到表中数据已经有序，或者比较次数等同于表中含有记录的个数，排序结束，这就是起泡排序。

注意：有多少元素，就要经过多少趟排序。每趟排序的最后一次比较是l-1-i 与 l-1-i-1，其中l-1是最后一个元素的索引，i是第i趟排序，写错可能会导致数组越界。

技巧：Go提供 a, b = b, a 的写法交换变量，不用自己定义tmp变量。否则如果用C语言，就要需要写一个swap函数，并且传入指针了。

分析：时间复杂度同实际表中数据的无序程度有关。时间消耗分为比较和交换，总体复杂度O(n^2)

package main

import "fmt"

func main() {
    ints := []int{49,38,65,97,76,13,27,49}
    
    l := len(ints)  // 有多少个元素，就会经过多次趟排序
    for i := 0; i < l; i = i + 1 {
        for j := 0; j < l - 1 - i; j++ { // 每趟排序都从0号索引开始，找出一个最大的放到l-1号索引。所以第1趟排序的最后一次比较是让索引位 l-1（最后一位） 与 l-2（倒数第二位） 比较，加上第i趟也就是让 l-1-i 与 l-1-i-1 比较。
            if ints[j] > ints[j+1] {
                ints[j], ints[j+1] = ints[j+1], ints[j]
            }
        }
    }
    fmt.Println(ints)
}

快速排序

快速排序算法详解（原理、实现和时间复杂度)

快排是对冒泡的改进，采用了 分治法 的思想，可以用 递归 简化代码。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

在待排序的数列中，我们首先要找一个数字作为基准数（pivot，可以随便选一个）。为了方便，我们一般选择第 1 个数字作为基准数。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

以 47、29、71、99、78、19、24、47 的待排序的数列为例进行排序，为了方便区分两个 47，我们对后面的 47 增加一个下画线，即待排序的数列为 47、29、71、99、78、19、24、47。

首先我们需要在数列中选择一个基准数，我们一般会选择中间的一个数或者头尾的数，这里直接选择第 1 个数 47 作为基准数，接着把比 47 小的数字移动到左边，把比 47 大的数字移动到右边，对于相等的数字不做移动。所以实际上我们需要找到中间的某个位置 k，这样 k 左边的值全部比 k 上的值小，k 右边的值全部比 k 上的值大。

接下来开始移动元素。怎么移动呢？其实冒泡排序也涉及对元素的移动，但是那样移动起来很累，比如把最后一个元素移动到第 1 个，就需要比较 n-1 次，同时交换 n-1 次，效率很低。其实，只需把第 1 个元素和最后一个元素交换就好了，这种思想是不是在排序时可以借鉴呢？之前说快速排序就是对冒泡排序的一个改进，就是这个原因。

快速排序的操作是这样的：首先从数列的右边开始往左边找，我们设这个下标为 i，也就是进行减减操作（i–），找到第 1 个比基准数小的值，让它与基准值交换；接着从左边开始往右边找，设这个下标为 j，然后执行加加操作（j++），找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大。

但是由于快速排序需要对数列中的元素来回移动，有时还是会改变相对顺序的（比如 47 在第 1 轮的移动过程中就被移动到 47 的右边了），所以快速排序并不是一个稳定的算法。

将数学逻辑转换为代码执行逻辑

/*
每次分组过程：
基准指针初始为pp = 0，基准值固定为p=ints[pp]=47，[]内为已排序元素
原数组：47, 29, 71, 99, 78, 19, 24, 47
初始: 47(i,pp), 29, 71, 99, 78, 19, 24, 47(j)
j比较p不交换：47(i,pp), 29, 71, 99, 78, 19, 24, [47(j)] // 因为pp初始化在第一个位置，所以从另外一边也就是j开始比较
j递减
j比较p交换：[24(i)], 29, 71, 99, 78, 19, 47(j,pp), [47]
i递增   // 编码需要一些技巧，见：循环中让两个loop互相转换可控的编码思路
i比较p不交换：[24, 29(i)], 71, 99, 78, 19, 47(j,pp), [47]
i递增
i比较p交换：[24, 29], 47(i,pp), 99, 78, 19, [71(j), 47]
j递减
j比较p交换：[24, 29, 19(i)], 99, 78, 47(j,pp), [71, 47]
i递增
i比较p交换：[24, 29, 19], 47(i,pp), 78, [99(j), 71, 47]
j递减
j比较p不交换：[24, 29, 19], 47(i,pp), [78(j), 99, 71, 47]
j递减
[24, 29, 19], 47(i,j,pp), [78, 99, 71, 47]，i<j条件不成立，一轮排序结束，大小堆已区分。
注意：在每次交换之前，容易忽略掉i<j这个条件，这样会因为ij的自增或自减导致已经分好组的元素再次被交换回来。
*/

package main

import "fmt"

func main() {
    arr := []int{47, 29, 71, 99, 78, 19, 24, 47}
    // arr := []int{2, 44, 4, 8, 33, 1, 22, -11, 6, 34, 55, 54, 9}
    var ints = make([]int, len(arr))
    ints = arr[:]
    
    quick_sort(ints)
    fmt.Println(ints)
}

func quick_sort(ints []int) {
    i := 0
    l := len(ints)
    j := l - 1
    pivot_pointer := 0 // 分组最终目的就是获得pivot的最终位置索引
    pivot := ints[pivot_pointer] // 每次分组都用第一个元素作为pivot
    for i < j { // 注意循环写法
        for i < j && ints[j] > pivot { // 注意for内套for并且加条件
            j = j - 1
        }
        if i < j { // 必须加条件判断，避免此时i=j
            ints[j], ints[i] = ints[i], ints[j]
            i = i + 1 // 操作对象从j变i
            pivot_pointer = j // 记录pivot所在位置
        }

        for i < j && ints[i] < pivot {
            i = i + 1
        }
        if i < j {
            ints[i], ints[j] = ints[j], ints[i]
            j = j - 1
            pivot_pointer = i
        }
    }
    fmt.Println(ints)
    fmt.Println(pivot_pointer)
    if (pivot_pointer > 0) { // 避免对过少或无效的数据执行递归
        quick_sort(ints[0:pivot_pointer]) // 含左不含右，避开中间的pivot_pointer
    }
    if (pivot_pointer+1 < l) {
        quick_sort(ints[pivot_pointer+1:l])
    }
}

编码技巧和思路：

• 当数据量太大时，可以用一部分数据分析逻辑，并转换成代码执行步骤，然后在代码中再确定好条件和数据边界问题。
• 从数组生成切片时一定要先make初始化内存，否则报错
• 分治+递归的目的是通过pivot_pointer索引把数组分成大小两部分，再分别递归，所以一轮递归的目的就是找到pivot_pointer
• pivot变量可以固定为第一个值，这样就避免在递归函数中插入新的pivot位置了
• 循环时，需要让i、j代表的元素与pivot做比较，小的放到左边，大的放到右边，放置操作可以用i、j值的”交换”操作以及i、j的自增自减来替代，直到除了pivot外所有元素都被放到了左右堆中
• 循环” ;for condition; “可以简写成”for condition”
• 循环中让两个loop转换可控的编码思路，下文详细介绍。
• 注意自增自减导致的指针最后不在目标位置，需要检查条件是否还成立才能继续用指针。假设数组是19,29,24以19为pivot分组，如果没有两个if i < j，结果将变成29,19,24。因为第一个内层for结束后，出现i=j的情况，然后经过i自增后i=1,j=0，来到第二个内层for后的逻辑时，将会把本来已经比较过的19和29交换。而有了两个条件后第一个内层for结束后就不再执行后续逻辑了，因为已经分好组了。
• 为了避免极端情况，最好在递归前对指针上下边界和数组长度做出检查和限制

循环中让两个loop互相转换可控的编码思路：

在循环中假设有两个loop，两个loop之间需要根据condition互相跳转到对方loop中去，该怎么处理？

比如左右指针i和j，分别单独向中间移动，直到两者相遇。两个指针是分别单独移动，可能会i自增j不变，或者j自减i不变。在分别单独自增或自减的过程中条件不满足了就可能导致可移动指针的角色转换，比如原本是i自增j不变，条件不满足了就变成i不变j自减，当然也能反过来。

for condition0 {
    for condition0 && condition1 {
        logic1
    }
    for condition0 && condition2 {
        logic2
    }
}

这样，当condition0是i<j时，condition1是关于i的条件，condition2是关于j的条件。那么不光两个logic可以循环执行，当logic1执行完不满足condition1后还能继续到logic2执行，logic2也是同理会重新进入logic1的判断逻辑。

堆排序

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。然后对堆中的结点按层进行编号，将这种逻辑结构映射到数组中，就会发现：

• 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
• 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

步骤

• 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆）。
  • 将无序序列随便填充到完全二叉树中
  • 从最后一个非叶子节点开始，从左到右，从下到上进行调整。调整过程中可能需要交换父节点和其中一个子节点的值，以满足大顶堆要求的父节点>=子节点。这时两个叶子节点并没有稳定，因为其他节点可能比当前叶子节点还小。这样一趟过程走完来到树的根节点，就发现只有根节点是稳定的，其他节点都是不稳定的，如果需要其他节点有序就需要继续寻找次大节点。
• 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整剩余的堆中节点直到平衡，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换，将所有节点的数值按从左到右，从上到下的顺序取出，就得到了从小到大的有序序列了。

将数学逻辑转换成代码逻辑。注意由于树的节点间具有数学逻辑，并且最后需要用数组(切片)获取有序序列，所以可以用数组(切片)作为堆的容器，节点的交换就根据n、2n+1、2n+2的索引关系进行交换。

// 利用切片操作影响数组内存的特性实现交换，没有使用指针
package main

import "fmt"

func main() {
    // arr := [...]int{20,30,90,40,70,110,60,10,100,50,80}
    arr := [...]int{9,8,7,6,5,4,3,2,1}
    var ints []int = make([]int, 0, len(arr))
    ints = arr[:]

    heap_sort(ints)

    fmt.Println(ints)
}

func heap_sort(ints []int) {
    for k := len(ints); k >= 2; k-- {
        // 构建大顶堆：从第一个非叶子结点(n/2-1)从下至上，从右至左（i--）调整结构。for结束会在ints[0]得到一个最大的稳定节点
        for i := k / 2 - 1; i >= 0; i = i - 1 {
            heap_adjust(ints, i, k - 1)
        }
        // 每次大顶堆构建结束，从第n个节点到第2个都要做首尾交换操作，然后对剩下的节点再次构建大顶堆
        ints[k - 1], ints[0] = ints[0], ints[k - 1]
    }
}

func heap_adjust(ints []int, i, k int) {
    // 2i+1是左子节点
    if (2 * i + 1) <= k && ints[2 * i + 1] > ints[i] {
        ints[i], ints[2 * i + 1] = ints[2 * i + 1], ints[i]
    }
    // 2i+2是右子节点
    if (2 * i + 2) <= k && ints[2 * i + 2] > ints[i] {
        ints[i], ints[2 * i + 2] = ints[2 * i + 2], ints[i]
    }
}

疑问：将切片传入和函数，可以影响到函数外的变量内存吗？

答案：在Go中可以。对slice的操作，函数入参、函数内外的变量都可以用原始slice，访问下标时寻址运算符允许不写。也就是说(*ints_ptr)[0]可以简写成ints_ptr[0]

下面是按照类C++等语言的方式写的无简写版指针操作。注意指针数组和数组指针的区别

Go数组指针和指针数组的区别

看后两个字即可：

• 数组指针:它是一个指针，是数组首位的地址值。数组指针在参数中写作*[]int。在取值时写作(*ints_ptr)[0]，()不能省略，因为[]优先于*
• 指针数组:它是一个数组，该数组的元素都为地址值。在参数中写作[]*int表示每个元素都是*int类型的指针。取值时写作*ints_ptr[0]表示先从数组中取一个值，这个值是某个指针的地址，再用*获取这个地址对应的值。另外，写值时，要保证每个元素都是地址。

// 数组指针版
package main

import "fmt"

func main() {
    arr := [...]int{20,30,90,40,70,110,60,10,100,50,80}
    // arr := [...]int{9,8,7,6,5,4,3,2,1}
    var ints []int = make([]int, 0, len(arr))
    ints = arr[:]

    heap_sort(&ints)

    fmt.Println(ints)
}

func heap_sort(ints *[]int) {
    for k := len(*ints); k >= 2; k-- {
        // 构建大顶堆：从第一个非叶子结点(n/2-1)从下至上，从右至左（i--）调整结构。for结束会在ints[0]得到一个最大的稳定节点
        for i := k / 2 - 1; i >= 0; i = i - 1 {
            heap_adjust(ints, i, k - 1)
        }
        // 每次大顶堆构建结束，从第n个节点到第2个都要做首尾交换操作，然后对剩下的节点再次构建大顶堆
        (*ints)[k - 1], (*ints)[0] = (*ints)[0], (*ints)[k - 1]
    }
}

func heap_adjust(ints *[]int, i, k int) {
    // 2i+1是左子节点
    if (2 * i + 1) <= k && (*ints)[2 * i + 1] > (*ints)[i] {
        (*ints)[i], (*ints)[2 * i + 1] = (*ints)[2 * i + 1], (*ints)[i]
    }
    // 2i+2是右子节点
    if (2 * i + 2) <= k && (*ints)[2 * i + 2] > (*ints)[i] {
        (*ints)[i], (*ints)[2 * i + 2] = (*ints)[2 * i + 2], (*ints)[i]
    }
}

重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

归并排序

同样采用分治法，可以借用递归减少代码量。

归并排序的性能不受输入数据的影响，始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

简单说就是，在多个已排序序列中分别拿出最小的元素，比较后得到最小的放入最终空间中，再从刚入选的序列中再顺序拿第二个和刚才的数据做比较，再把其他序列中的数据按照同样方式写入序列，直到最终只剩一个序列，就把剩下序列中的所有数据一次性写入最终空间，

步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

将数学逻辑转换为代码执行逻辑：

/*
arr1=4578 arr2=1236
定义索引i，j从0开始
for嵌套，分别比较
i=0,j=0：4>1，1入选，j++，结果[1]
i=0,j=1：4>2，2入选，j++，结果[1,2]
…
i=0,j=3：1<4，4入选，i++，结果[1,2,3,4]
…
i=2,j=3：7>6，6入选，j++，结果[1,2,3,4,5,6]，
判断此时j>len(arr2)，arr2数组已空（注意：每轮自增后都要判断），就把arr1剩余的拷贝到arr中
*/

package main

import "fmt"

func main() {
    arr1 := [...]int{4,5,7,8}
    var ints1 = make([]int, 4)
    ints1 = arr1[:]
    arr2 := [...]int{1,2,3,6}
    var ints2 = make([]int, 4)
    ints2 = arr2[:]

    ints := make([]int, 0, len(arr1) + len(arr2))
    mergeSort(ints1, ints2, &ints)
    fmt.Println(ints)
}

func mergeSort(ints1, ints2 []int, ints_ptr *[]int) {
    l1 := len(ints1)
    l2 := len(ints2)
    i:=0
    j:=0
    for i < l1 && j < l2 {
        if ints1[i] <= ints2[j] {
            *ints_ptr = append(*ints_ptr, ints1[i])
            i = i + 1
            continue
        } else {
            *ints_ptr = append(*ints_ptr, ints2[j])
            j = j + 1
            continue
        }
    }
    if i == l1 {
        *ints_ptr = append(*ints_ptr, ints2[j:l2]...)
    }
    if j == l2 {
        *ints_ptr = append(*ints_ptr, ints1[i:l1]...)
    }
}

编码技巧和思路：

• 结果切片的初始化，应该让len=0，cap=所有数据的总长度，也就是make([]int, 0, 8)。这样在逐步将数据append进slice的过程中才不会出现问题。如果用make([]int, 8)则意味着已经有8个零值把空间占满了，后面再append只会在8个0后继续扩容并写入。在排序前先建好目标长度切片可以避免递归中频繁开辟空间。
• mergeSort时应该传入最终结果切片的地址。因为make slice操作是在mergeSort之外创建的空间，所以函数内应该传入地址，函数内用指针操作slice原值
• 虽然有两个指针，但是一个循环足够。在一个循环过程中，条件是i、j都没有遍历到最后一项，然后分别比较i、j对应的元素，有点像数组的前后指针移动的写法，不需要定义两个for。
• 向mergeSort传入了结果slice的地址，所以声明时用ints_ptr *[]int。使用时对*ints_ptr执行append操作。这样能避免在mergeSort内再占用一次内存空间。
• 当i或j达到末尾时，需要把另一个切片的所有数据追加到最终切片末尾。也就是target_slice = append(target_slice, slicei...)，注意...，没有将被认为是值而不是slice

多路归并

因为k路平衡归并中的 k 值不断增大，会增加内部归并的时间。也就是说比如5-路平衡归并时，若每次从 5 个文件中想得到一个最小值就需要比较 4 次。

所以，想要减少提高比较得出最小值的效率，可以用堆、胜者树、败者树来实现数据结构，用更少的比较次数得到最小值。

堆，赢者树，败者树的区别与联系

败者树实现内部归并

堆排序，如上节所属是O(nlogn)级别的时间复杂度，每次拿出一个最小(大)值后，其他节点要重新调整直到找出下一个最小(大)值。调整堆的时候，每次都要选出父节点的两个孩子节点的最小(大)值，然后再用孩子节点的最小(大)值和父节点进行比较，所以每调整一次需要比较两次。

在k路归并这个场景下，目的是在增加 k 值时不会影响其内部归并的效率，在一轮二叉遍历结束后得到k路最小值。并在下一轮查找最小值的过程中能充分利用上一轮的比较结果，减少比较次数。胜者树很符合这个场景。

胜者树可以看做锦标赛，叶子节点看做一个参赛队伍，只有胜者有资格进入下一轮比赛。与堆相比，胜者树不再使用所有节点保存数据，而是只用叶子节点保存数据，这样比较过程中如果一个节点的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他节点或不相关的比较的结果。

这个特点很适合做多路归并，也就是每个叶子节点代表了一路归并序列，每路序列分别出一个最小值加入到这个胜者树中，然后角出一个最小值后，将最小值写入最终序列。再从最小值所在的那一路中再选一个新值加入到树中，然后从该结点到根结点的路径修改这棵二叉树，就又能得出一个最小值。这个过程避免了无关节点的变动，只做出了兄弟、父亲节点在自下而上路径上的比较。

针对现实情况，要求排序的顺序是从小到大，所以更小的值会获胜。但是如果新来一个数值，替换树中的某个节点，要重新获取最小值，就需要与新值的兄弟和父节点作比较两次，再一路向上。

如果父亲节点保存的是败者，也就是更大的值呢，而胜者用于上一层的继续比较？比如说6和12构成第3层的叶子节点，10是第2层的叶子节点。6和12的父亲保存败者12的索引，6用来继续向上比较，也就是左子树胜者6和10比较得出第1层应该保存的败者索引，而不是第2层的败者12与10比较，所以第1层保存10的索引。也就是说根节点保存的就是亚军索引，那冠军就要在根节点之上单独加一个节点储存索引。根节点上追加的冠军节点用ls[0]记录最小值，ls[1]也就是二叉树的根节点（亚军）不一定是第二小的值，但是却是某个半区最小的值。这样，新值作为叶子节点，不再需要比较父亲和兄弟，直接比较父亲，比父亲小就继续用小值向上比较并保存大值，比父亲大就改变父节点为大值并用小值向上比较。所以败者树比胜者树会减少一半的比较过程。

下面是败者树的详细介绍。

败者树是树形选择排序的一种变形，本身是一棵完全二叉树。父亲节点保存子节点中更大的那一个（败者）。k路归并就需要k个叶子节点（可以不在同一层）。每个叶子节点存放第k路数组中目前的最小值。

由于二叉树左右节点比较后，较大值会被存到父节点。从叶子节点逐渐向上遍历，就能得到所有节点的相对大小，那些较大

为了防止在归并过程中某个归并段变为空，处理的办法为：可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时，表明 5 个归并段已全部归并完成。（因为只要还有记录，最终的胜者就不可能是附加的最大值）

多路归并的实现就是先分路，再排序，整理最终序列，需要注意数据量超级大并且内存不足情况的处理。具体实现过程略。

示例图

多路归并的使用场景

大数找极值：10亿个数，找出最大的10个（大小为10的小根堆，分治法与多路归并）

大数排序：10万个数，从小到大输出（分治法、内存排序、多路归并）

大文件小内存排序：要对900MB的数据进行排序，但机器上只有100 MB的可用内存。

大文件小内存分析：

将文件分成许多块，每块xMB,针对每个快各自进行排序，存回文件系统。然后将这些块逐一合并，最终得到全部排好序的文件。

具体步骤

• 读入100 MB的数据至内存中，用某种常规方式（如快速排序、堆排序、败者树、归并排序等方法）在内存中完成排序。
• 将排序完成的数据写入磁盘。
• 重复步骤1和2直到所有的数据都存入了不同的100 MB的块（临时文件）中。在这个例子中，有900 MB数据，单个临时文件大小为100 MB，所以会产生9个临时文件。
• 读入每个临时文件（顺串）的前10 MB（ = 100 MB / (9块 + 1)）的数据放入内存中的输入缓冲区，最后的10 MB作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果。）
• 执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。一旦9个输入缓冲区中的一个变空，就从这个缓冲区关联的文件，读入一个10M数据，除非这个文件已读完。这是外归并排序能在主存外完成排序的关键步骤 – 因为归并算法(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并)，每个大块不用完全载入主存。

算法方法论

二分法

link

问题：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

分析：插入目标值，无非四种情况

使用二分查找的基础条件是数组是有序数组。

题目还可能强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下表可能不是唯一的。

要在二分查找的过程中，保持不变量，这也就是「循环不变量」

• 二分法第一种写法：定义 target 是在一个在左闭右闭的区间里，「也就是[left, right] （这个很重要）」。

class Solution {
public:

    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1; // 定义target在左闭右闭的区间里，[left, right] 
        while (left <= right) { // 当left==right，区间[left, right]依然有效
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
        return right + 1;
    }

}; 

func main(){
	arr1 := []int{4}
	arr2 := []int{1, 3}
	arr3 := []int{1, 2, 4}
	arr4 := []int{1, 2}
	target := 3

	fmt.Println(binarySearch(arr1, target))
	fmt.Println(binarySearch(arr2, target))
	fmt.Println(binarySearch(arr3, target))
	fmt.Println(binarySearch(arr4, target))

}

func binarySearch(arr []int, target int) int{
	n := len(arr)
	if len(arr) == 0 {
		return 0
	}

	l := 0
	r := n - 1

	for ;l <= r; {
		m := (l + r) / 2 // 如果l+r是奇数，m落在floor(mid)上

		if arr[m] < target {
			l = m + 1
		} else if arr[m] > target {
			r = m - 1
		} else {
			return m
		}
	}

	return r + 1
}

时间复杂度：O(logn)

空间复杂度：O(1)

如果target 是在一个在左闭右开的区间里，也就是 [left, right) 。

那么循环条件要改成 while(left < right>) ，因为 left == right 的时候，在 [left, right) 是无效的空间

滑动窗口

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2, 3, 1, 2, 4, 3]

输出：2

解释：子数组 [4, 3] 是该条件下的长度最小的子数组。

暴力解法：两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2) 。

循环嵌套。for设置子序列起点为i。for设置子序列终止位置为j。一旦发现子序列和超过了s，更新result。一旦符合条件就break。

滑动窗口：「就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果」。

其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

解题的关键在于 窗口的起始位置如何移动

class Solution {
public:

    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }

}; 

「滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。」

时间复杂度：O(n) 空间复杂度：O(1)

编码常用的数据结构

精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

编码基础系列-数据结构

常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等。

下面将用Go语言设计所有数据结构，所以还需要追加切片slice、映射（字典）map、通道Channel等特殊结构。

数组array

内置类型。在连续的内存中存储多个元素的结构，数组中的元素通过数组下标进行访问，数组下标从0开始。

注意：

• 数组的大小固定后就无法扩容了
• 数组只能存储同一种类型的数据
• 数组的大小是类型的一部分，不能省略
• 添加和删除的操作慢，因为要移动其他的元素。

// 数组初始化
func main() {
    arr1 := [...]int{20,30}
    arr2 := [2]int{20,30}
    fmt.Println(arr1)
    fmt.Println(arr2)
    output(arr1)
    output2(&arr1)
}

func output(arr [2]int) {
    arr[0] = 1
    fmt.Println(arr)
}

func output2(arr *[2]int) {
    arr[0] = 2
    fmt.Println(arr)
}

在Go中，数组的初始化如果不知道长度，可以用…让编译器自行推算。但是[…]int不能作为参数类型，需要确定的长度，否则会提示use of [...] array outside of array literal，但是这样很不方便，数组扩容甚至要改参数类型。

所以，Go提供了切片slice

切片slice

内置类型切片是对数组的抽象。实际上是对数组的引用。

与数组相比，切片的长度是不固定的。slice的长度可以在数据增加或收缩的时候进行更改。当无法预测有多少个元素要存储到集合中的时候，slice是非常有用的数据结构。

slice中有两个概念：一是len长度，二是cap容量。长度是指已经被赋过值的最大下标+1，可通过内置函数len()获得。容量是指slice目前可容纳的最多元素个数，可通过内置函数cap()获得。slice是引用类型，因此在当传递slice时将引用同一指针，修改值将会影响它的底层对象，也就是数组。

slice声明时选择的底层对象可以是具名数组或匿名数组。具名数组就是已经存在一个数组时，借用这个数组初始化slice。匿名则是值直接初始化slice，由Go语言内部创建一个外部不可见的底层数组存储空间。无论哪种方式初始化的slice，slice的操作都会影响到底层数组的内存。

基于匿名数组的切片初始化：

s :=make([]int, len, cap)语法定义切片能避免越界问题。

// 声明
var ints1 []int
var ints2 []int
var ints3 []int
// 未初始化就访问
fmt.Println(ints1) // 不会报错，显示[]，元素是nil不是零值，所以不可访问
// fmt.Println(ints1[0]) // 会报错，因为长度未知，0号索引还无法寻址。runtime error: index out of range [0] with length 0
// ints1[0] = 1 // 会报错，runtime error: index out of range [0] with length 0
// 定义 + 初始化零值
ints1 = 1
ints1 = make([]int, 5) // 长度=5，容量忽略（go会自己估计合适的容量，比如5）
ints2 = make([]int, 5, 10) // 长度=5，容量=10，前5个元素被初始化为'零值'，后5个元素未初始化
ints3 = make([]int, 0, 10) // 没有任何元素被初始化
ints4 := make([]int, 0) // 支持简写定义。没有任何元素的空切片
// 定义 + 初始化指定的值
ints5 := []int{10, 20, 30, 40, 50} // 长度=5，容量=5
ints6 := []int{} //长度为0，容量为0，当你想从函数返回空集合时，空片是有用的。
ints7 := []int{4: 0} //想让第5个元素为0，但是前4个元素也要被初始化为0
// 追加元素
ints10 :=append(ints1,1) // len!=0时，已初始化一些零值，追加是在这些零值后面
ints11 :=append(ints1,1,2) // 支持追加多个元素
ints12 :=append(ints10,ints11...) // 追加切片需要加上...，表明这是一个切片要特殊处理
// 打印
fmt.Printf("ints1: len=%d, cap=%d\n", len(ints1), cap(ints1))
fmt.Println(ints1)
fmt.Println(ints2)
fmt.Println(ints3)
fmt.Println(ints4)
fmt.Println(ints5)
fmt.Println(ints6)
fmt.Println(ints7)
fmt.Println(ints10)
fmt.Println(ints11)
fmt.Println(ints12)
// 输出
[]
ints1: len=5, cap=5
[0 0 0 0 0]
[0 0 0 0 0]
[]
[]
[10 20 30 40 50]
[]
[0 0 0 0 0]
[0 0 0 0 0 1]
[0 0 0 0 0 1 2]
[0 0 0 0 0 1 0 0 0 0 0 1 2]

基于具名数组的切片初始化：

arr := [...]int{10, 20, 30, 40, 50}
// 具名数组生成切片
ints1 := make([]int, 0, len(arr))
ints2 := make([]int, 0, len(arr))
ints3 := make([]int, 0, len(arr))
ints4 := make([]int, 0, len(arr))
ints5 := make([]int, 0)
// 切片截取
ints1 = arr[:] // 数组所有内容作为切片的底层内存
ints1[0] = 1 // 对切片的修改，会影响底层的数组
ints2 = arr[:1] // 不提供index时，左表示0，右表示len(arr)
ints3 = arr[1:2] // 含左不含右
// ints4 = arr[:-1] // 报错
// 切片追加
ints5 = append(ints1, ints2...)
// 切片拷贝
intsTarget := make([]int, 0)
intsTarget = ints5
copy(intsTarget, ints2)
fmt.Println(ints1)
fmt.Println(ints2)
fmt.Println(ints3)
fmt.Println(ints4)
fmt.Println(ints5)
fmt.Println(intsTarget)
// 输出
[1 20 30 40 50]
[1]
[20]
[]
[1 20 30 40 50 1]
[1 20 30 40 50 1]

ints := make([]int, 0) 与 ints = arr[:]可以以具名数组为底层空间，初始化一个切片。注意，对切片的修改，会影响底层的数组。

栈stack

线性表。栈顶允许操作，栈底不允许操作。后进先出。从栈顶放入元素的操作叫入栈Push，取出元素叫出栈Pop。

支持以下方法

• Push(t)：将值t压至栈顶
• Pop()：若栈非空，则将栈顶对象移除，并将其返回；否则，报错
• Size()：返回栈内值的数目
• IsEmpty()：检查栈是否为空
• NewStack()：构造器

Go的数据结构与实现【Stack】

为了简单，用数组模拟栈

package main

import (
    "fmt" // fmt.Errorf()
    "sync" // sync.RWMutex
    "errors" // errors.New()
)

type T int // 包装类型，避免太多硬编码

type Stack struct {
    sync.RWMutex // 加锁操作
    array []T // 实际数据用slice存储
}

func NewStack() *Stack {
    stack := &Stack{} // 要返回指针，注意空struct及引用的写法
    stack.array = []T{} // 空struct，值为nil，一般用在返回前初始化
    return stack
}

func (s *Stack) Push(t T) { // 基于指针接收器的方法
    s.Lock() // 不要忘记加写锁
    s.array = append(s.array, t)
    s.Unlock() // 解锁
}

func (s *Stack) Pop() (*T, error){ // 需要返回出栈的值的指针，以及错误。具名参数和匿名参数不能同时出现，否则"syntax error: mixed named and unnamed function parameters"，这里error类型不需要变量，所以都用匿名参数。
    // 需要判断是否为空，空要返回错误
    if s.IsEmpty() {
        // return nil, errors.New("empty stack") // 返回值类型如果有nil或T，需要返回指针，否则会提示"cannot use nil as type T in return argument"
        return nil, fmt.Errorf("empty stack") //
    }

    s.Lock()
    l := len(s.array)
    t := s.array[l-1]
    s.array = s.array[:l - 1]
    s.Unlock()
    return &t, nil
}

func (s *Stack) Size() int { // 如果不写返回值类型，调用时会报错
    s.RLock() // 读要加锁
    defer s.RUnlock() // 在return后defer
    return len(s.array)
}

func (s *Stack) IsEmpty() bool{ // 如果不写返回值类型，调用时会报错
    return s.Size() == 0
}

func main() {
    s := NewStack()
    s.Push(1)
    s.Push(2)
    fmt.Println(s.IsEmpty())
    fmt.Println(s.Size())
    fmt.Println(s.array)
    val_ptr,err := s.Pop()
    if err != nil {
        fmt.Println(err)
    } else {
        fmt.Println(*val_ptr)
    }
    fmt.Println(s.array)
}

/*
输出：
false
2
[1 2]
2
[1]
*/

注意代码中可能容易写错的小问题

链表linkedList

链表是一种通过指针串联在一起的线性结构，每一个节点是由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

因为含有大量的指针域，占用空间较大；查找元素需要遍历链表来查找，非常耗时。但是数据量较小，适合需要频繁增加，删除操作的场景

• 数组与链表的区别 link

拿几个人一起去看电影时坐座位为例。

• 数组的特点
  • 在内存中，数组是一块连续的区域。 拿上面的看电影来说，这几个人在电影院必须坐在一起。
  • 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。 比如看电影时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。
  • 插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。 当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。
  • 随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
  • 不利于扩展，数组定义的空间不够时要重新定义数组。
• 链表的特点
  • 在内存中可以存在任何地方，不要求连续。 在电影院几个人可以随便坐。
  • 每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……
  • 增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
  • 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起。
  • 不指定大小，扩展方便。链表大小不用定义，数据随意增删。

数组的优点

• 随机访问性强
• 查找速度快 数组的缺点
• 插入和删除效率低
• 可能浪费内存
• 内存空间要求高，必须有足够的连续内存空间。
• 数组大小固定，不能动态拓展 链表的优点
• 插入删除速度快
• 内存利用率高，不会浪费内存
• 大小没有固定，拓展很灵活。 链表的缺点
• 不能随机查找，必须从第一个开始遍历，查找效率低

链表的类型

• 单链表

链接的入口点称为列表的头结点也就是head。

• 双向链表

单链表中的节点只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

• 循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

• 链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

• 链表的定义

不定义构造函数是可以的，C++默认生成一个构造函数。但是这个构造函数不会初始化任何成员变化

如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

ListNode* head = new ListNode(); 
head->val = 5; 

• 链表的操作
• 删除节点

只要将C节点的next指针 指向E节点就可以了。

C++里最好是再手动释放这个D节点，释放这块内存。其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

• 添加节点

链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

所以在写代码的时候，需要单独写一段逻辑来处理移除头结点的情况。

其实「可以设置一个虚拟头结点」，这样原链表的所有节点就都可以按照统一的方式进行移除了。不过，return 头结点的时候，return dummyNode->next; ， 这才是新的头结点

• 比较数组和链表

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

实现链表

支持以下方法：

• Add：添加一个元素到链表末尾
• Insert：向链表指定位置插入元素
• RemoveAt：移除指定索引位置的元素
• IndexOf：取指定索引位置的元素
• IsEmpty：判断链表是否为空
• Size：获取链表长度
• Traverse：遍历链表并输出

package main

import (
    "fmt"
    "sync"
)
type T int

type Node struct {
    val T
    next *Node
}

type LinkedList struct {
    sync.RWMutex
    head *Node
    size int
}

func NewNode(t T) (*Node){ // 返回节点的指针
    return &Node{ val: t} // 需要提供节点的值，不知道next指向所以不提供
}

func NewLinkedList() (*LinkedList){ // 返回指针
    return &LinkedList{} // 初始化空链表，不需要首个节点情况
}

func (l *LinkedList) Add(t T) {
    l.Lock()
    defer l.Unlock()

    node := NewNode(t)
    
    // 需要区分是否头节点
    if l.size == 0 {
        l.head = node
    } else {
        head := l.head
        for head.next != nil {
            head = head.next
        }
        head.next = node
    }

    // 长度+1
    l.size = l.size + 1
}

func (l *LinkedList) Traverse() {
    l.RLock()
    defer l.RUnlock()

    head := l.head
    for head.next != nil {
        head.Print() // 打印节点
        head = head.next
    }
    head.Print() // 打印最后一个节点
}

func (n *Node) Print() {
    fmt.Println(n.val)
}

func (l *LinkedList) IndexOf(t T) (*Node){
    l.RLock()
    l.RUnlock()

    head := l.head
    for head.next != nil {
        if head.val == t {
            return head
        }
        head = head.next
    }
    if head.val == t {
        return  head
    } else {
        return nil
    }
}

func (l *LinkedList) IsEmpty() (bool){
    l.RLock()
    defer l.RUnlock()
    return l.head == nil
}

func (l *LinkedList) Size() (int){
    l.RLock()
    defer l.RUnlock()
    return l.size
}

func main() {
    l := NewLinkedList()
    l.Add(1)
    l.Add(2)
    l.Traverse()
    fmt.Println(l.Size())
    idx := l.IndexOf(2)
    idx.Print()
}

/*
输出：
1
2
2
2
*/

只实现了Add()和IndexOf()，而没有实现RemoveAt()、InsertAt()等，这些会考虑size、插入位置在头尾、是否head、计数等情况

双向链表

Go已经实现了双向链表，见container/list包。

特点在下面的LRU Cache一节。源码在Github

队列queue

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队

支持下面的两个基本方法：

• Enqueue(t) 将值t加到队列末端
• Dequeue() 若队列非空，则将队首元素移除，并将其返回 否则，报错
• Size() 返回队列内值的数目
• IsEmpty() 检查队列是否为空
• Front() 若队列非空，则返回队首元素（但并不移除）

为了简单，用数组模拟队列

package main

import (
    "fmt"
    "sync"
    "errors"
    )

type T int

type Queue struct {
    sync.RWMutex
    array []T
}

func NewQueue() *Queue{
    q := Queue{}
    q.array = []T{}
    return &q
    // 也可以写成：
    // return &Queue{
    //     array: []T{}, // comma逗号是必须有的，否则编译会报错
    // }
}

func (q *Queue)Enqueue(val T) {
    q.Lock()
    defer q.Unlock()
    q.array = append(q.array, val)
}

func (q *Queue) Dequeue() (*T, error){
    q.Lock()
    defer q.Unlock()
    
    l := len(q.array)
    if l == 0 {
        return nil, errors.New("empty")
    }
    ret := q.array[0] // 返回索引0（队头）
    q.array = q.array[1:l]
    return &ret, nil
}

func (q *Queue) Front() (*T, error){
    q.Lock()
    defer q.Unlock()
    
    l := len(q.array)
    if l == 0 {
        return nil, errors.New("empty")
    }
    return &q.array[0], nil // 返回索引0（队头）
}

func main() {
    q := NewQueue()
    q.Enqueue(1)
    front, _ := q.Front()
    fmt.Println(*front) // 得到的是指针
    pop, _ := q.Dequeue()
    fmt.Println(*pop)
}

除了数组外，还有类似双向链表对双向进出队列的实现，比如redis支持rpush+lpop，也支持lpush和rpop。

树tree、堆heap

堆结构可见上面”堆排序”一节，堆也是以二叉树为基础的。

二叉搜索树

每个节点的值都大于或等于左子树中的节点值，并且小于或等于右子树中的节点值。

支持：

• 插入，遵守规则
  • 如果新节点的值小于当前节点的值，我们去左孩子
  • 如果新节点的值大于当前节点的值，我们去右孩子
  • 如果当前节点为空时，我们到达了一个叶节点，我们可以在该位置插入新节点
• 搜索
  • 与节点中的值进行比较来搜索值；然后，我们将根据结果继续左或右孩子。
• 删除
  • 找到要删除的节点
  • 根据不同情况删除
    • 没有孩子：这是最简单的情况；我们只需要在它的父节点中用nil替换这个节点
    • 只有一个孩子：在父节点中，我们用它唯一的孩子替换这个节点。
    • 有两个孩子：这是最复杂的情况，因为它需要树重组，可以有两种解决办法：
      • 找到左子树中的最大值，将值赋给给节点，然后将左子树最大值这个节点删除(删除可以用递归实现)
      • 找到左子树中的最小值，将值赋给给节点，然后将右子树最小值这个节点删除。当然这样会有个弊端：当一直删除时，会导致树高度失衡，导致一边高，一边低，解决这样的办法可以删除左右子树最大最小节点交替实行。或者记录一高度，主要删除，左子树或者右子树高的那一边。
• 遍历
  • 前序
  • 中序
  • 后序
• 最值
  • Max
  • Min
• 打印

package main

import (
    "fmt"
    "sync"
)

type T int

type Node struct {
    val T // 节点值
    left *Node // 左右节点指针
    right *Node
}

// binary search tree
type BST struct {
    sync.RWMutex
    root *Node // 提供根节点即可
}

func NewNode(t T) (*Node){
    return &Node{
        val: t, // 注意逗号
    }
}

func NewBST() (*BST){
    return &BST{}
}

// func NewTree(t T) (*Node){ // 用一个节点初始化tree，返回指针。这里的创建tree不光可以用在根节点，也作用于所有子tree
//     return &Node{
//         val: t,
//     }
// }

// bst的插入方法
func (bst *BST) Insert(t T) {
    bst.Lock()
    defer bst.Unlock()

    node := NewNode(t)
    if bst.root == nil { // nil 需要特殊处理，因为没有val属性。而且非*Node节点不能作为递归参数，所以要在递归前提前处理
        bst.root = node
    } else {
        insert(bst.root, node) // 从根节点向下寻找合适的位置插入新的节点。递归的参数应该是节点而不是树，否则继续向下查找时还要用孩子节点构建树结构
    }
}

// 插入函数，从根节点向下寻找合适的位置插入新的节点
func insert(root *Node, node *Node) {
    if root.val < node.val { // 注意"<="或"<"都可以，会影响到孩子节点和父亲节点相同时树的结构。
        if root.right == nil {
            root.right = node // 如果右孩子不存在，新节点就充当右孩子
        } else {
            insert(root.right, node) // 递归，重置根节点为右孩子
        }
    } else {
        if root.left == nil {
            root.left = node
        } else {
            insert(root.left, node)
        }
    }
}

func (bst *BST) Print() {
	bst.Lock()
	defer bst.Unlock()

	fmt.Println("------------------------------------------------")
	stringify(bst.root, 0)
	fmt.Println("------------------------------------------------")
}

// 将树结构字符串化，不同层级需要加不同的空格数量
// 是一棵躺着的树
// 非常巧妙
func stringify(root *Node, level int) {
	if root != nil {
		format := ""
		for i := 0; i < level; i++ {
			format += "       "
		}
		format += "-[ "
		level++
        // 注意：同一子树上的左右兄弟节点是挨着打印的，左子树打印完才会打印右子树，兄弟节点也是挨着的。
		stringify(root.left, level) // 在对左子树递归到最深层时，直到左孩子为nil，表示来到了最左叶子节点，开始打印。
        // 注意：最深层递归结束后，返回执行上一层的递归，而不是兄弟节点，也就是说前序遍历的012三个节点，需要先打印1再打印0最后打印2，并且由于0是根节点，2是右子树也就是后面那个递归时才打印
		fmt.Printf(format+"%d\n", root.val)
		stringify(root.right, level) // 在右子树递归到最深层时，直到右孩子为nil，开始打印最右叶子节点。
	}
}

const (
	t1 T = iota + 1
	t2
	t3
	t4
	t5
	t6
	t7
	t8
	t9
)

func main() {
    bst := NewBST()
	bst.Insert(t5)
	bst.Insert(t3)
	bst.Insert(t2)
	bst.Insert(t4)
	bst.Insert(t5) // 插入重复值的情况
	bst.Insert(t6)
	bst.Insert(t1)
	bst.Insert(t7)
	bst.Insert(t8)
    bst.Print()
	fmt.Println(bst.Search(t8))
	fmt.Println(bst.Search(t9))
}

// 测试删除相同值的节点，以及指针测试
// func main() {
//     bst := NewBST()
// 	bst.Insert(t5)
// 		bst.Insert(t5)
// 	bst.Insert(t6)
// 	bst.Insert(t4)
// 	bst.Insert(t6) // 插入重复值的情况
// 	bst.Insert(t5)
// 	bst.Insert(t7)
// 	bst.Insert(t5)
//     bst.Print()
//     bst.RemoveRight(t5)
//     bst.Print()
//     bst.RemoveWrong(t6)
//     bst.Print()
// }

func (bst *BST) Search(t T) bool{
    bst.RLock()
    defer bst.RUnlock()

    return search(bst.root, t) // 和insert类似，递归的参数仍然是节点，而不是树。但是因为不是在root下插入孩子节点，所以root可以作为递归参数，在递归函数内root和后面的孩子节点是一样的判断是否nil即可。
}

func search(root *Node, t T) bool {
    if root == nil {
        return false
    }
    if root.val == t {
        return true
    } else if root.val < t { // 注意else if，不要和其他语言搞混
        return search(root.right, t) // 注意递归是要return的，否则与返回值不符
    } else {
        return search(root.left, t)
    }
}

// 删除节点（错误写法）
func (bst *BST) RemoveWrong(t T) {
    bst.Lock()
    defer bst.Unlock()

    fmt.Println(bst.root)

    fmt.Println(&(bst.root.val))
    removeWrong(bst.root, t) // 错误写法
}

// 删除节点（错误写法）
// 注意：十分重要！此时传入的root是值，而不是引用，在函数内打印root节点"fmt.Println(&root)"得到的地址是不同的，所以内部如果执行"root=nil"这种赋值就会出错
func removeWrong(root *Node, t T) {
    fmt.Println(&root) // 和Remove()中的变量地址不一致，这里是局部变量
    if root == nil { // 特殊处理
        return
    }
    if root.val < t {
        removeWrong(root.right, t) // 递归右子树
    } else if root.val > t {
        removeWrong(root.left, t)
    } else {
        // 因为节点相等时有三种情况，所以放到else中处理
        if root.left == nil && root.right == nil {
            // 叶子节点直接置为nil即可，就表示删除，也就没有后继节点了
            // 测试发现：地址是局部变量地址，改变的val值却被记录到了函数外，nil还是存在函数内没有影响函数外
            // 这就是省略指针，还有接收器可以是指针或值这种语言特点，容易出现的问题！
            fmt.Println(root)
            fmt.Println(&(root.val)) // 可以验证局部变量root操作的属性val是否与函数外的val地址一致？是的。
            fmt.Println(root.val)
			root.val = 100 // 注意：明明是传值的函数，为*Node节点重新定义了一个局部变量，但是为什么局部变量的val修改后会影响到函数外的val？因为局部变量root是按照传引用的方式将*Node节点传进来了，所以除了root变量本身，其他的所有都是引用的函数外节点指针的内容，修改了"root.val"就相当于修改了函数外的val。但是唯独局部变量root是函数内新生成的变量，"root = nil"修改的就是局部变量内存对应的值，而"root.val"还是在修改函数外的值。
            root = nil
            fmt.Println((root))
            return // 不要忘记return
        }else if root.left != nil && root.right == nil {
            root = root.left
            return
        } else if root.left == nil && root.right != nil {
            root = root.right
            return
        } else {
            // 左右节点都存在时，不光要重组树结构，当要删除的节点还有左右孩子时，还要继续查找与值最接近的节点用来替换掉当前被删除的节点作为新的父亲。
            // 这个节点一般位于右子树的最后一个左叶子节点或左子树的最后一个右叶子节点，也就是左子树的最大值或右子树的最小值，替换掉节点后删除那个最深叶子节点即可。
            // 比如在前面insert()函数中使用"<"就会看到根节点是5，左子树最深层节点的右孩子也是5，当然也可以存储到右子树最深层节点的左孩子上.
            // 这里选择右子树的最后一个左叶子节点
            smallest_right_node := root.right
            for {
                if smallest_right_node != nil && smallest_right_node.left != nil {
                    smallest_right_node = smallest_right_node.left
                } else {
                    // 此时一定是smallest_right_node是叶子节点，所以smallest_right_node.left==nil
                    // 这就找到了右子树的最后一个左叶子节点
                    break
                }
            }
            // 用左叶子节点的值替换root的值，注意还保留着left和right指针
            root.val = smallest_right_node.val
            // 再递归删除右子树的左叶子节点
            removeWrong(root.right, smallest_right_node.val)
            return // 不要忘了结束递归
        }
    }
}

// 删除节点（正确写法）
func (bst *BST) RemoveRight(t T) {
    bst.Lock()
    defer bst.Unlock()

    fmt.Println(&bst.root)
    removeRight(&bst.root, t) // 正确写法，应该传入节点指针的指针，这样才有机会通过"*root = nil"把节点指针改成nil。如果直接传节点指针进入函数，只能改局部变量
}

// 删除节点（正确写法）
// 需要传引用，也就是执行节点指针的指针。在函数内用*取值。
func removeRight(root **Node, t T) {
    fmt.Println(root) // 函数外节点指针的地址
    fmt.Println(*root) // 函数外的节点指针
    if (*root) == nil { // 特殊处理 // 尽可能用括号包裹，避免歧义
        return
    }
	if (*root).val < t {
		removeRight(&((*root).right), t) // 递归右子树 // 参数是节点指针的指针，(*root)是节点，&((*root).right)就是节点指针的指针
    } else if (*root).val > t {
		removeRight(&((*root).left), t)
    } else {
        // 因为节点相等时有三种情况，所以放到else中处理
        if (*root).left == nil && (*root).right == nil {
            // 叶子节点直接置为nil即可，就表示删除，也就没有后继节点了
            fmt.Println((*root).val)
            (*root) = nil // 最重要的地方：此时*root表示函数外的一个节点指针，把此节点指针改成nil后，他的父亲判断孩子就是nil了
            fmt.Println((*root))
            return // 不要忘记return
        }else if (*root).left != nil && (*root).right == nil {
            (*root) = (*root).left
            return
        } else if (*root).left == nil && (*root).right != nil {
            (*root) = (*root).right
            return
        } else {
            // 左右节点都存在时，不光要重组树结构，当要删除的节点还有左右孩子时，还要继续查找与值最接近的节点用来替换掉当前被删除的节点作为新的父亲。
            // 这个节点一般位于右子树的最后一个左叶子节点或左子树的最后一个右叶子节点，也就是左子树的最大值或右子树的最小值，替换掉节点后删除那个最深叶子节点即可。
            // 比如在前面insert()函数中使用"<"就会看到根节点是5，左子树最深层节点的右孩子也是5，当然也可以存储到右子树最深层节点的左孩子上.
            // 这里选择右子树的最后一个左叶子节点
            smallest_right_node := (*root).right
            for {
                if smallest_right_node != nil && smallest_right_node.left != nil {
                    smallest_right_node = smallest_right_node.left
                } else {
                    // 此时一定是smallest_right_node是叶子节点，所以smallest_right_node.left==nil
                    // 这就找到了右子树的最后一个左叶子节点
                    break
                }
            }
            // 用左叶子节点的值替换root的值，注意还保留着left和right指针
            (*root).val = smallest_right_node.val
            // 再递归删除右子树的左叶子节点
			removeRight(&((*root).right), (*root).val)
            return // 不要忘了结束递归
        }
    }
}

// 遍历（前、中、后序，这里只用递归法实现前序遍历）
func (bst *BST) PreOrder() {
    bst.RLock()
    defer bst.RUnlock()
    // TODO
}

/*
输出：
插入测试：
------------------------------------------------
                     -[ 1
              -[ 2
       -[ 3
              -[ 4
-[ 5
       -[ 5
              -[ 6
                     -[ 7
                            -[ 8
------------------------------------------------
true
false

注意打印格式：
- 是一棵躺着的树
- 从树的叶子节点开始打印
- 每一层都是先打印左节点再打印右节点，所以同一层的左右节点是挨着的
- 父亲节点和子节点相同时，根据代码的不同可能有两种情况
*/

/*
输出：
删除测试：
------------------------------------------------
              -[ 4
                            -[ 5
                     -[ 5
       -[ 5
-[ 5
              -[ 6
       -[ 6
              -[ 7
------------------------------------------------
0xc000074038
0xc000074038
0xc000074050
0xc000074090
7

------------------------------------------------
              -[ 4
                            -[ 5
                     -[ 5
       -[ 5
-[ 6
              -[ 6
       -[ 7
------------------------------------------------
&{6 0xc000074060 0xc000074080}
0xc00007e020
0xc00007e028
0xc00007e030
&{6  }
6

------------------------------------------------
              -[ 4
                            -[ 5
                     -[ 5
       -[ 5
-[ 6
              -[ 100
       -[ 7
------------------------------------------------
*/

注意，删除节点时，当要删除的节点还有左右孩子时，需要找到一个最接近被删除节点替换掉被删除的节点，这个节点一般位于右子树的最深层的左叶子节点或左子树的最深层的右叶子节点，替换掉节点后删除那个最深叶子节点即可。

尤其注意，要让节点指针*Node赋值为nil，需要给函数传递节点指针的指针**Node，否则只能给局部变量root赋值为nil，而不会影响到函数外。通过打印函数内外的参数地址就可以验证了。

而给函数内局部变量root的属性val赋值时，哪怕参数是*Node，修改的也是函数外的val。这是因为只有局部变量操作的是局部内存，而局部变量操作的struct都是通过传引用在操作函数外的值。通过打印函数内外的val属性的地址就能验证了。

前序、中序、后序遍历过程略。

字典map

Go提供了map，但不是并发安全的，可以用sync.Map。

支持如下操作：

func (m *Map) CompareAndDelete(key, old any) (deleted bool)
func (m *Map) CompareAndSwap(key, old, new any) bool
func (m *Map) Delete(key any)
func (m *Map) Load(key any) (value any, ok bool)
func (m *Map) LoadAndDelete(key any) (value any, loaded bool)
func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool)
func (m *Map) Range(f func(key, value any) bool)
func (m *Map) Store(key, value any)
func (m *Map) Swap(key, value any) (previous any, loaded bool)

使用过程

package main

import (
    "fmt"
    "sync"
)

func main() {
    var m sync.Map

    // 写入
    m.Store("k1", "v1")

    // 读取
    v1, _ := m.Load("k1")
    fmt.Println(v1)

    // 遍历
    // 传一个函数
    m.Range(func(k, v interface{}) bool { // 注意：迭代函数sync.Map.Range(func(k, v interface) bool{...}) 是固定格式，不能增减参数或去掉返回值
        k1 := k.(string)
        v1 := v.(string)
        fmt.Println(k1, v1)
        return true
    })

    // 删除
    m.Delete("k1")
    v1, ok := m.Load("k1")
    fmt.Println(v1, ok)

    // 读取或写入
    m.LoadOrStore("k2", "v2")
    v2, _ := m.Load("k2")
    fmt.Println(v2)
}

/*
输出：
v1
k1 v1
<nil> false
v2
*/

集合set

Set是值的集合，可以迭代这些值、添加新值、删除值并清除集合、获取集合大小、检查集合是否包含值、实现并交差操作，集合中的一个值只存储一次，不能重复。

Set可以用Map实现，可以让Map的值是空Struct即可，不占用内存空间，并且Map的key是唯一的。这样就只需要再用sync.Map作为底层结构保证并发安全就行了。

package main

import (
    "fmt"
    "sync"
    "errors"
)

type T int

type Set struct {
    sync.RWMutex // 因为对sync.Map的操作可能不是原子操作（比如先查再加），所以需要上锁
    m sync.Map
    size int // 暂时用int
}

func NewSet() *Set{
    var m sync.Map
    return &Set{m: m, size: 0}
}

func (s *Set) Add(k interface{}) bool{ // interface{}才是完整的类型，不要忘记{}
    s.Lock()
    defer s.Unlock()

    _, ok := s.m.Load(k) // 不需要value，只判断是否存在
    if ok {
        return false
    }
    s.m.Store(k, struct{}{}) // 注意value用空struct类型的空值，不占用任何内存空间
    s.size = s.size + 1 // 不要忘记size变化
    return true
}

func (s *Set) Contains(k interface{}) (bool, error){
    s.RLock()
    defer s.RUnlock()

    _, ok := s.m.Load(k)
    if ok {
        return true, nil
    }
    return false, errors.New("not exist")
}

func (s *Set) Size() (int){
    s.Lock()
    defer s.Unlock()
    return s.size
}

func (s *Set) Delete(k interface{}) (bool){
    s.Lock()
    defer s.Unlock()

    _, ok := s.m.Load(k)
    if ok {
        s.m.Delete(k)
        s.size = s.size - 1
        return true
    }
    return false
}

func (s *Set) Clear() {
    s.Lock()
    defer s.Unlock()

	s.m.Range(func(k, v interface{}) bool{ // 注意：迭代函数sync.Map.Range(func(k, v interface) bool{...}) 是固定格式，不能增减参数或去掉返回值
        s.m.Delete(k)
		return true
    })
}

// 并集Union，将s和s1合并存储到新集合u
func (s *Set) Union(s1 *Set) (*Set){
    // 注意s、s1的上锁期间，如果还想做写操作会引起死锁
    s.RLock()
    defer s.RUnlock()
    s1.RLock()
    defer s1.RUnlock()

    // 错误的存储方式：用s给u赋值。最终合并的集合是s的底层存储空间，u不过是对s的引用，也就是改变了s的原始集合。并且将s1写入到集合的过程中，可能导致s的死锁，因为写入目标正在被锁定。
    /*
    var u Set // 局部变量u是集合s的底层空间的副本。对u的操作不会影响到s。
    if s.size < s1.size { // 对size的判断，将短集合插入到长集合
        u = *s1
        s.m.Range(func(k, v interface{}) bool{
            (&u).Add(k)
		    return true
        })
    } else {
        u = *s
        s1.m.Range(func(k, v interface{}) bool{
            (&u).Add(k)
		    return true
        })
    }
    return &u // 注意：返回的是局部变量的指针，出现内存逃逸，但是Go支持这种写法
    */

    // 正确的存储方式：用新集合存储，分别将s和s1都加入到结果集合中，重复的会被排除，但是这样效率较低
    u := NewSet()
    s.m.Range(func(k, v interface{}) bool{
        u.Add(k)
		return true
    })
    s1.m.Range(func(k, v interface{}) bool{
        u.Add(k)
    })
    return u
}

// 交集Intersection
func (s *Set) Intersection(s1 *Set) (*Set){
    s.RLock()
    defer s.RUnlock()
    s1.RLock()
    defer s1.RUnlock()

    u := NewSet()
    if s.size < s1.size {
        s.m.Range(func(k, v interface{}) bool {
            if _, ok := s1.m.Load(k); ok {
                u.Add(k)
            }
            return true
        })
    } else {
        s1.m.Range(func(k, v interface{}) bool {
            if _, ok := s.m.Load(k); ok {
                u.Add(k)
            }
            return true
        })
    }
    return u
}

// 差集Difference，差集区分方向：在s中不在s1中
func (s *Set) Difference(s1 *Set) (*Set){
    s.RLock()
    defer s.RUnlock()
    s1.RLock()
    defer s1.RUnlock()

    u := NewSet()
    s.m.Range(func(k, v interface{}) bool {
        if _, ok := s1.m.Load(k); !ok {
            u.Add(k)
        }
        return true
    })
    return u
}

// 迭代，注意map、sync.Map的迭代或者叫Range时，顺序是不确定的
func (s *Set) Iteration(offset, limit int) ([]interface{}, error) {
    // TODO: 需要迭代返回，否则数量可能会很大不适合一次性返回
    // sync.Map是无序的，怎么用offset和limit迭代呢？又没有索引
    ret := make([]interface{}, 0, s.size)
    s.m.Range(func(k, v interface{}) (bool) {
        ret = append(ret, k)
        return true
    })
    return ret, nil
}

func main() {
    s := NewSet()
    // 插入
    ok1 := s.Add(1)
    fmt.Println(ok1)
    // 重复插入
    ok2 := s.Add(1)
    fmt.Println(ok2)
    // 包含
    ok, err := s.Contains(1)
    fmt.Println(ok, err)
    // 空间
    fmt.Println(s.Size())
    // 删除
    s.Delete(1)
    ok, err = s.Contains(1)
    fmt.Println(ok, err)
    ok2 = s.Add(2)
    fmt.Println(ok2)
    // 清空
    s.Clear()
    ok, err = s.Contains(2)
    fmt.Println(ok, err)

    // 并集
    s1 := NewSet()
	s2 := NewSet()
    s1.Add(1)
    s2.Add(2)
    u1 := s1.Union(s2)
    ok, err = u1.Contains(1)
    fmt.Println(ok, err)
    ok, err = u1.Contains(2)
    fmt.Println(ok, err)
    // 并集不能影响原集合
    ok, err = s1.Contains(1)
    fmt.Println(ok, err)
    ok, err = s1.Contains(2)
    fmt.Println(ok, err)
    
    // 交集
    u2 := s1.Union(s2)
    ok, err = u2.Contains(1)
    fmt.Println(ok, err)
    ok, err = u2.Contains(2)
    fmt.Println(ok, err)

    // 差集
    u3 := s1.Union(s2)
    ok, err = u3.Contains(1)
    fmt.Println(ok, err)
    ok, err = u3.Contains(2)
    fmt.Println(ok, err)

    // 迭代
    fmt.Println(u1.Iteration(0, 0))
}

/*
输出：
常规操作：
true
false
true <nil>
1
false not exist
true
false not exist

并集：
true <nil>
true <nil>
true <nil>
false not exist

交集：
false not exist
false not exist

差集：
true <nil>
false not exist

迭代：
[1 2] <nil>
*/

散列表（哈希表）hash

Go的map结构，就是使用hash为底层结构的。现在来创建自己的哈希结构就有点多余，直接用map就行了，需要并发安全就sync.Map。

环形缓冲区RingBuffer（环形队列RingQueue）

环形缓冲区是一种有界循环数据结构，用于在两个或多个线程之间缓冲数据。当我们继续写入环形缓冲区时，它会在到达末尾时回绕。

环形缓冲区是一种高效的FIFO缓冲区。它使用可以预先分配的固定大小的数组，并允许高效的内存访问模式。所有缓冲区操作都是常数时间O(1)，包括消耗一个元素，因为它不需要移动元素。

另一方面，确定环形缓冲区的正确大小至关重要。例如，如果缓冲区过小并且读取速度很慢，则写入操作可能会阻塞很长时间。我们可以使用动态调整大小，但它需要移动数据，我们会错过上面讨论的大部分优势。

环形缓冲区是使用在边界处环绕的固定大小数组实现的。

在数组结构中，有三个关键位置：

• 缓冲区中用于插入元素的下一个可用位置（注意：必须是可用于插入的）
• 缓冲区中的下一个未读元素
• 数组的结尾，即缓冲区环绕到数组开头的点

ring_buffer的容量cap是指底层存储空间的总长度，大小size是实际占用的未读的数据长度。

所以用data表示底层数组，用w和r表示下一个可写索引和下一个可读索引，w和r的初始值可以有不同的设计。比如，让w=r=0，则cap=len(data)，size=w-r+1（要求w>=r，否则表示数据覆写了）。

判断缓冲区满就是size == cap，如果再写入需要确定是否能覆盖旧数据，可以覆盖旧数据，或者需要阻塞等待r消费一个数据，或者直接返回失败。

判断缓冲区空，需要根据w和r的初始值。如果让w、r都从0开始，w==r就表示缓冲区空，注意这要求没有经过数据覆写。

package main

import (
    "errors"
    "fmt"
    "sync"
)

type T interface{}

type RB struct {
    sync.RWMutex
    data []T
    size int
    cap int
    w int
    r int
}

func NewRB(capacity int) *RB{
    return &RB{
        data: make([]T, capacity),
        size: 0,
        cap: capacity,
        w: 0,
        r: 0,
    }
}

func (rb *RB) Write(t T) error{
    rb.Lock()
    defer rb.Unlock()

    // 不支持覆盖数据
    if rb.size == rb.cap {
        // 可以阻塞等待读
        return errors.New("buffer full")
    }
    rb.data[rb.r] = t
    rb.size = rb.size + 1
    rb.w = (rb.w + 1) % rb.cap
    return nil
}

func (rb *RB) Read() (T, error){
    rb.RLock()
    defer rb.RUnlock()

    // 不支持覆盖数据
    // 注意：由于r、w初始于同一位置，当w写完数据后如果出现环导致w还是落到了r的位置，这是就不能用r、w的对应关系来判断是否满空了，size就是用来弥补这个缺点的。
    if rb.size == 0 {
        // 可以阻塞等待写
        return nil, errors.New("buffer empty")
    }
    data := rb.data[rb.r]
    rb.size = rb.size - 1
    rb.r = (rb.r + 1) % rb.cap
    return data, nil
}

func (rb *RB) Size() int{
    rb.RLock()
    defer rb.RUnlock()
    return rb.size
}

func (rb *RB) IsFull() bool{
    rb.RLock()
    defer rb.RUnlock()
    return rb.size == rb.cap
}

func (rb *RB) IsEmpty() bool{
    rb.RLock()
    defer rb.RUnlock()
    return rb.size == 0
}

func main() {
    rb := NewRB(1)
    fmt.Println(rb.IsEmpty())
    fmt.Println(rb.IsFull())
    fmt.Println(rb.Size())

    v, err := rb.Read()
    fmt.Println(v, err)

    err = rb.Write("x")
    fmt.Println(err)
    fmt.Println(rb.IsEmpty())
    fmt.Println(rb.IsFull())
    fmt.Println(rb.Size())

    err = rb.Write("y")
    fmt.Println(err)

    v, err = rb.Read()
    fmt.Println(v, err)
    fmt.Println(rb.IsEmpty())
    fmt.Println(rb.IsFull())
    fmt.Println(rb.Size())

    v, err = rb.Read()
    fmt.Println(v, err)
}

/*
输出：
true
false
0

<nil> buffer empty

<nil>
false
true
1

buffer full

x <nil>
true
false
0

<nil> buffer empty
*/

尤其注意，因为是有环的，所以无论是w还是r经过N次操作后，下一个落点可能是任意的，所以不能用r、w的相互计算判断空还是满，所以才会增加size用来做读写前期判断，每次读写后对size增减。

比如r、w开始都是0，容量是1。初始没有数据当然无法读取。经过1次写入后，`(w+1) % cap`还是0，也就是说下一个要写的位置还是0，下一个要读的位置也是0，这到底能不能读？所以才要size。

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

最近最少使用（LRU）是一种缓存逐出算法，它按使用顺序组织元素。在LRU策略下，如果缓存容量已满要放入下一个元素，最长时间没有被使用的元素会被从缓存中逐出。

要求

• 所有操作都应按O(1)的顺序运行
• 缓存大小有限
• 所有缓存操作都必须支持并发
• 如果缓存已满，添加新项必须调用LRU策略

LRU Cache用双向链表实现。双向链表的头部表示最近有需要的节点，尾部表示很久都没有用过的节点。因为链表需要从一边开始遍历，如果规定了从头部读取，就要把有用的节点放头部，然后以不影响正常读写的方式并发或阻塞地去链表尾删除需要淘汰的节点。

将键值对插入缓存的步骤：

• 如果在缓存中找到key，则将其移动到双向链表的前面并更新value
• 否则，检查缓存的当前容量，若溢出，则从双向链表中删除最近最久未使用的条目
• 将新元素存储在列表的前面。

从缓存中读取键值对的步骤： 在返回值的同时，还需要将它移到双向链表的前面，以保持最近最少使用的逻辑。

这样LRU Cache结构需要一个双向链表，并提供最大容量、当前的元素数量，以及存储数据的结构。为了从两个方向分别进行增、删，还需要指定两个方向的指针起始位置。

虽然双向链表可以使用container/list包，但是自己实现可以指定要增删的指针位置，并且明白内部存储逻辑。

标准的双向链表和节点应该支持如下功能

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

type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element

要实现LRU Cache，需要使用到双向链表的New、PushFront、GetFront、DeleteBack、MoveToFront、Len功能。

因为container/list包实现的是一个环形双向链表，这里不需要环，所以将container/list包的内容搬出来一部分

package main

import (
    "fmt"
    "errors"
    "sync"
)

const SMALL_SIZE = 64 // 注意：不是 const var "x"
const BIG_SIZE = 1024

type T interface{} // 注意1.18后interface{}可以改成any

// 节点
type Element struct {
    next, prev *Element
    key T
    val T
    // Element不是环，所以不需要像container/list保存当前节点的root来源、长度len。并且不用考虑下一个节点是否会出现环，next指针可以替代Next()。
}

type List struct {
    sync.RWMutex
    cap int
    len int
    head *Element
    tail *Element
}

func New(cap int) (*List) {
    return new(List).Init(cap) // new一个对象指针后，派指定的Init()方法初始化
}

func (l *List) Init(cap int) (*List){
    l.Lock()
    defer l.Unlock()
    // 节点不能初始化，注意没有初始化的节点是nil，并且不能访问prev和next
	l.head = nil
	l.tail = nil

    l.len = 0
    l.cap = cap
    return l
}

// 从头部插入，如果超出容量就淘汰部分
func (l *List) PushFront(k, v T) (bool, error){
    l.Lock()
    defer l.Unlock()
    if l.len >= l.cap {
        // 阻塞淘汰 淘汰规则可以从New时用参数提供，这里简单硬编码。
        if l.cap <= SMALL_SIZE {
            // 举例：64删1
            l.DeleteBackWithoutLock()
        } else if l.cap <= BIG_SIZE {
            // 举例：64-1M删64分之一(也就是1-16)
            for i := 0; i < l.len / SMALL_SIZE; i++ {
                l.DeleteBackWithoutLock()
            }
        }else {
            // 举例：>1M删1M分之一
            for i := 0; i < l.cap / BIG_SIZE; i++ {
                l.DeleteBackWithoutLock()
            }
        }
    }
    if l.len >= l.cap {
        // 如果仍然空间不足，说明出现故障
        return false, errors.New("listfull")
    }

	p := &Element{key: k, val: v, prev: nil, next: nil}	

	if l.len == 0{
		l.head = p
		l.tail = p
	}else if l.len == 1{
		tmp := l.head
		l.tail = tmp
		p.next = tmp
		tmp.prev = p
		l.head = p
	} else {
		tmp := l.head
		p.next = tmp
		tmp.prev = p
		l.head = p
	}
	
	l.len++


	
    return true, nil
}

// 从末尾删除（上锁）
func (l *List) DeleteBack() (bool, error){
    l.Lock()
    defer l.Unlock()
	return l.DeleteBackWithoutLock()
}

// 从末尾删除（无锁），可以被其他上锁方法调用
func (l *List) DeleteBackWithoutLock() (bool, error){
    if l.len < 1 {
        return false, errors.New("list empty")
    }

	if l.tail.prev != nil {
		// 剩余>1个元素时，tail有prev。注意head.nex和tail.prev.next不是一码事，后者prev是nil时会报错
        l.tail.prev.next = nil
		l.tail = l.tail.prev
	} else {
		// 如果仅剩一个元素时，head和tail的prev和tail都是nil，如果不判断就直接拿prev.next会报错nil pointer
		l.tail.key = nil
        l.tail.val = nil
		l.tail.next = nil
		l.tail.prev = nil
		l.head.key = nil
		l.head.next = nil
		l.head.prev = nil
	}
    l.len--
    return true, nil
}

// 从头查找，找到就移动到头部
func (l *List) GetFromFront(k T) (T, bool,  error){
    l.Lock()
    defer l.Unlock()

    if l.len == 0 {
        return nil, false, errors.New("empty list")
    }
    for p := l.head; p != nil; p = p.next {
        if p.key == k {
            ok, err := l.MoveToFrontWithoutLock(p)
            return p.val, ok, err
        }
    }
    return nil, false, errors.New("can't find key")
}

func (l *List) MoveToFrontWithoutLock(p *Element) (bool, error){
    if l.len == 0 {
        return false, errors.New("empty list")
    } else if l.len == 1 {
        return true, nil
    } else {
		// 如果是头节点，直接返回，否则最后将p放到头部的逻辑如果不判断p是否就是head会导致head.next=head
		if p == l.head {
			return true, nil
		}
        // 将p从原链表中摘除并缝合原链（包含p是尾节点的处理）
		if p.prev != nil {
			p.prev.next = p.next
			if p.next != nil {
				p.next.prev = p.prev
			}
		}
        // 如果p是尾节点，需要重置尾结点
        if l.tail == p {
            l.tail = p.prev
        }
        // p放到头部
		if p != l.head {
        	l.head.prev = p
        	p.next = l.head
		}
        p.prev = nil
        l.head = p
        return true, nil
    }
}

func main() {
	l := New(1)
    fmt.Println("初始化容量=1的双向链表")
	
    fmt.Println("删除空list（不能报错）")
    ok, err := l.DeleteBack()
	fmt.Println(ok, err)
    fmt.Println(l.len)
    fmt.Println(l.head)
	// fmt.Println(l.head.prev) // 由于空list的head是nil，所以不存在key、val、prev和next，会报错。更好的做法是next和prev只能通过方法Next()和Prev()访问
	// fmt.Println(l.head.next)
    // fmt.Println(l.head.val)
    fmt.Println(l.tail)
	// fmt.Println(l.tail.prev)
	// fmt.Println(l.tail.next)
    // fmt.Println(l.tail.val)
	fmt.Println()

    fmt.Println("向空list添加一个元素")
    ok, err = l.PushFront("x", "x")
	fmt.Println(ok, err)
    fmt.Println(l.len)
    fmt.Println(l.head.val)
    fmt.Println(l.tail.val)
	fmt.Println()
	
    fmt.Println("从容量=1的非空list删除一个元素变成空list")
	ok, err = l.DeleteBack()
	fmt.Println(ok, err)
    fmt.Println(l.len)
    // fmt.Println(l.head.val) // 报错
    // fmt.Println(l.tail.val) // 报错
	fmt.Println()
	
    fmt.Println("向容量=1的list添加2个元素，让老元素阻塞淘汰")
	ok, err = l.PushFront("x", "x")
	ok, err = l.PushFront("y", "y")
	fmt.Println(ok, err)
    fmt.Println(l.len)
    fmt.Println(l.head.val)
    fmt.Println(l.tail.val)
	fmt.Println()
	
    fmt.Println("-------------------\n")
    
    fmt.Println("初始化容量=3的双向链表")
	l = New(3)
	ok, err = l.PushFront("x", "x")
	ok, err = l.PushFront("y", "y")
	ok, err = l.PushFront("z", "z")
	
    fmt.Println("连续插入三个元素")
    fmt.Println("头节点、前驱、后继节点")
	fmt.Println(l.head)
	fmt.Println(l.head.prev)
	fmt.Println(l.head.next)
	fmt.Println()
	
    fmt.Println(l.head.next)
	fmt.Println(l.head.next.prev)
	fmt.Println(l.head.next.next)
	fmt.Println()
	
    fmt.Println(l.tail)
	fmt.Println(l.tail.prev)
	fmt.Println(l.tail.next)
	fmt.Println()

    fmt.Println("查找不存在的缓存")
    v, ok, err := l.GetFromFront("a")
    fmt.Println(v, ok, err)
	fmt.Println()

    fmt.Println("查找位于head位置的缓存")
    v, ok, err = l.GetFromFront("z")
    fmt.Println(v, ok, err)
	fmt.Println()
    
    fmt.Println(l.head)
	fmt.Println(l.head.prev)
	fmt.Println(l.head.next)
	fmt.Println()
	
    fmt.Println(l.head.next)
	fmt.Println(l.head.next.prev)
	fmt.Println(l.head.next.next)
	fmt.Println()
	
    fmt.Println(l.tail)
	fmt.Println(l.tail.prev)
	fmt.Println(l.tail.next)
	fmt.Println()

    fmt.Println("查找位于中间或末尾位置的缓存")
    v, ok, err = l.GetFromFront("x")
    fmt.Println(v, ok, err)
	fmt.Println()

    fmt.Println(l.head)
	fmt.Println(l.head.prev)
	fmt.Println(l.head.next)
	fmt.Println()
	
    fmt.Println(l.head.next)
	fmt.Println(l.head.next.prev)
	fmt.Println(l.head.next.next)
	fmt.Println()
	
    fmt.Println(l.tail)
	fmt.Println(l.tail.prev)
	fmt.Println(l.tail.next)
	fmt.Println()

    fmt.Println("从容量=3的非空list尾部删除一个元素变成非空list")
	ok, err = l.DeleteBack()
	fmt.Println(ok, err)
    fmt.Println(l.len)

    fmt.Println(l.head)
	fmt.Println(l.head.prev)
	fmt.Println(l.head.next)
	fmt.Println()
	
    fmt.Println(l.head.next)
	fmt.Println(l.head.next.prev)
	fmt.Println(l.head.next.next)
	fmt.Println()
	
    fmt.Println(l.tail)
	fmt.Println(l.tail.prev)
	fmt.Println(l.tail.next)
	fmt.Println()

}

```go
输出：

初始化容量=1的双向链表
删除空list（不能报错）
false list empty
0
<nil>
<nil>

向空list添加一个元素
true <nil>
1
x
x

从容量=1的非空list删除一个元素变成空list
true <nil>
0

向容量=1的list添加2个元素，让老元素阻塞淘汰
true <nil>
1
y
y

-------------------

初始化容量=3的双向链表
连续插入三个元素
头节点、前驱、后继节点
&{0xc00005e210 <nil> z z}
<nil>
&{0xc00005e1e0 0xc00005e240 y y}

&{0xc00005e1e0 0xc00005e240 y y}
&{0xc00005e210 <nil> z z}
&{<nil> 0xc00005e210 x x}

&{<nil> 0xc00005e210 x x}
&{0xc00005e1e0 0xc00005e240 y y}
<nil>

查找不存在的缓存
<nil> false can't find key

查找位于head位置的缓存
z true <nil>

&{0xc00005e210 <nil> z z}
<nil>
&{0xc00005e1e0 0xc00005e240 y y}

&{0xc00005e1e0 0xc00005e240 y y}
&{0xc00005e210 <nil> z z}
&{<nil> 0xc00005e210 x x}

&{<nil> 0xc00005e210 x x}
&{0xc00005e1e0 0xc00005e240 y y}
<nil>

查找位于中间或末尾位置的缓存
x true <nil>

&{0xc00005e240 <nil> x x}
<nil>
&{0xc00005e210 0xc00005e1e0 z z}

&{0xc00005e210 0xc00005e1e0 z z}
&{0xc00005e240 <nil> x x}
&{<nil> 0xc00005e240 y y}

&{<nil> 0xc00005e240 y y}
&{0xc00005e210 0xc00005e1e0 z z}
<nil>

从容量=3的非空list删除一个元素变成非空list
true <nil>
2
&{0xc00005e240 <nil> x x}
<nil>
&{<nil> 0xc00005e1e0 z z}

&{<nil> 0xc00005e1e0 z z}
&{0xc00005e240 <nil> x x}
<nil>

&{<nil> 0xc00005e1e0 z z}
&{0xc00005e240 <nil> x x}
<nil>

双向链表比单链表复杂很多，容易出错。

图graph

图是网络结构的表示。现实世界中有大量图谱示例，互联网和社交图谱就是经典示例。图基本上是一组由边连接的节点。

顶点之间的关系可以是有向的或无向的，也可能是有环的。

有向图的连接线被称为弧，自然就存在弧头和弧尾。对一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度，反之就是出度。

图的集合表示，有向图的集合举例VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}

无论是无向图还是有向图，从一个顶点到另一顶点途经的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为”回路”（或”环”）。

和二叉树类似，若图中各个顶点都与除自身外的其他顶点有直接关系，这样的无向图称为完全图。具有 n 个顶点的完全图，图中边的数量为 n(n-1)/2；而对于具有 n 个顶点的有向完全图，图中弧的数量为 n(n-1)。

根据图有无权，可以将图划分为两大类：图和网 。

图结构有邻接矩阵（二维数组）或邻接表（链表）两种实现方式。

在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。

二维切片在go中的初始化方法：

	// 方法0
	row, column := 3, 4
	var answer [][]int
	for i := 0; i < row; i++ {
		inline := make([]int, column)
		answer = append(answer, inline)
	}
	fmt.Println(answer)

	// 方法1
	answer1 := make([][]int, row)
	for i := range answer1 {
		answer1[i] = make([]int, column)
	}
	fmt.Println(answer1)

二维数组所占据的空间为O(V^2)，V为节点总数。所需内存随着节点增加而迅速增多。如果边不是很密集，那么很多数组元素记为0，只有稀疏的一些数组元素记为1，所以并不是很经济。

更经济的实现方式是使用邻接表(adjacency list)，即记录每个节点所有的相邻节点。对任意节点m创建一个链表，如果有节点k联通到m，就把此节点加入到m的链表中。邻接表是实现图的标准方式。

var graph []Node // 保存所有的节点

type Node struct { // 每个节点都需要保存graph中的X节点到当前节点A的weight，next保存另一个能联通到X节点的节点B的weight
    weight int
    next *Node
}

需要实现：

• AddNode()：添加一个节点到图里
• AddEdge()：添加一条边到图里
• Print()：打印图结构

邻接矩阵（二维数组）实现图

// 图的二维数组实现
package main

import (
    "fmt"
    "sync"
    "strconv" // Atoi
    // "reflect"
    "errors"
)

type T int

// 顶点vertex
type Node struct {
    name string
}

type Graph struct {
    sync.RWMutex
    edges [][]int // 二维切片存边（顶点的关系）
    nodes []Node // 一维切片存节点
}

func NewGraph(n int, node_names []string) (*Graph){
    nodes := make([]Node, 0, n)
    for _, node_name := range node_names { // 注意for range中一个变量是指k而不是v
        nodes = append(nodes, Node{
            name: node_name,
        })
    }
    edges := make([][]int, n) // 注意二维写法。如果是长款不等的二维切片要先用row生成，再用column生成
    for k, _ := range edges { // 注意只用k值，先遍历x坐标
        edges[k] = make([]int, n) // 注意写法
    }
    return &Graph{
        edges: edges,
        nodes: nodes,
    }
}

func (g *Graph) Print() {
    g.Lock()
    defer g.Unlock()

    fmt.Println("--------------------")
    head := "Graph\t"
    for _, v := range g.nodes { // 注意for range中一个变量是指k而不是v
        // fmt.Println(reflect.TypeOf(v))
        head += v.name + "\t"
    }
    head += "\n"
    fmt.Println(head)
    content := ""
    for k1, v1 := range g.edges {
        content += g.nodes[k1].name + "\t"
        for k2,_ := range v1 { // 只用k
            content += strconv.Itoa(g.edges[k1][k2]) + "\t" // 注意Itoa
        }
        if k1 < len(g.edges) - 1 {
            content += "\n"
        }
    }
    fmt.Println(content)
    fmt.Println("--------------------")
}

func (g *Graph) AddNode(node_name string) (bool, error){
    g.Lock()
    defer g.Unlock()

    if node_name == "" {
        return false, errors.New("node name empty")
    }
    for _, v := range g.nodes {
        if v.name == node_name {
            return false, errors.New("node name exists")
        }
    }
    g.nodes = append(g.nodes, Node{
            name: node_name,
        })
    // 还要加边,arr[i][len]，以及arr[len][i]
    l := len(g.nodes)
    // 必须先填行，再填列，因为列要在循环中进行，如果没有最后一行，列就要在最后少循环一次，否则会报错
    g.edges = append(g.edges, make([]int, l - 1)) // 给g.edges[][]添加一行g.edges[n] = make([]int, l - 1)，这里不是l而是l-1，因为Graph[n][n]将在下面循环中补充
    for i := 0; i < l; i++ {
        g.edges[i] = append(g.edges[i], 0) // 给g.edges[i]追加一个零值，注意最后一个零值就是上面没加的g.edges[n][n]
    }
    fmt.Println(g.edges)

    return true, nil
}

func (g *Graph) CheckEdgeExistWithoutLock(node1, node2 Node) (int, int, error) {
    var k1 int = -1 // 注意，初始值不能是>=0的int，因为目标值可能是0。也不能不赋值，因为默认会给初始化为0
    var k2 int = -1
    for k, v := range g.nodes {
        if v.name == node1.name {
            k1 = k
        }
    }
    for k, v := range g.nodes { // 注意k，v是for内局部变量，与上面的kv作用域是不同的，需要被短声明
        if v.name == node2.name {
            k2 = k
        }
    }
    if k1 != k2 && k1 != -1 && k2 != -1 { // 注意即使没有初始化，初值也是0，而不能用nil判断，否则会报错
        return k1, k2, nil
    }
    return -1, -1, errors.New("edge not exist")
}

func (g *Graph) SetEdge(node1, node2 Node, weight int) (bool, error){
    g.Lock()
    defer g.Unlock()
    k1, k2, err := g.CheckEdgeExistWithoutLock(node1, node2)
    if err != nil {
        return false, err
    }
    g.edges[k1][k2] = weight
    return true, nil
}

func (g *Graph) GetEdge(node1, node2 Node) (int, error){
    g.RLock()
    defer g.RUnlock()
    k1, k2, err := g.CheckEdgeExistWithoutLock(node1, node2)
    if err != nil {
        return -1, err
    }
    return g.edges[k1][k2], nil
}

func main() {
    n := 3
    node_names := make([]string, 0, n)
    node_names = append(node_names, "A", "B", "C") // 实际上应该改成提交Node类型的参数
    g := NewGraph(n, node_names)
    node1 := Node{"A"}
    node2 := Node{"B"}
    node3 := Node{"C"}
    g.SetEdge(node1, node2, 2)
    g.SetEdge(node3, node1, 3)
    g.Print()
    g.AddNode("D")
    g.Print()
    node4 := Node{"D"}
    g.SetEdge(node4, node1, 5)
    g.SetEdge(node1, node4, 6)
    g.Print()
    fmt.Println(g.GetEdge(node1, node4))
}

/*
输出：
--------------------
Graph	A	B	C	

A	0	2	0	
B	0	0	0	
C	3	0	0	
--------------------
[[0 2 0 0] [0 0 0 0] [3 0 0 0] [0 0 0 0]]
--------------------
Graph	A	B	C	D	

A	0	2	0	0	
B	0	0	0	0	
C	3	0	0	0	
D	0	0	0	0	
--------------------
--------------------
Graph	A	B	C	D	

A	0	2	0	6	
B	0	0	0	0	
C	3	0	0	0	
D	5	0	0	0	
--------------------
*/

邻接表（链表）实现图

package main

import (
    "fmt"
    "sync"
    // "reflect"
    "unsafe"
)
var graph []Node // 保存所有的节点

type Graph struct {
    sync.RWMutex
    nodes []*Node
}

type Node struct { // 一个顶点后面链上多个边，保存从当前顶点到其他顶点的距离
    name string
    next *Edge
}

type Edge struct { // 每个Edge都需要保存graph中的X节点到当前节点A的weight，next保存另一个能联通到X节点的节点B的weight
    node *Node
    weight int
    next *Edge
}

func NewNode(name string) *Node{
    return &Node{
        name: name,
    }
}

func NewEdge(node2 *Node, weight int) *Edge{
    return &Edge{
        node: node2,
        weight: weight,
    }
}

func NewGraph(size int) *Graph{
    return &Graph{
        nodes: make([]*Node, 0, size),
    }
}

func (g *Graph) AddNode(node *Node) {
    g.Lock()
    defer g.Unlock()
    g.nodes = append(g.nodes, node)
}

func (g *Graph) AddEdge(node1, node2 *Node, weight int) {
    g.Lock()
    defer g.Unlock()
    // 省略：判断是否存在CheckExistWithoutLock
    head := g.nodes[0]
    if unsafe.Pointer(head.next) == nil {
        head.next = NewEdge(node2, weight)
    } else {
        tmp := head.next
        for unsafe.Pointer(tmp.next) != nil {
            tmp = tmp.next
        }
        tmp.next = NewEdge(node2, weight)
    }
}

func (g *Graph) PrintTarget(node1, node2 *Node) string {
    ret := ""
    return ret
}

func main() {
    g := NewGraph(3)
    n1 := NewNode("A")
    n2 := NewNode("B")
    n3 := NewNode("C")
    g.AddNode(n1)
    g.AddNode(n2)
    g.AddNode(n3)
    g.AddEdge(n1, n2, 1)
    g.AddEdge(n1, n3, 2)
    
    fmt.Println("n1->n2，打印n2节点")
    e2 := g.nodes[0].next
    fmt.Println(e2)
    fmt.Println(e2.weight)
    fmt.Println(e2.node.name)
    fmt.Println(e2.next)
    fmt.Println()
    
    fmt.Println("n1->n2->n3，打印n3节点")
    e3 := e2.next
    fmt.Println(e3)
    fmt.Println(e3.weight)
    fmt.Println(e3.node.name)
    fmt.Println(e3.next)
}

/*
输出：
n1->n2，打印n2节点
&{0xc00000c0a0 1 0xc00000c100}
1
B
&{0xc00000c0c0 2 }
n1->n2->n3，打印n3节点
&{0xc00000c0c0 2 }
2
C
nil
*/

不再针对链表结构做过多实现，包括Print、GetTargetByStart、GetEdge、SetEdge、CheckEdgeExistWithUnlock等都比较简单。

深度和广度优先搜索

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然深度优先搜索是一个递归的过程，注意如果一个顶点没有邻接点时，这个顶点的深度优先就到头了，需要返回到上一层，直到有还没被访问的邻接点时才继续。直到最终将初始顶点和后续顶点的邻接点都访问到了，没有其他邻接点时遍历结束。

比如a连通b、c、d，b连通e，d连通f。访问顺序就是abecdf。

广度优先搜索算法(Breadth First Search)，又称为”宽度优先搜索”或”横向优先搜索”，简称BFS。

它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。类似于树的按层遍历。

比如a连通b、c、d，b连通e，d连通f。访问顺序就是abcdef。

在实现搜索的代码中，可以用集合Set存储遍历过的顶点，避免重复访问。对链表实现来说，广度优先更好编码，因为所有邻接顶点都在同一个Node后链着，一次性可以遍历完，一边记录到Set，一边记录到待后续遍历的slice。这一层遍历完后，下一层按照slice的顺序继续遍历直到找不到Set中不存在的邻接顶点就表示以此顶点开始的搜索结束了。

注意，如果是多顶点结构，还需要从其他顶点开始搜索。

求最短路径

在实际场景中，求图中两个节点的最短路径，以及”一笔画”（不重复送信）问题。

floyed

dijkstra

通道channel

主要参考

leetcode刷题指南

Go的数据结构与实现

Golang 数据结构和算法

图解！24张图彻底弄懂九大常见数据结构！