美文网首页Go程序员Golang开发指南
Golang基础篇之数据结构-栈

Golang基础篇之数据结构-栈

作者: 码码码码 | 来源:发表于2017-07-26 00:29 被阅读265次

    本篇通过实现一个自定义的栈,来学习Go语言的自定义类型及其方法
    首先栈的概念不用多说,它是一种支持从顶端插入或删除的线性表,废话少说上代码。
    GOPATH下新建stack目录,栈的所有实现在stack.go文件之中。
    首先需要一个能够保存数据的结构体

    type Stack []interfice {}
    

    这里声明Stack为空接口类型的切片(Go语言之中的切片可以理解为一个长度可变的数组)。由于Go语言所有类型都实现了空接口,因此任意类型的值都可以存储在Stack之中。
    接下来,由于Stack的底层数据类型是一个切片,我们可以为其实现Len()Cap()方法用来获取其长度和容量(Go语言之中首字母大写的方法为包外可访问的,类似于Java或者C++之中类的public方法)。

    func (stack Stack) Len() int {
        return len(stack)
    }
    

    方法的定义如上。func关键字用来定义方法,其后紧跟的是方法所作用的类型,这里这个Len()方法作用于Stack这个类型的值,该值通常被称为该方法的“接受器”(Go语言的类型声明,变量声明都将类型放在名称之后);然后是方法名以及参数列表,这里参数为空;最后面是方法的返回值,这里为int。方法的实现调用了Go语言的内建函数len()len()返回切片和数组的长度。
    Cap()方法与Len()类似,其实现也调用了内建函数cap()来获取切片的长度

    func (stack Stack) Cap() int {
        return cap(stack)
    }
    

    接下来实现其关键方法Push()Top()Pop()

    func (stack *Stack) Push(value interface{})  {
        *stack = append(*stack, value)
    }
    

    Push()方法的接收器为一个Stack类型的指针(Go指针的写法与C/C++类似,类型前面加上*号)。Go语言的所有方法参数都是值传递,接收器实际也是作为方法的一个参数传递进入方法的。如果传递一切片或者数组进方法,实际是将切片或数组的值拷贝了一份传入了方法之中,此时在方法之中对该切片或数组做的操作都不会影响方法之外的原始值。如果想要方法之中的操作影响到方法外的原始值,则应该使用指针作为参数,对指针的操作会直接反应到内存之中的原始值上去。在这里我们希望更改原始值(往原始的stack之中添加数据), 所以接收器是一个指针。方法的参数是一个interface{}类型的值,也就是说该方法可以接受任意类型作为参数。方法的实现使用了内建函数append(),往切片对尾部中添加新值。

    func (stack Stack) Top() (interface{}, error)  {
        if len(stack) == 0 {
            return nil, errors.New("Out of index, len is 0")
        }
        return stack[len(stack) - 1], nil
    }
    

    Top()方法返回一个任意类型的值以及一个error(是的没错,Go语言的方法可以返回多个值)。当stack为空时,返回一个空值和一个error类型的值(这里使用errors包的New()函数创建)。当stack不为空时,返回底层切片的最后一个值和一个空的error

    func (stack *Stack) Pop() (interface{}, error)  {
        theStack := *stack
        if len(theStack) == 0 {
            return nil, errors.New("Out of index, len is 0")
        }
        value := theStack[len(theStack) - 1]
        *stack = theStack[:len(theStack) - 1]
        return value, nil
    }
    

    Pop()方法的接收器同样是一个Stack的指针。其中theStack[:len(theStack) - 1]这种写法,是Go中取子切片的方法,:两边是起始index和结束index。起始index为0时可以省略。结束的index也可以省略,省略时结束index为切片的len()值。
    此外还有一个简单的IsEmpty()方法

    func (stack Stack) IsEmpty() bool  {
        return len(stack) == 0
    }
    

    以上所有方法实现完毕,写一个stack_test.go来测试stack.go,在包目录下运行go test即可查看结果。测试通过即可使用go install命令将该stack包安装到GOPATH之中,然后就可以在其他项目引用自己实现的Stack
    完整源码比较短,直接贴在这里
    stack.go

    package stack
    
    import "errors"
    
    type Stack []interface {}
    
    func (stack Stack) Len() int {
        return len(stack)
    }
    
    func (stack Stack) IsEmpty() bool  {
        return len(stack) == 0
    }
    
    func (stack Stack) Cap() int {
        return cap(stack)
    }
    
    func (stack *Stack) Push(value interface{})  {
        *stack = append(*stack, value)
    }
    
    func (stack Stack) Top() (interface{}, error)  {
        if len(stack) == 0 {
            return nil, errors.New("Out of index, len is 0")
        }
        return stack[len(stack) - 1], nil
    }
    
    func (stack *Stack) Pop() (interface{}, error)  {
        theStack := *stack
        if len(theStack) == 0 {
            return nil, errors.New("Out of index, len is 0")
        }
        value := theStack[len(theStack) - 1]
        *stack = theStack[:len(theStack) - 1]
        return value, nil
    }
    

    stack_test.go

    package stack
    
    import (
        "testing"
    )
    
    func TestStack_Len(t *testing.T) {
        var myStack Stack
        myStack.Push(1)
        myStack.Push("test")
        if myStack.Len() == 2 {
            t.Log("Pass Stack.Len")
        } else {
            t.Error("Failed Stack.Len")
        }
    }
    
    func TestStack_IsEmpty(t *testing.T) {
        var mStack Stack
        if mStack.IsEmpty() {
            t.Log("Pass Stack.IsEmpty")
        } else {
            t.Error("Failed Stack.IsEmpty")
        }
    }
    
    func TestStack_Cap(t *testing.T) {
        myStack := make(Stack, 3)
        if myStack.Cap() == 3 {
            t.Log("Pass Stack.Cap")
        } else {
            t.Error("Failed Stack.Cap")
        }
    }
    
    func TestStack_Push(t *testing.T) {
        var mStack Stack
        mStack.Push(3)
        if mStack.Len() == 1 {
            t.Log("Pass Stack.Push")
        } else {
            t.Error("Failed Stack.Push")
        }
    }
    
    func TestStack_Top(t *testing.T) {
        var mStack Stack
        if _, err := mStack.Top(); err == nil {
            t.Error("Failed Stack.Top")
        }
        mStack.Push(3)
        if value, _ := mStack.Top(); value == 3 {
            t.Log("Pass Stack.Top")
        } else {
            t.Errorf("Failed Stack.Top, value is %d", value)
        }
    }
    
    func TestStack_Pop(t *testing.T) {
        var mStack Stack
        if _, err := mStack.Pop(); err == nil {
            t.Error("Failed Stack.Top")
        }
        mStack.Push("test")
        mStack.Push(3)
        if value, _ := mStack.Pop(); value == 3 && mStack.Len() == 1 {
            t.Log("Pass Stack.Pop")
        } else {
            t.Errorf("Failed Stack.Pop, value is %d, len is %d", value, mStack.Len())
        }
    }
    
    附注

    相关文章

      网友评论

      本文标题:Golang基础篇之数据结构-栈

      本文链接:https://www.haomeiwen.com/subject/rtwgkxtx.html