Go实现List、Set、Stack、Deque等数据结构的操作方法_Golang

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 main
import (
	"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 和 get
	list.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
	}
	// 测试 remove
	err = list.remove(1)
	if err != nil {
		fmt.println("error:", err)
	} else {
		fmt.println("size after remove:", list.size()) // 输出: size after remove: 2
	}
	// 测试 getfirst 和 getlast
	first, 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 和 removefirst
	list.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
	}
	// 测试 removelast
	err = list.removelast()
	if err != nil {
		fmt.println("error:", err)
	} else {
		fmt.println("size after removelast:", list.size()) // 输出: size after removelast: 1
	}
	// 测试 clear
	list.clear()
	fmt.println("is list empty after clear?", list.isempty()) // 输出: is list empty after clear? true
}

stack

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

package main
import (
	"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 和 peek
	stack.push(1)
	stack.push(2)
	stack.push(3)
	fmt.println("top element:", stack.peek()) // 输出: top element: 3
	// 测试 pop
	fmt.println("popped element:", stack.pop())         // 输出: popped element: 3
	fmt.println("top element after pop:", stack.peek()) // 输出: top element after pop: 2
	// 测试 isempty
	fmt.println("is stack empty?", stack.isempty()) // 输出: is stack empty? false
	// 测试 search
	fmt.println("index of 2:", stack.search(2)) // 输出: index of 2: 1
	fmt.println("index of 3:", stack.search(3)) // 输出: index of 3: -1
	// 测试 clear
	stack.clear()
	fmt.println("is stack empty after clear?", stack.isempty()) // 输出: is stack empty after clear? true
}

deque

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

package main
import (
	"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 和 pushback
	deque.pushback(1)
	deque.pushfront(2)
	deque.pushback(3)
	deque.pushfront(4)
	// 测试 popfront
	fmt.println("popped from front:", deque.popfront()) // 输出: popped from front: 4
	fmt.println("popped from front:", deque.popfront()) // 输出: popped from front: 2
	// 测试 popback
	fmt.println("popped from back:", deque.popback()) // 输出: popped from back: 3
	fmt.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 和 pushback
	deque.pushfront(5)
	deque.pushback(6)
	// 测试 peekfront 和 peekback
	fmt.println("front element:", deque.popfront()) // 输出: front element: 5
	fmt.println("back element:", deque.popback())   // 输出: back element: 6
}

set

package main
import (
	"fmt"
	"sync"
)
/*
 set: 可以去除重复元素
	- add: 添加元素
	- remove: 删除元素
	- contains: 检查元素是否存在
	- isempty: 判断集合是否为空
	- clear: 清空集合
	- iterator: 返回一个迭代器通道
	...
*/
type set struct {
	mu   sync.rwmutex
	data 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 和 contains
	set.add(1)
	set.add(2)
	set.add(3)
	fmt.println("contains 1:", set.contains(1)) // 输出: contains 1: true
	fmt.println("contains 4:", set.contains(4)) // 输出: contains 4: false
	// 测试 remove
	set.remove(2)
	fmt.println("contains 2 after remove:", set.contains(2)) // 输出: contains 2 after remove: false
	// 测试 isempty
	fmt.println("is set empty?", set.isempty()) // 输出: is set empty? false
	// 测试 clear
	set.clear()
	fmt.println("is set empty after clear?", set.isempty()) // 输出: is set empty after clear? true
	// 测试 iterator
	set.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] = -1
	fmt.println("length of data:", len(data))   // 输出: length of data: 2
	fmt.println("capacity of data:", cap(data)) // 输出: capacity of data: 20
}

更多的数据结构，比如linkedlist等，大家可以自行下来尝试一下。