内容简介:转载请注明出处栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品,先堆进来的压在底下,随后一件一件往上堆。取走时,只能从上面一件一件取。读和取都在顶部进行,底部一般是不动的。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为进栈,删除则称为退栈。 栈也称为后进先出表。在这
转载请注明出处 数据结构——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实现堆栈
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。