1 golang常见数据结构实现
1.1 链表
举单链表的例子，双向链表同理只是多了pre指针。
定义单链表结构：
构造链表及打印链表：
1.2 可变数组
可变数组在各种语言中都非常常用，在golang中，可变数组语言本身已经实现，就是我们的切片slice。
1.3 栈和队列
1.3.1 原生切片实现栈和队列
栈：先进后出，后进先出，类似弹夹
队列：先进先出
golang中，实现并发不安全的栈和队列，非常简单，我们直接使用原生切片即可。
1.3.1.1 切片原生栈实现
1.3.1.2 切片原生队列实现
1.3.2 *并发安全的栈和队列
1.3.2.1 切片实现并发安全的栈并发安全的栈
入栈
出栈
1、如果切片偏移量向前移动 stack.array[0 : stack.size-1]，表明最后的元素已经不属于该数组了，数组变相的缩容了。此时，切片被缩容的部分并不会被回收，仍然占用着空间，所以空间复杂度较高，但操作的时间复杂度为：o(1)。
2、如果我们创建新的数组 newarray，然后把老数组的元素复制到新数组，就不会占用多余的空间，但移动次数过多，时间复杂度为：o(n)。
获取栈顶元素
获取栈大小和判定是否为空
1.3.2.2 切片实现并发安全的队列队列结构
入队
出队
1、原地挪位，依次补位 queue.array[i-1] = queue.array[i]，然后数组缩容：queue.array = queue.array[0 : queue.size-1]，但是这样切片缩容的那部分内存空间不会释放。
2、创建新的数组，将老数组中除第一个元素以外的元素移动到新数组。
1.4 字典map和集合set
1.4.1 map
字典也是程序语言经常使用的结构，golang中的字典是其自身实现的map结构。具体操作可以查看语言api
并发安全的map，可以定义结构，结构中有一个map成员和一个锁变量成员，参考并发安全的栈和队列的实现。go语言也实现了一个并发安全的map,具体参考sync.map的api
1.4.2 set
我们可以借助map的特性，实现一个set结构。
set结构
map的值我们不适用，定义为空的结构体struct{}
初始化set
往set中添加一个元素
删除一个元素
查看元素是否在集合set中
查看集合大小
查看集合是否为空
清除集合所有元素
将集合转化为切片
1.5 二叉树
二叉树：每个节点最多只有两个儿子节点的树。
满二叉树：叶子节点与叶子节点之间的高度差为 0 的二叉树，即整棵树是满的，树呈满三角形结构。在国外的定义，非叶子节点儿子都是满的树就是满二叉树。我们以国内为准。
完全二叉树：完全二叉树是由满二叉树而引出来的，设二叉树的深度为 k，除第 k 层外，其他各层的节点数都达到最大值，且第 k 层所有的节点都连续集中在最左边。
二叉树结构定义
树的遍历
1、先序遍历：先访问根节点，再访问左子树，最后访问右子树。
2、后序遍历：先访问左子树，再访问右子树，最后访问根节点。
3、中序遍历：先访问左子树，再访问根节点，最后访问右子树。
4、层次遍历：每一层从左到右访问每一个节点。
按层遍历：
到此这篇关于用go实现常见的数据结构的文章就介绍到这了,更多相关go实现数据结构内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
