Go實現(xiàn)List、Set、Stack、Deque等數(shù)據(jù)結(jié)構(gòu)的操作方法

更新時間：2024年12月05日 10:44:52 作者：NPE~

Go語言團隊的一個核心目標(biāo)是保持語言的簡單性,他們認(rèn)為,如果一個功能可以用簡單的組合來實現(xiàn),那就沒有必要把它放進標(biāo)準(zhǔn)庫里,本文給大家介紹Go實現(xiàn)List、Set、Stack、Deque等數(shù)據(jù)結(jié)構(gòu)的操作方法,感興趣的朋友跟隨小編一起看看吧

Go實現(xiàn)List、Set、Stack、Deque等數(shù)據(jù)結(jié)構(gòu)

完整代碼地址（歡迎大家??）：https://github.com/ziyifast/ziyifast-code_instruction/tree/main/go-demo/go-data-structure
大家有接觸過除Go其他語言（如：Java）可能就會想為什么Go沒有像deque、stack、set、list這些常見的數(shù)據(jù)容器。尤其是對于那些習(xí)慣了用這些容器解決LeetCode問題的同學(xué)來說，就更為不便。

1 為什么Go原生不提供這些容器：為了簡潔

Go語言自誕生以來就有著非常明確的目標(biāo)，那就是簡潔、高效、并發(fā)。為了實現(xiàn)這些目標(biāo)，Go在設(shè)計上做了很多取舍。

簡單性：Go語言團隊的一個核心目標(biāo)是保持語言的簡單性。他們認(rèn)為，如果一個功能可以用簡單的組合來實現(xiàn)，那就沒有必要把它放進標(biāo)準(zhǔn)庫里。
deque、stack、set、list這些數(shù)據(jù)結(jié)構(gòu)雖然常用，但它們并不是編寫高效、可維護代碼的唯一途徑。通過組合切片和映射，開發(fā)者可以實現(xiàn)絕大多數(shù)需要的數(shù)據(jù)結(jié)構(gòu)。
鼓勵最佳實踐：Go語言推崇一種“最小驚奇”的設(shè)計原則。也就是說，代碼應(yīng)該盡可能地容易理解和預(yù)測。標(biāo)準(zhǔn)庫的設(shè)計哲學(xué)之一就是提供最少但足夠的工具，讓開發(fā)者能夠按照最佳實踐來編寫代碼。
這個哲學(xué)避免了標(biāo)準(zhǔn)庫的膨脹，同時確保了代碼的清晰性和可維護性。
社區(qū)的力量：Go語言的生態(tài)系統(tǒng)非常活躍，有很多高質(zhì)量的第三方庫可以提供你需要的高級數(shù)據(jù)結(jié)構(gòu)。如果標(biāo)準(zhǔn)庫包含了所有可能需要的數(shù)據(jù)結(jié)構(gòu)，那它將變得非常龐大且難以維護。

相反，通過社區(qū)貢獻，Go可以保持核心的簡潔，同時又不失靈活性。

2 實現(xiàn)

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

雖然Go語言沒有內(nèi)置這些高級數(shù)據(jù)結(jié)構(gòu)，但通過組合使用切片和映射，我們依然可以實現(xiàn)幾乎所有需要的數(shù)據(jù)結(jié)構(gòu)。

而且，這種方式更符合Go語言簡潔、高效的設(shè)計哲學(xué)。
最重要的是，這也讓我們更加理解這些數(shù)據(jù)結(jié)構(gòu)的內(nèi)部實現(xiàn)，而不僅僅是簡單地調(diào)用現(xiàn)成的API。

所以，下次再遇到類似的問題，大家也可以自己試試看實現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)，既能提升編碼能力，又能更深入地理解Go語言的設(shè)計理念。

List

思路：對于列表來說，通常需要有Add、Remove等操作，其實golang原生的切片就很接近切片，因此我們簡單做封裝即可

package main
import (
	"errors"
	"fmt"
)
/*
	List:
		- NewList(): 創(chuàng)建一個新的列表
		- Add(element): 在列表末尾添加元素
		- Remove(index): 根據(jù)索引移除元素
		- Size(): 返回列表的大小
		- Get(index): 根據(jù)索引獲取元素
		- IsEmpty(): 判斷列表是否為空
		- Clear(): 清空列表
		- GetFirst(): 獲取第一個元素
		- GetLast(): 獲取最后一個元素
		- RemoveLast(): 移除最后一個元素
		- AddFirst(element): 在列表開頭添加元素
		- RemoveFirst(): 移除第一個元素
		...
*/
type List struct {
	data []interface{}
}
// NewList 創(chuàng)建一個新的列表
func NewList() *List {
	return &List{
		data: []interface{}{},
	}
}
// Add 在列表末尾添加元素
func (l *List) Add(v interface{}) {
	l.data = append(l.data, v)
}
// Remove 根據(jù)索引移除元素
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 根據(jù)索引獲取元素
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 雙端隊列結(jié)構(gòu)體
type Deque struct {
	data *list.List
}
// NewDeque 創(chuàng)建一個新的雙端隊列
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: 可以去除重復(fù)元素
	- Add: 添加元素
	- Remove: 刪除元素
	- Contains: 檢查元素是否存在
	- IsEmpty: 判斷集合是否為空
	- Clear: 清空集合
	- Iterator: 返回一個迭代器通道
	...
*/
type Set struct {
	mu   sync.RWMutex
	data map[interface{}]bool
}
// NewSet 創(chuàng)建一個新的集合
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
}

更多的數(shù)據(jù)結(jié)構(gòu)，比如LinkedList等，大家可以自行下來嘗試一下。

3 代碼地址

完整代碼地址（歡迎大家??）：https://github.com/ziyifast/ziyifast-code_instruction/tree/main/go-demo/go-data-structure

到此這篇關(guān)于Go實現(xiàn)List、Set、Stack、Deque等數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Go List、Set、Stack、Deque數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: