背景
golang 不像c++，已经有stl这种通用的高级数据结构。所以如果想要栈，队列，链表等数据结构需要自己实现。
下面介绍下常用的几种数据结构
链表
单链表是一种链式存取的数据结构，一个链表由一个或者多个节点组成，每个节点有一个指针指向下一个节点。 以下是一个节点为int的链表实现。
package list type List struct { Head * ListNode length int } type ListNode struct { Next *ListNode Data int } func (p *List) AddNode(data int) { if p.Head == nil { p.Head = new(ListNode) } var node = &ListNode { Data : data, } currentNext := p.Head.Next p.Head.Next = node node.Next = currentNext } func (p *List) Lenth() int { return p.length } // delete specified pos func (p *List) DeleteWithPos(pos int) { if pos + 1 > p.length { return } var i int pre := p.Head for { if i == pos { pre.Next = pre.Next.Next } pre = pre.Next i++ } return } func (p *List) DeleteWithData(data int) { pre := p.Head for { if pre.Next == nil { break } if data == pre.Next.Data { pre.Next = pre.Next.Next } pre = pre.Next } return } 复制代码队列
队列和生活中排队的队伍比较相似。特性是FIFO(first in first out)，先进先出。 第一个进入队列的，会第一个出来。举个例子，你去银行存钱，有10个人排队，第一个加入队伍的即1号，必定是第一个办理业务的。
那么看下golang 如何实现一个队列：
package queue import ( "errors" ) type Queue []interface{} func (queue *Queue) Len() int { return len(*queue) } func (queue *Queue) IsEmpty() bool { return len(*queue) == 0 } func (queue *Queue) Cap() int { return cap(*queue) } func (queue *Queue) Push(value interface{}) { *queue = append(*queue, value) } func (queue *Queue) Pop() (interface{}, error) { theQueue := *queue if len(theQueue) == 0 { return nil, errors.New("Out of index, len is 0") } value := theQueue[0] *queue = theQueue[1:len(theQueue)] return value, nil } 复制代码栈
一种先入后出的数据结构。 栈在生活中的场景，可以对应一个桶，里面装了大米，先放进去的最后才会被取出来。 这里使用interface实现一个相对通用的栈。
package stack import "errors" type Stack []interface{} func (stack Stack) Len() int { return len(stack) } func (stack Stack) IsEmpty() bool { return len(stack) == 0 } func (stack Stack) Cap() int { return cap(stack) } func (stack *Stack) Push(value interface{}) { *stack = append(*stack, value) } func (stack Stack) Top() (interface{}, error) { if len(stack) == 0 { return nil, errors.New("Out of index, len is 0") } return stack[len(stack)-1], nil } func (stack *Stack) Pop() (interface{}, error) { theStack := *stack if len(theStack) == 0 { return nil, errors.New("Out of index, len is 0") } value := theStack[len(theStack)-1] *stack = theStack[:len(theStack)-1] return value, nil } 复制代码总结
以上是几种常见的高级数据结构，结合golang内置的数据结构，已经可以应对大多数业务场景的开发。后续将会介绍一些更复杂的数据结构，如跳表，二叉树，平衡二叉树，堆。
作者：牛牛码特
链接：https://juejin.cn/post/6844903918107885575
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
有疑问加站长微信联系（非本文作者）
