转载请注明出处数据结构——Golang实现堆栈
Golang
1. 栈（stack）
栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。读和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈，删除则称为退栈。 栈也称为后进先出表。
2. Golang 实现
2.1. 相关结构体
在这里，我把栈拆分为两个部分，容器和链表，容器用结构体实现，链表用单链表，当然大家也可以用其他链表结构，甚至数组来实现。
这里的例子，也是使用单链表实现的。
// 栈信息
type Stack struct {
list *SingleList
}
2.2. 栈初始化
对stack 进行简单的初始化，也即是对于单链表的初始化
// Init 初始化栈
func (s *Stack) Init() {
s.list = new(SingleList)
s.list.Init()
}
2.3. 压入栈（push)
往栈内插入数据，称为push，在这里对于栈的压入压出都是对链表的表头处理，当然也可以对表尾处理，道理都是一样的
// Push 压入栈
func (s *Stack)Push(data interface{}) bool {
node := &SingleNode{
Data: data,
}
return s.list.Insert(0, node)
}
2.4. 压出栈(pop)
取出栈顶数据，称为pop。
// Pop 压出栈
func (s *Stack)Pop() interface{}{
node := s.list.Get(0)
if node != nil {
s.list.Delete(0)
return node.Data
}
return nil
}
2.5. 查看栈顶数据(peek)
只查看栈顶元素，并不取出
// Peek 查看栈顶元素
func (s *Stack)Peek() interface{}{
node := s.list.Get(0)
if node != nil {
return node.Data
}
return nil
}
2.6. 栈长度(size)
查询栈当前元素数量
// Size 获取栈的长度
func (s *Stack)Size()uint{
return s.list.Size
}
3. 单元测试
package dstr
import(
"testing"
)
func TestStack_Init(t *testing.T) {
stack := new(Stack)
stack.Init()
t.Log("stack init success")
}
func TestStack_Push(t *testing.T){
stack := new(Stack)
stack.Init()
b := stack.Push(1)
if !b {
t.Error("stack push failed")
return
}
t.Log("stack push success")
data := stack.Peek()
var (
ok bool
num int
)
if num, ok = data.(int); ok && num == 1{
t.Log("stack push and peek success")
return
}
t.Error("stack push success but peek failed")
}
func TestStack_Pop(t *testing.T){
stack := new(Stack)
stack.Init()
d1 := stack.Pop()
if d1 != nil{
t.Error("empty stack pop error")
return
}
t.Log("empty stack pop success")
stack.Push(1)
stack.Push(2)
stack.Push(3)
d2 := stack.Pop()
var (
ok bool
num int
)
if num, ok = d2.(int); ok && num == 3 && stack.Size() == 2{
t.Log("stack pop success")
return
}
t.Error("stack pop failed")
}
func TestStack_Peek(t *testing.T){
stack := new(Stack)
stack.Init()
d := stack.Peek()
if d == nil {
t.Log("empty stack peek success")
return
}
t.Error("empty stack peek fail")
}
4. 源码
完
转载请注明出处: 数据结构——Golang实现堆栈
