本文共 2948 字,大约阅读时间需要 9 分钟。
数据结构堆栈 内存堆栈
A stack is an ordered collection of items following the Last-In-First-Out (LIFO) principle. We add and remove items from the same part of the pile, called the top. We cannot remove items from the base. Just like a pile of books.
堆栈是遵循后进先出(LIFO)原则的项目的有序集合。 我们从堆的同一部分(称为顶部)添加和删除项目。 我们无法从基础中删除项目。 就像一堆书。
Stacks have tons of uses, from creating a history of pages visited to commands entered and to store actions that can be undone.
从创建访问页面的历史记录到输入的命令以及存储可以撤消的操作,堆栈都有许多用途。
Internally the stack will be represented with a slice
type, and I’ll expose the
在内部,堆栈将以slice
类型表示,我将公开
Push()
Push()
Pull()
Pull()
New()
New()
methods.
方法。
New()
serves as the constructor, which initializes the internal slice when we start using it.
New()
用作构造函数,当我们开始使用它时会初始化内部切片。
I’ll create an ItemStack
generic type, concurrency safe, that can generate stacks containing any type by using genny
, to create a type-specific stack implementation, encapsulating the actual value-specific data structure containing the data.
我将创建一个ItemStack
泛型类型,并发安全的,可以生成包含任何类型的使用堆栈genny
,创建一个特定类型的堆栈实现,封装包含数据的实际值特定的数据结构。
// Package stack creates a ItemStack data structure for the Item typepackage stackimport ( "sync" "github.com/cheekybits/genny/generic")// Item the type of the stacktype Item generic.Type// ItemStack the stack of Itemstype ItemStack struct { items []Item lock sync.RWMutex}// New creates a new ItemStackfunc (s *ItemStack) New() *ItemStack { s.items = []Item{} return s}// Push adds an Item to the top of the stackfunc (s *ItemStack) Push(t Item) { s.lock.Lock() s.items = append(s.items, t) s.lock.Unlock()}// Pop removes an Item from the top of the stackfunc (s *ItemStack) Pop() *Item { s.lock.Lock() item := s.items[len(s.items)-1] s.items = s.items[0 : len(s.items)-1] s.lock.Unlock() return &item}
The tests describe the usage of the above implementation.
这些测试描述了上述实现的用法。
package stackimport ( "testing")var s ItemStackfunc initStack() *ItemStack { if s.items == nil { s = ItemStack{} s.New() } return &s}func TestPush(t *testing.T) { s := initStack() s.Push(1) s.Push(2) s.Push(3) if size := len(s.items); size != 3 { t.Errorf("wrong count, expected 3 and got %d", size) }}func TestPop(t *testing.T) { s.Pop() if size := len(s.items); size != 2 { t.Errorf("wrong count, expected 2 and got %d", size) } s.Pop() s.Pop() if size := len(s.items); size != 0 { t.Errorf("wrong count, expected 0 and got %d", size) }}
You can use this generic implemenation to generate type-specific stacks, using
您可以使用以下通用实现来生成特定于类型的堆栈,方法是:
//generate a `IntStack` stack of `int` valuesgenny -in stack.go -out stack-int.go gen "Item=int"//generate a `StringStack` stack of `string` valuesgenny -in stack.go -out stack-string.go gen "Item=string"
翻译自:
数据结构堆栈 内存堆栈
转载地址:http://xaqgb.baihongyu.com/