Golang中实现常用数据结构

来源：千锋教育

发布人：xqq

时间： 2023-12-22 08:15:47

Golang中实现常用数据结构

在编程中，数据结构是不可或缺的一部分，它们帮助我们组织和处理数据。在Golang中，有许多内置的数据结构，如数组、切片、map等。但是这些数据结构不一定能够满足我们的需求。因此，在这篇文章中，我们将探讨如何实现Golang中一些常用的数据结构，如栈、队列、链表和堆。

1. 栈

栈是一种LIFO（Last In, First Out）数据结构，它的元素遵循后进先出的规则。栈通常有两个基本操作：push（将元素添加到栈的顶部）和pop（从栈的顶部删除元素）。

在Golang中，我们可以使用slice轻松实现栈：

`go

type Stack interface{}

func (s *Stack) Push(value interface{}) {

*s = append(*s, value)

}

func (s *Stack) Pop() interface{} {

if s.Len() == 0 {

return nil

}

lastIndex := s.Len() - 1

value := (*s)

*s = (*s)

return value

}

func (s *Stack) Len() int {

return len(*s)

}

使用这个栈的例子：`gos := Stack{}s.Push(1)s.Push(2)s.Push(3)fmt.Println(s.Pop()) // 3fmt.Println(s.Pop()) // 2fmt.Println(s.Pop()) // 1fmt.Println(s.Pop()) // nil

2. 队列

队列是一种FIFO（First In, First Out）数据结构，它的元素遵循先进先出的规则。队列通常包括两个基本操作：enqueue（将元素添加到队列的末尾）和dequeue（从队列的头部删除元素）。

在Golang中，我们可以使用slice和两个指针（一个指向队列的开头，另一个指向队列的结尾）来轻松实现一个队列：

`go

type Queue interface{}

func (q *Queue) Enqueue(value interface{}) {

*q = append(*q, value)

}

func (q *Queue) Dequeue() interface{} {

if q.Len() == 0 {

return nil

}

value := (*q)

*q = (*q)

return value

}

func (q *Queue) Len() int {

return len(*q)

}

使用这个队列的例子：`goq := Queue{}q.Enqueue(1)q.Enqueue(2)q.Enqueue(3)fmt.Println(q.Dequeue()) // 1fmt.Println(q.Dequeue()) // 2fmt.Println(q.Dequeue()) // 3fmt.Println(q.Dequeue()) // nil

3. 链表

链表是一种线性数据结构，它由一系列节点组成，每个节点都包括数据和一个指向下一个节点的指针。链表可以是单向的（每个节点只有一个指针，指向下一个节点）、双向的（每个节点有两个指针，一个指向前一个节点，另一个指向后一个节点）或循环的（最后一个节点指向头结点）。

在Golang中，我们可以使用结构体来定义一个单向链表的节点：

`go

type Node struct {

Value interface{}

Next *Node

}

然后使用这个结构体来实现链表：`gotype LinkedList struct {    Head *Node    Len  int}func (l *LinkedList) PushFront(value interface{}) {    node := &Node{Value: value}    if l.Head == nil {        l.Head = node    } else {        node.Next = l.Head        l.Head = node    }    l.Len++}func (l *LinkedList) PushBack(value interface{}) {    node := &Node{Value: value}    if l.Head == nil {        l.Head = node    } else {        tail := l.Head        for tail.Next != nil {            tail = tail.Next        }        tail.Next = node    }    l.Len++}func (l *LinkedList) Remove(value interface{}) {    if l.Head == nil {        return    }    if l.Head.Value == value {        l.Head = l.Head.Next        l.Len--        return    }    prev := l.Head    curr := l.Head.Next    for curr != nil {        if curr.Value == value {            prev.Next = curr.Next            l.Len--            break        }        prev = curr        curr = curr.Next    }}func (l *LinkedList) Len() int {    return l.Len}

使用这个链表的例子：

`go

l := LinkedList{}

l.PushFront(1)

l.PushBack(2)

l.PushBack(3)

fmt.Println(l.Len()) // 3

l.Remove(2)

fmt.Println(l.Len()) // 2

4. 堆堆是一种树形数据结构，在堆中，每个节点的值总是大于等于（或小于等于）其子节点的值。堆通常用来实现优先级队列。在Golang中，我们可以使用heap包提供的接口来实现堆。首先，我们需要定义一个我们想要使用的类型，并让它实现heap.Interface接口：`gotype IntHeap intfunc (h IntHeap) Len() int {    return len(h)}func (h IntHeap) Less(i, j int) bool {    return h < h}func (h IntHeap) Swap(i, j int) {    h, h = h, h}func (h *IntHeap) Push(x interface{}) {    *h = append(*h, x.(int))}func (h *IntHeap) Pop() interface{} {    old := *h    n := len(old)    x := old    *h = old    return x}

然后，我们可以使用这个IntHeap来创建一个堆：

`go

h := &IntHeap{2, 1, 5}

heap.Init(h)

heap.Push(h, 3)

heap.Push(h, 4)

for h.Len() > 0 {

fmt.Println(heap.Pop(h))

}