使用go實現(xiàn)常見的數(shù)據(jù)結構
更新時間：2021年03月03日 11:13:20 作者：x1aoda1
這篇文章主要介紹了使用go實現(xiàn)常見的數(shù)據(jù)結構,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
1 golang常見數(shù)據(jù)結構實現(xiàn)
1.1 鏈表
舉單鏈表的例子，雙向鏈表同理只是多了pre指針。
定義單鏈表結構：
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 節(jié)點上
node2 := new(LinkNode)
node2.Data = 3
node1.NextNode = node2 // node2 鏈接到 node1 節(jié)點上
// 順序打印。把原鏈表頭結點賦值到新的NowNode上
// 這樣仍然保留了原鏈表頭結點node不變
nowNode := node
for nowNode != nil {
fmt.Println(nowNode.Data)
// 獲取下一個節(jié)點。鏈表向下滑動
nowNode = nowNode.NextNode
}
}
1.2 可變數(shù)組
可變數(shù)組在各種語言中都非常常用，在golang中，可變數(shù)組語言本身已經(jīng)實現(xiàn)，就是我們的切片slice。
1.3 棧和隊列
1.3.1 原生切片實現(xiàn)棧和隊列
棧：先進后出，后進先出，類似彈夾
隊列：先進先出
golang中，實現(xiàn)并發(fā)不安全的棧和隊列，非常簡單，我們直接使用原生切片即可。
1.3.1.1 切片原生棧實現(xiàn)
func main() {
// 用切片制作一個棧
var stack []int
// 元素1 入棧
stack = append(stack, 1, 5, 7, 2)
// 棧取出最近添加的數(shù)據(jù)。例如[1,5,7,2] ，len = 4
x := stack[len(stack)-1] // 2
// 切掉最近添加的數(shù)據(jù)，上一步和這一步模仿棧的pop。
stack = stack[:len(stack)-1] // [1,5,7]
fmt.Printf("%d", x)
}
1.3.1.2 切片原生隊列實現(xiàn)
func main() {
// 用切片模仿隊列
var queue []int
// 進隊列
queue = append(queue, 1, 5, 7, 2)
// 隊頭彈出，再把隊頭切掉，模仿隊列的poll操作
cur := queue[0]
queue = queue[1:]
fmt.Printf("%d", cur)
}
1.3.2 *并發(fā)安全的棧和隊列
1.3.2.1 切片實現(xiàn)并發(fā)安全的棧并發(fā)安全的棧
// 數(shù)組棧，后進先出
type Mystack struct {
array []string // 底層切片
size int // 棧的元素數(shù)量
lock sync.Mutex // 為了并發(fā)安全使用的鎖
}
入棧
// 入棧
func (stack *Mytack) Push(v string) {
stack.lock.Lock()
defer stack.lock.Unlock()
// 放入切片中，后進的元素放在數(shù)組最后面
stack.array = append(stack.array, v)
// 棧中元素數(shù)量+1
stack.size = stack.size + 1
}
出棧
1、如果切片偏移量向前移動 stack.array[0 : stack.size-1]，表明最后的元素已經(jīng)不屬于該數(shù)組了，數(shù)組變相的縮容了。此時，切片被縮容的部分并不會被回收，仍然占用著空間，所以空間復雜度較高，但操作的時間復雜度為：O(1)。
2、如果我們創(chuàng)建新的數(shù)組 newArray，然后把老數(shù)組的元素復制到新數(shù)組，就不會占用多余的空間，但移動次數(shù)過多，時間復雜度為：O(n)。
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]
// 創(chuàng)建新的數(shù)組，空間占用不會越來越大，但可能移動元素次數(shù)過多
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
// 棧中元素數(shù)量-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
}
1.3.2.2 切片實現(xiàn)并發(fā)安全的隊列隊列結構
// 數(shù)組隊列，先進先出
type Myqueue struct {
array []string // 底層切片
size int // 隊列的元素數(shù)量
lock sync.Mutex // 為了并發(fā)安全使用的鎖
}
入隊
// 入隊
func (queue *Myqueue) Add(v string) {
queue.lock.Lock()
defer queue.lock.Unlock()
// 放入切片中，后進的元素放在數(shù)組最后面
queue.array = append(queue.array, v)
// 隊中元素數(shù)量+1
queue.size = queue.size + 1
}
出隊
1、原地挪位，依次補位 queue.array[i-1] = queue.array[i]，然后數(shù)組縮容：queue.array = queue.array[0 : queue.size-1]，但是這樣切片縮容的那部分內存空間不會釋放。
2、創(chuàng)建新的數(shù)組，將老數(shù)組中除第一個元素以外的元素移動到新數(shù)組。
// 出隊
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++ {
// 從第一位開始進行數(shù)據(jù)移動
queue.array[i-1] = queue.array[i]
}
// 原數(shù)組縮容
queue.array = queue.array[0 : queue.size-1]
*/
// 創(chuàng)建新的數(shù)組，移動次數(shù)過多
newArray := make([]string, queue.size-1, queue.size-1)
for i := 1; i < queue.size; i++ {
// 從老數(shù)組的第一位開始進行數(shù)據(jù)移動
newArray[i-1] = queue.array[i]
}
queue.array = newArray
// 隊中元素數(shù)量-1
queue.size = queue.size - 1
return v
}
1.4 字典Map和集合Set
1.4.1 Map
字典也是程序語言經(jīng)常使用的結構，golang中的字典是其自身實現(xiàn)的map結構。具體操作可以查看語言api
并發(fā)安全的map，可以定義結構，結構中有一個map成員和一個鎖變量成員，參考并發(fā)安全的棧和隊列的實現(xiàn)。go語言也實現(xiàn)了一個并發(fā)安全的map,具體參考sync.map的api
1.4.2 Set
我們可以借助map的特性，實現(xiàn)一個Set結構。
Set結構
map的值我們不適用，定義為空的結構體struct{}
// 集合結構體
type Set struct {
m map[int]struct{} // 用字典來實現(xiàn)，因為字段鍵不能重復
len int // 集合的大小
sync.RWMutex // 鎖，實現(xiàn)并發(fā)安全
}
初始化Set
// 新建一個空集合
func NewSet(cap int64) *Set {
temp := make(map[int]struct{}, cap)
return &Set{
m: temp,
}
}
往set中添加一個元素
// 增加一個元素
func (s *Set) Add(item int) {
s.Lock()
defer s.Unlock()
s.m[item] = struct{}{} // 實際往字典添加這個鍵
s.len = len(s.m) // 重新計算元素數(shù)量
}
刪除一個元素
// 移除一個元素
func (s *Set) Remove(item int) {
s.Lock()
s.Unlock()
// 集合沒元素直接返回
if s.len == 0 {
return
}
delete(s.m, item) // 實際從字典刪除這個鍵
s.len = len(s.m) // 重新計算元素數(shù)量
}
查看元素是否在集合set中
// 查看是否存在元素
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
}
1.5 二叉樹
二叉樹：每個節(jié)點最多只有兩個兒子節(jié)點的樹。
滿二叉樹：葉子節(jié)點與葉子節(jié)點之間的高度差為 0 的二叉樹，即整棵樹是滿的，樹呈滿三角形結構。在國外的定義，非葉子節(jié)點兒子都是滿的樹就是滿二叉樹。我們以國內為準。
完全二叉樹：完全二叉樹是由滿二叉樹而引出來的，設二叉樹的深度為 k，除第 k 層外，其他各層的節(jié)點數(shù)都達到最大值，且第 k 層所有的節(jié)點都連續(xù)集中在最左邊。
二叉樹結構定義
// 二叉樹
type TreeNode struct {
Data string // 節(jié)點用來存放數(shù)據(jù)
Left *TreeNode // 左子樹
Right *TreeNode // 右字樹
}
樹的遍歷
1、先序遍歷：先訪問根節(jié)點，再訪問左子樹，最后訪問右子樹。
2、后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點。
3、中序遍歷：先訪問左子樹，再訪問根節(jié)點，最后訪問右子樹。
4、層次遍歷：每一層從左到右訪問每一個節(jié)點。
// 先序遍歷
func PreOrder(tree *TreeNode) {
if tree == nil {
return
}
// 先打印根節(jié)點
fmt.Print(tree.Data, " ")
// 再打印左子樹
PreOrder(tree.Left)
// 再打印右字樹
PreOrder(tree.Right)
}
// 中序遍歷
func MidOrder(tree *TreeNode) {
if tree == nil {
return
}
// 先打印左子樹
MidOrder(tree.Left)
// 再打印根節(jié)點
fmt.Print(tree.Data, " ")
// 再打印右字樹
MidOrder(tree.Right)
}
// 后序遍歷
func PostOrder(tree *TreeNode) {
if tree == nil {
return
}
// 先打印左子樹
MidOrder(tree.Left)
// 再打印右字樹
MidOrder(tree.Right)
// 再打印根節(jié)點
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)
// 當前節(jié)點有左孩子，加入左孩子進隊列
if cur.Left != nil {
queue = append(queue, cur.Left)
}
// 當前節(jié)點有右孩子，加入右孩子進隊列
if cur.Right != nil {
queue = append(queue, cur.Right)
}
}
}
到此這篇關于用go實現(xiàn)常見的數(shù)據(jù)結構的文章就介紹到這了,更多相關go實現(xiàn)數(shù)據(jù)結構內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
基于golang uint8、int8與byte的區(qū)別說明
這篇文章主要介紹了基于golang uint8、int8與byte的區(qū)別說明，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
go使用errors.Wrapf()代替log.Error()方法示例
這篇文章主要為大家介紹了go使用errors.Wrapf()代替log.Error()的方法示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-08-08
對于go1.16的新變化,大家印象最深的可能是io包的大規(guī)模重構,但這個重構實際上還引進了一個優(yōu)化,這篇文章要說的就是這個優(yōu)化,所以本將給大家介紹golang是如何優(yōu)化目錄遍歷的,需要的朋友可以參考下2024-08-08
Go不支持類，而是提供了結構體。結構體中可以添加屬性和方法。這樣可以將數(shù)據(jù)和操作數(shù)據(jù)的方法綁定在一起，實現(xiàn)與類相似的效果。這篇文章介紹了go語言中的面向對象，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
Go語言使用Timeout Context取消任務的實現(xiàn)
本文主要介紹了Go語言使用Timeout Context取消任務的實現(xiàn),包括基本的任務取消和控制HTTP客戶端請求的超時,具有一定的參考價值,感興趣的可以了解一下2024-01-01
這篇文章主要介紹了Go處理PDF的實現(xiàn)代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-01-01
這篇文章主要介紹了golang 對私有函數(shù)進行單元測試的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05
這篇文章主要介紹了淺談go中defer的一個隱藏功能，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-12-12
這篇文章主要介紹了go語言中json處理方式,文中通過實例代碼講解的非常詳細,對大家的學習或工作有一定的幫助,感興趣的小伙伴跟著小編一起來看看吧2024-05-05
Golang實現(xiàn)優(yōu)雅的將struct轉換為map
在項目實踐中，有時候我們需要將struct結構體轉為map映射表，然后基于map做數(shù)據(jù)裁剪或操作。那么下面我來介紹下常用的兩種轉換方式，希望對大家有所幫助2023-01-01