Golang 中栈、队列的实现及常用操作,数据结构系列原文:flaviocopes.com,翻译已获作者授权。
栈
概述
栈是数据按照后进先出 LIFO(Last-In-First-Out) 原则组成的集合。添加和移除元素都是在栈顶进行,类比书堆,不能在栈底增删元素。
栈的应用很广泛,比如网页跳转后一层层返回,ctrl+z 撤销操作等。
使用 slice
动态类型来实现栈,栈元素的类型是使用 genny 创建的通用类型 ItemStack
,实现以下常用操作:
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| package stack
import ( "github.com/cheekybits/genny/generic" "sync" )
type Item generic.Type
type ItemStack struct { items []Item lock sync.RWMutex }
func (s *ItemStack) New() *ItemStack { s.items = []Item{} return s }
func (s *ItemStack) Push(t Item) { s.lock.Lock() s.items = append(s.items, t) s.lock.Unlock() }
func (s *ItemStack) Pop() *Item { s.lock.Lock() item := s.items[len(s.items)-1] s.items = s.items[:len(s.items)-1 ] s.lock.Unlock() return &item }
|
测试用例:stack_test.go
队列
概述
队列是数据按照先进先出 FIFO(First-In-First-Out) 原则组成的集合,类比排队,在队列任一端添加元素,从对应的另一端删除元素。
使用 slice
动态类型来实现队列,元素的类型为通用类型 ItemQueue
,实现以下常用操作:
1 2 3 4 5 6
| New() Enqueue() Dequeue() Front() IsEmpty() Size()
|
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| package queue
import ( "github.com/cheekybits/genny/generic" "sync" )
type Item generic.Type
type ItemQueue struct { items []Item lock sync.RWMutex }
func (q *ItemQueue) New() *ItemQueue { q.items = []Item{} return q }
func (q *ItemQueue) Enqueue(t Item) { q.lock.Lock() q.items = append(q.items, t) q.lock.Unlock() }
func (q *ItemQueue) Dequeue() *Item { q.lock.Lock() item := q.items[0] q.items = q.items[1:len(q.items)] q.lock.Unlock() return &item }
func (q *ItemQueue) Front() *Item { q.lock.Lock() item := q.items[0] q.lock.Unlock() return &item }
func (q *ItemQueue) IsEmpty() bool { return len(q.items) == 0 }
func (q *ItemQueue) Size() int { return len(q.items) }
|
测试用例:queue_test.go