使用go实现常见的数据结构

type LinkNode struct {
	Data int64
	NextNode *LinkNode
}

func main() {

	node := new(LinkNode)
	node.Data = 1

	node1 := new(LinkNode)
	node1.Data = 2
	node.NextNode = node1 // node1 链接到 node 节点上

	node2 := new(LinkNode)
	node2.Data = 3
	node1.NextNode = node2 // node2 链接到 node1 节点上

	// 顺序打印。把原链表头结点赋值到新的NowNode上
	// 这样仍然保留了原链表头结点node不变
	nowNode := node
	for nowNode != nil {
		fmt.Println(nowNode.Data)
		// 获取下一个节点。链表向下滑动
		nowNode = nowNode.NextNode
	}
}

func main() {
	// 用切片制作一个栈
	var stack []int
	// 元素1 入栈
	stack = append(stack, 1, 5, 7, 2)
	// 栈取出最近添加的数据。例如[1,5,7,2] ，len = 4
	x := stack[len(stack)-1] // 2
	// 切掉最近添加的数据，上一步和这一步模仿栈的pop。
	stack = stack[:len(stack)-1] // [1,5,7]
	fmt.Printf("%d", x)
}

func main() {

	// 用切片模仿队列
	var queue []int
	// 进队列
	queue = append(queue, 1, 5, 7, 2)
	// 队头弹出，再把队头切掉，模仿队列的poll操作
	cur := queue[0]
	queue = queue[1:]

	fmt.Printf("%d", cur)
}

// 数组栈，后进先出
type Mystack struct {
 array []string // 底层切片
 size int // 栈的元素数量
 lock sync.Mutex // 为了并发安全使用的锁
}

// 入栈
func (stack *Mytack) Push(v string) {
 stack.lock.Lock()
 defer stack.lock.Unlock()

 // 放入切片中，后进的元素放在数组最后面
 stack.array = append(stack.array, v)

 // 栈中元素数量+1
 stack.size = stack.size + 1
}

func (stack *Mystack) Pop() string {
 stack.lock.Lock()
 defer stack.lock.Unlock()

 // 栈中元素已空
 if stack.size == 0 {
 panic("empty")
 }

 // 栈顶元素
 v := stack.array[stack.size-1]

 // 切片收缩，但可能占用空间越来越大
 //stack.array = stack.array[0 : stack.size-1]

 // 创建新的数组，空间占用不会越来越大，但可能移动元素次数过多
 newArray := make([]string, stack.size-1, stack.size-1)
 for i := 0; i < stack.size-1; i++ {
 newArray[i] = stack.array[i]
 }
 stack.array = newArray

 // 栈中元素数量-1
 stack.size = stack.size - 1
 return v
}

// 获取栈顶元素
func (stack *Mystack) Peek() string {
 // 栈中元素已空
 if stack.size == 0 {
 panic("empty")
 }

 // 栈顶元素值
 v := stack.array[stack.size-1]
 return v
}

// 栈大小
func (stack *Mystack) Size() int {
 return stack.size
}

// 栈是否为空
func (stack *Mystack) IsEmpty() bool {
 return stack.size == 0
}

// 数组队列，先进先出
type Myqueue struct {
 array []string // 底层切片
 size int // 队列的元素数量
 lock sync.Mutex // 为了并发安全使用的锁
}

// 入队
func (queue *Myqueue) Add(v string) {
 queue.lock.Lock()
 defer queue.lock.Unlock()

 // 放入切片中，后进的元素放在数组最后面
 queue.array = append(queue.array, v)

 // 队中元素数量+1
 queue.size = queue.size + 1
}

// 出队
func (queue *Myqueue) Remove() string {
 queue.lock.Lock()
 defer queue.lock.Unlock()

 // 队中元素已空
 if queue.size == 0 {
 panic("empty")
 }

 // 队列最前面元素
 v := queue.array[0]

 /* 直接原位移动，但缩容后继的空间不会被释放
 for i := 1; i < queue.size; i++ {
 // 从第一位开始进行数据移动
 queue.array[i-1] = queue.array[i]
 }
 // 原数组缩容
 queue.array = queue.array[0 : queue.size-1]
 */

 // 创建新的数组，移动次数过多
 newArray := make([]string, queue.size-1, queue.size-1)
 for i := 1; i < queue.size; i++ {
 // 从老数组的第一位开始进行数据移动
 newArray[i-1] = queue.array[i]
 }
 queue.array = newArray

 // 队中元素数量-1
 queue.size = queue.size - 1
 return v
}

// 集合结构体
type Set struct {
 m map[int]struct{} // 用字典来实现，因为字段键不能重复
 len int // 集合的大小
 sync.RWMutex // 锁，实现并发安全
}

// 新建一个空集合
func NewSet(cap int64) *Set {
 temp := make(map[int]struct{}, cap)
 return &Set{
 m: temp,
 }
}

// 增加一个元素
func (s *Set) Add(item int) {
 s.Lock()
 defer s.Unlock()
 s.m[item] = struct{}{} // 实际往字典添加这个键
 s.len = len(s.m) // 重新计算元素数量
}

// 移除一个元素
func (s *Set) Remove(item int) {
 s.Lock()
 s.Unlock()

 // 集合没元素直接返回
 if s.len == 0 {
 return
 }

 delete(s.m, item) // 实际从字典删除这个键
 s.len = len(s.m) // 重新计算元素数量
}

// 查看是否存在元素
func (s *Set) Has(item int) bool {
 s.RLock()
 defer s.RUnlock()
 _, ok := s.m[item]
 return ok
}

// 查看集合大小
func (s *Set) Len() int {
 return s.len
}

// 集合是够为空
func (s *Set) IsEmpty() bool {
 if s.Len() == 0 {
 return true
 }
 return false
}

// 清除集合所有元素
func (s *Set) Clear() {
 s.Lock()
 defer s.Unlock()
 s.m = map[int]struct{}{} // 字典重新赋值
 s.len = 0 // 大小归零
}

func (s *Set) List() []int {
 s.RLock()
 defer s.RUnlock()
 list := make([]int, 0, s.len)
 for item := range s.m {
 list = append(list, item)
 }
 return list
}

// 二叉树
type TreeNode struct {
 Data string // 节点用来存放数据
 Left *TreeNode // 左子树
 Right *TreeNode // 右字树
}

// 先序遍历
func PreOrder(tree *TreeNode) {
 if tree == nil {
 return
 }

 // 先打印根节点
 fmt.Print(tree.Data, " ")
 // 再打印左子树
 PreOrder(tree.Left)
 // 再打印右字树
 PreOrder(tree.Right)
}

// 中序遍历
func MidOrder(tree *TreeNode) {
 if tree == nil {
 return
 }

 // 先打印左子树
 MidOrder(tree.Left)
 // 再打印根节点
 fmt.Print(tree.Data, " ")
 // 再打印右字树
 MidOrder(tree.Right)
}

// 后序遍历
func PostOrder(tree *TreeNode) {
 if tree == nil {
 return
 }

 // 先打印左子树
 MidOrder(tree.Left)
 // 再打印右字树
 MidOrder(tree.Right)
 // 再打印根节点
 fmt.Print(tree.Data, " ")
}

func Level(head *TreeNode) {

	if head == nil {
		return
	}

	// 用切片模仿队列
	var queue []*TreeNode
	queue = append(queue, head)

	for len(queue) != 0 {
		// 队头弹出，再把队头切掉，模仿队列的poll操作
		cur := queue[0]
		queue = queue[1:]

		fmt.Printf("%d", (*cur).Data)

		// 当前节点有左孩子，加入左孩子进队列
		if cur.Left != nil {
			queue = append(queue, cur.Left)
		}

		// 当前节点有右孩子，加入右孩子进队列
		if cur.Right != nil {
			queue = append(queue, cur.Right)
		}
	}

}