上海产品网站建设,支付宝网站怎么设计的,免费软件如何盈利,淮南品牌型网站建设介绍
栈是存放值的一种特殊容器#xff0c;在插入与删除值时#xff0c;这种结构遵循后进先出#xff08;Last-in-first-out#xff0c;LIFO#xff09;的原则#xff0c;也就是说#xff0c;值可以任意插入栈中#xff0c;但每次取出的都是此前插入的最后一个值。
实…介绍
栈是存放值的一种特殊容器在插入与删除值时这种结构遵循后进先出Last-in-first-outLIFO的原则也就是说值可以任意插入栈中但每次取出的都是此前插入的最后一个值。
实现
栈必须支持以下方法 此外还可以定义如下的方法 此外还应该提供一个类似构造器的NewStack()方法当我们开始使用它时它会初始化一个栈。
基于数组的简单实现
为了实现栈接口我们可以用一个数组来存放其中的元素。
type T inttype Stack struct {sync.RWMutexarray []T
}构造器NewStack()方法如下
func NewStack() *Stack {stack : Stack{}stack.array []T{}return stack
}接下来我们去实现之前提到的操作方法
// Push adds t to the top of the stack
func (s *Stack) Push(t T) {s.Lock()s.array append(s.array, t)s.Unlock()
}对于Push()方法只需要将值添加到数组中Go的原生语法为我们解决了这一步骤。
// Pop removes the top element from the stack
func (s *Stack) Pop() (*T, error) {if s.IsEmpty() {return nil, fmt.Errorf(stack must not be empty)}s.Lock()item : s.array[len(s.array)-1]s.array s.array[0 : len(s.array)-1]s.Unlock()return item, nil
}Pop()方法中首先检查栈是否为空如果栈空则返回空值以及错误信息否则将数组第一位取出整个数组右移一位。
// Size returns the size of the stack
func (s *Stack) Size() int {s.RLock()defer s.RUnlock()return len(s.array)
}func (s *Stack) IsEmpty() bool {s.RLock()defer s.RUnlock()return len(s.array) 0
}至于额外的两个方法即检查栈结构体中成员变量即可。注意到栈结构体在定义时加入了锁资源因此以上所有方法都是并发安全的。
单元测试
我们对实现的方法进行单元测试
package stackimport testingvar (t1 T 1t2 T 2t3 T 3
)func TestStack_Push(t *testing.T) {stack : NewStack()stack.Push(t1)stack.Push(t2)stack.Push(t3)first : stack.array[0]last : stack.array[len(stack.array)-1]if first ! t1 || last ! t3 {t.Errorf(wrong order, expected first 1 and last 3 but got %d and %d, t1, t3)}
}func TestStack_Pop(t *testing.T) {stack : NewStack()stack.Push(t1)stack.Push(t2)stack.Push(t3)_, _ stack.Pop()if size : stack.Size(); size ! 2 {t.Errorf(wrong count, expected 2 and got %d, size)}_, _ stack.Pop()_, _ stack.Pop()if size : stack.Size(); size ! 0 {t.Errorf(wrong count, expected 0 and got %d, size)}_, err : stack.Pop()if err nil {t.Errorf(stack must not be empty)}
}func TestStack_Size(t *testing.T) {stack : NewStack()stack.Push(t1)stack.Push(t2)stack.Push(t3)if size : stack.Size(); size ! 3 {t.Errorf(wrong count, expected 3 and got %d, size)}
}func TestStack_IsEmpty(t *testing.T) {stack : NewStack()empty : stack.IsEmpty()if !empty {t.Errorf(wrong status, expected true and got %t, empty)}stack.Push(t1)empty stack.IsEmpty()if empty {t.Errorf(wrong status, expected false and got %t, empty)}
}至此单元测试通过我们就完成了栈数据结构的实现。
