数据结构——Golang实现堆栈

栏目: Go · 发布时间: 5年前

内容简介:转载请注明出处栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构,它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品,先堆进来的压在底下,随后一件一件往上堆。取走时,只能从上面一件一件取。读和取都在顶部进行,底部一般是不动的。栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为进栈,删除则称为退栈。 栈也称为后进先出表。在这

转载请注明出处 数据结构——Golang实现堆栈

数据结构——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. 源码

github源码

转载请注明出处: 数据结构——Golang实现堆栈


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

注意力商人

注意力商人

吳修銘 / 黃庭敏 / 天下雜誌 / 2018-4-2 / NT$650

電子郵件,免費!照片分享,無上限! 你是否想過,隨手可得的免費內容、便利的免費服務,到底都是誰在付費? 如果商品免費,那你就不是消費者,而是商品! 你我可能都不知不覺地把自己賣給了注意力商人! 「『媒體轉型、網路演化與資訊浪潮」此一主題最具洞見的作者。』──黃哲斌(資深媒體人) 「這是少有的關注產業發展的傳播史,對現在或未來的『注意力產業』」中人來說,不可不讀。」──......一起来看看 《注意力商人》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试