Go实现List、Set、Stack、Deque等数据结构

完整代码地址（欢迎大家⭐️）：https://github.com/ziyifast/ziyifast-code_instruction/tree/main/go-demo/go-data-structure
大家有接触过除Go其他语言（如：Java）可能就会想为什么Go没有像deque、stack、set、list这些常见的数据容器。尤其是对于那些习惯了用这些容器解决LeetCode问题的同学来说，就更为不便。

1 为什么Go原生不提供这些容器：为了简洁

Go语言自诞生以来就有着非常明确的目标，那就是简洁、高效、并发。为了实现这些目标，Go在设计上做了很多取舍。

简单性：Go语言团队的一个核心目标是保持语言的简单性。他们认为，如果一个功能可以用简单的组合来实现，那就没有必要把它放进标准库里。
deque、stack、set、list这些数据结构虽然常用，但它们并不是编写高效、可维护代码的唯一途径。通过组合切片和映射，开发者可以实现绝大多数需要的数据结构。
鼓励最佳实践：Go语言推崇一种“最小惊奇”的设计原则。也就是说，代码应该尽可能地容易理解和预测。标准库的设计哲学之一就是提供最少但足够的工具，让开发者能够按照最佳实践来编写代码。
这个哲学避免了标准库的膨胀，同时确保了代码的清晰性和可维护性。
社区的力量：Go语言的生态系统非常活跃，有很多高质量的第三方库可以提供你需要的高级数据结构。如果标准库包含了所有可能需要的数据结构，那它将变得非常庞大且难以维护。

相反，通过社区贡献，Go可以保持核心的简洁，同时又不失灵活性。

2 实现

完整代码地址：https://github.com/ziyifast/ziyifast-code_instruction/tree/main/go-demo/go-data-structure

虽然Go语言没有内置这些高级数据结构，但通过组合使用切片和映射，我们依然可以实现几乎所有需要的数据结构。

而且，这种方式更符合Go语言简洁、高效的设计哲学。
最重要的是，这也让我们更加理解这些数据结构的内部实现，而不仅仅是简单地调用现成的API。

所以，下次再遇到类似的问题，大家也可以自己试试看实现这些数据结构，既能提升编码能力，又能更深入地理解Go语言的设计理念。

List

思路：对于列表来说，通常需要有Add、Remove等操作，其实golang原生的切片就很接近切片，因此我们简单做封装即可

package mainimport ("errors""fmt"
)/*List:- NewList(): 创建一个新的列表- Add(element): 在列表末尾添加元素- Remove(index): 根据索引移除元素- Size(): 返回列表的大小- Get(index): 根据索引获取元素- IsEmpty(): 判断列表是否为空- Clear(): 清空列表- GetFirst(): 获取第一个元素- GetLast(): 获取最后一个元素- RemoveLast(): 移除最后一个元素- AddFirst(element): 在列表开头添加元素- RemoveFirst(): 移除第一个元素...
*/type List struct {data []interface{}
}// NewList 创建一个新的列表
func NewList() *List {return &List{data: []interface{}{},}
}// Add 在列表末尾添加元素
func (l *List) Add(v interface{}) {l.data = append(l.data, v)
}// Remove 根据索引移除元素
func (l *List) Remove(index int) error {if index < 0 || index >= len(l.data) {return errors.New("index out of bounds")}l.data = append(l.data[:index], l.data[index+1:]...)return nil
}// Size 返回列表的大小
func (l *List) Size() int {return len(l.data)
}// Get 根据索引获取元素
func (l *List) Get(index int) (interface{}, error) {if index < 0 || index >= len(l.data) {return nil, errors.New("index out of bounds")}return l.data[index], nil
}// IsEmpty 判断列表是否为空
func (l *List) IsEmpty() bool {return len(l.data) == 0
}// Clear 清空列表
func (l *List) Clear() {l.data = []interface{}{}
}// GetFirst 获取第一个元素
func (l *List) GetFirst() (interface{}, error) {if l.IsEmpty() {return nil, errors.New("list is empty")}return l.data[0], nil
}// GetLast 获取最后一个元素
func (l *List) GetLast() (interface{}, error) {if l.IsEmpty() {return nil, errors.New("list is empty")}return l.data[len(l.data)-1], nil
}// AddFirst 在列表开头添加元素
func (l *List) AddFirst(v interface{}) {l.data = append([]interface{}{v}, l.data...)
}// RemoveFirst 移除第一个元素
func (l *List) RemoveFirst() error {if l.IsEmpty() {return errors.New("list is empty")}l.data = l.data[1:]return nil
}// RemoveLast 移除最后一个元素
func (l *List) RemoveLast() error {if l.IsEmpty() {return errors.New("list is empty")}l.data = l.data[:len(l.data)-1]return nil
}func main() {list := NewList()// 测试 Add 和 Getlist.Add(1)list.Add(2)list.Add(3)value, err := list.Get(1)if err != nil {fmt.Println("Error:", err)} else {fmt.Println("Value at index 1:", value) // 输出: Value at index 1: 2}// 测试 Removeerr = list.Remove(1)if err != nil {fmt.Println("Error:", err)} else {fmt.Println("Size after remove:", list.Size()) // 输出: Size after remove: 2}// 测试 GetFirst 和 GetLastfirst, err := list.GetFirst()if err != nil {fmt.Println("Error:", err)} else {fmt.Println("First element:", first) // 输出: First element: 1}last, err := list.GetLast()if err != nil {fmt.Println("Error:", err)} else {fmt.Println("Last element:", last) // 输出: Last element: 3}// 测试 AddFirst 和 RemoveFirstlist.AddFirst(0)first, err = list.GetFirst()if err != nil {fmt.Println("Error:", err)} else {fmt.Println("First element after addFirst:", first) // 输出: First element after addFirst: 0}err = list.RemoveFirst()if err != nil {fmt.Println("Error:", err)} else {fmt.Println("Size after removeFirst:", list.Size()) // 输出: Size after removeFirst: 2}// 测试 RemoveLasterr = list.RemoveLast()if err != nil {fmt.Println("Error:", err)} else {fmt.Println("Size after removeLast:", list.Size()) // 输出: Size after removeLast: 1}// 测试 Clearlist.Clear()fmt.Println("Is list empty after clear?", list.IsEmpty()) // 输出: Is list empty after clear? true
}

Stack

Stack最大的特点就是：先进后出，这里底层存储我们也可以采用切片来进行封装

package mainimport ("fmt"
)/*Stack:- Push(item): 入栈- Pop(): 出栈- Peek(): 返回栈顶元素，但不删除它- IsEmpty(): 判断栈是否为空- Search(item): 搜索 item 元素在栈中的位置，如果没找到，返回 -1- Clear(): 清空栈...
*/type Stack struct {data []interface{}
}func NewStack() *Stack {return &Stack{data: []interface{}{},}
}// Push 入栈
func (s *Stack) Push(v interface{}) {s.data = append(s.data, v)
}// Pop 出栈
func (s *Stack) Pop() interface{} {if len(s.data) == 0 {return nil}val := s.data[len(s.data)-1]s.data = s.data[:len(s.data)-1]return val
}// Peek 返回栈顶元素，但不删除它
func (s *Stack) Peek() interface{} {if len(s.data) == 0 {return nil}return s.data[len(s.data)-1]
}// IsEmpty 判断栈是否为空
func (s *Stack) IsEmpty() bool {return len(s.data) == 0
}// Search 搜索 item 元素在栈中的位置，如果没找到，返回 -1
func (s *Stack) Search(v interface{}) int {for index, value := range s.data {if value == v {return index}}return -1
}// Clear 清空栈
func (s *Stack) Clear() {s.data = []interface{}{}
}func main() {stack := NewStack()// 测试 Push 和 Peekstack.Push(1)stack.Push(2)stack.Push(3)fmt.Println("Top element:", stack.Peek()) // 输出: Top element: 3// 测试 Popfmt.Println("Popped element:", stack.Pop())         // 输出: Popped element: 3fmt.Println("Top element after pop:", stack.Peek()) // 输出: Top element after pop: 2// 测试 IsEmptyfmt.Println("Is stack empty?", stack.IsEmpty()) // 输出: Is stack empty? false// 测试 Searchfmt.Println("Index of 2:", stack.Search(2)) // 输出: Index of 2: 1fmt.Println("Index of 3:", stack.Search(3)) // 输出: Index of 3: -1// 测试 Clearstack.Clear()fmt.Println("Is stack empty after clear?", stack.IsEmpty()) // 输出: Is stack empty after clear? true
}

Deque

Deque双端队列：前后都可以进出

package mainimport ("container/list""fmt"
)/*Deque:- PushFront: 在队列前端插入元素- PushBack: 在队列后端插入元素- PopFront: 从队列前端移除并返回元素- PopBack: 从队列后端移除并返回元素...
*/// Deque 双端队列结构体
type Deque struct {data *list.List
}// NewDeque 创建一个新的双端队列
func NewDeque() *Deque {return &Deque{data: list.New()}
}// PushFront 在队列前端插入元素
func (d *Deque) PushFront(value interface{}) {d.data.PushFront(value)
}// PushBack 在队列后端插入元素
func (d *Deque) PushBack(value interface{}) {d.data.PushBack(value)
}// PopFront 移除并返回队列前端的元素
func (d *Deque) PopFront() interface{} {front := d.data.Front()if front != nil {d.data.Remove(front)return front.Value}return nil
}// PopBack 移除并返回队列后端的元素
func (d *Deque) PopBack() interface{} {back := d.data.Back()if back != nil {d.data.Remove(back)return back.Value}return nil
}func main() {deque := NewDeque()// 测试 PushFront 和 PushBackdeque.PushBack(1)deque.PushFront(2)deque.PushBack(3)deque.PushFront(4)// 测试 PopFrontfmt.Println("Popped from front:", deque.PopFront()) // 输出: Popped from front: 4fmt.Println("Popped from front:", deque.PopFront()) // 输出: Popped from front: 2// 测试 PopBackfmt.Println("Popped from back:", deque.PopBack()) // 输出: Popped from back: 3fmt.Println("Popped from back:", deque.PopBack()) // 输出: Popped from back: 1// 测试空队列的情况fmt.Println("Popped from front on empty deque:", deque.PopFront()) // 输出: Popped from front on empty deque: <nil>fmt.Println("Popped from back on empty deque:", deque.PopBack())   // 输出: Popped from back on empty deque: <nil>// 再次测试 PushFront 和 PushBackdeque.PushFront(5)deque.PushBack(6)// 测试 PeekFront 和 PeekBackfmt.Println("Front element:", deque.PopFront()) // 输出: Front element: 5fmt.Println("Back element:", deque.PopBack())   // 输出: Back element: 6
}

Set

package mainimport ("fmt""sync"
)/*Set: 可以去除重复元素- Add: 添加元素- Remove: 删除元素- Contains: 检查元素是否存在- IsEmpty: 判断集合是否为空- Clear: 清空集合- Iterator: 返回一个迭代器通道...
*/type Set struct {mu   sync.RWMutexdata map[interface{}]bool
}// NewSet 创建一个新的集合
func NewSet() *Set {return &Set{data: make(map[interface{}]bool),}
}// Add 添加元素到集合
func (s *Set) Add(value interface{}) {s.mu.Lock()defer s.mu.Unlock()s.data[value] = true
}// Remove 从集合中删除元素
func (s *Set) Remove(value interface{}) {s.mu.Lock()defer s.mu.Unlock()delete(s.data, value)
}// Contains 检查元素是否存在于集合中
func (s *Set) Contains(value interface{}) bool {s.mu.RLock()defer s.mu.RUnlock()return s.data[value]
}// IsEmpty 判断集合是否为空
func (s *Set) IsEmpty() bool {s.mu.RLock()defer s.mu.RUnlock()return len(s.data) == 0
}// Clear 清空集合
func (s *Set) Clear() {s.mu.Lock()defer s.mu.Unlock()s.data = make(map[interface{}]bool)
}// Iterator 返回一个迭代器通道
func (s *Set) Iterator() <-chan interface{} {ch := make(chan interface{})go func() {defer func() {if r := recover(); r != nil {fmt.Println("Recovered in Iterator:", r)}close(ch)}()s.mu.RLock()defer s.mu.RUnlock()for k := range s.data {ch <- k}}()return ch
}func main() {set := NewSet()// 测试 Add 和 Containsset.Add(1)set.Add(2)set.Add(3)fmt.Println("Contains 1:", set.Contains(1)) // 输出: Contains 1: truefmt.Println("Contains 4:", set.Contains(4)) // 输出: Contains 4: false// 测试 Removeset.Remove(2)fmt.Println("Contains 2 after remove:", set.Contains(2)) // 输出: Contains 2 after remove: false// 测试 IsEmptyfmt.Println("Is set empty?", set.IsEmpty()) // 输出: Is set empty? false// 测试 Clearset.Clear()fmt.Println("Is set empty after clear?", set.IsEmpty()) // 输出: Is set empty after clear? true// 测试 Iteratorset.Add(1)set.Add(2)set.Add(3)fmt.Println("Elements in set:")for i := range set.Iterator() {fmt.Println(i)}// 其他测试代码data := make([]int, 2, 20)data[0] = -1fmt.Println("Length of data:", len(data))   // 输出: Length of data: 2fmt.Println("Capacity of data:", cap(data)) // 输出: Capacity of data: 20
}