Go数据结构

(1)Go实现栈和leetcode-20解答

2019-04-14  本文已影响0人  哥斯拉啊啊啊哦

栈是一种线性结构,遵循先进后出的原则

在操作上类似数组的子集

只能从一端添加元素,也只能从一端取出元素

这一端成为栈顶

应用地方:撤销操作,程序调用的系统栈,括号匹配等等


// 栈类定义和操作方法的实现

package stack

import (
    "github.com/pkg/errors"
)

type arrayStack []interface{}

func NewArrayStack() *arrayStack {
    return &arrayStack{}
}

func (i *arrayStack) Push(char interface{}) {
    *i = append(*i, char)
}

func (i *arrayStack) Pop() (interface{}, error) {
    j := *i
    l := len(j)
    c := cap(j) / 4

    if l == 0 {
        return nil, errors.New(
            "Failed to pop, stack is empty ")
    }

    // 如果长度小于容量的1/4,将容量缩短1/2
    if l <= c {
        buffer := make(arrayStack, 0, 2*c)
        for i := 0; i < l; i++ {
            buffer = append(buffer, j[i])
        }
        j = buffer
    }

    value := j[l-1]
    *i = j[:l-1]
    return value, nil
}

func (i *arrayStack) Top() (interface{}, error) {
    j := *i
    if len(j) == 0 {
        return nil, errors.New("Out of index,len is 0 ")
    }
    return j[len(j)-1], nil
}

func (i *arrayStack) Len() int {
    return len(*i)
}

func (i *arrayStack) Cap() int {
    return cap(*i)
}

func (i *arrayStack) IsEmpty() bool {
    return len(*i) == 0
}
// 做测试

func main() {
    test()
}

func test() {
    a := stack.NewArrayStack()

    for i := 0; i < 5; i++ {
        a.Push("hello world-" + strconv.Itoa(i))
    }

    fmt.Printf("isEmpty: %v, len=%v, cap=%v, pop=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Pop()))
    fmt.Printf("isEmpty: %v, len=%v, cap=%v, top=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Top()))
    fmt.Printf("isEmpty: %v, len=%v, cap=%v, pop=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Pop()))
    fmt.Printf("isEmpty: %v, len=%v, cap=%v, pop=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Pop()))
    fmt.Printf("isEmpty: %v, len=%v, cap=%v, pop=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Pop()))
    fmt.Printf("isEmpty: %v, len=%v, cap=%v, pop=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Pop()))
    fmt.Printf("isEmpty: %v, len=%v, cap=%v, pop=%v\n",
        a.IsEmpty(), a.Len(), a.Cap(), fmt.Sprintln(a.Pop()))
}
最终输出结果如下
isEmpty: false, len=5, cap=8, pop=hello world-4 <nil>
isEmpty: false, len=4, cap=8, top=hello world-3 <nil>
isEmpty: false, len=4, cap=8, pop=hello world-3 <nil>
isEmpty: false, len=3, cap=8, pop=hello world-2 <nil>
isEmpty: false, len=2, cap=8, pop=hello world-1 <nil>
isEmpty: false, len=1, cap=4, pop=hello world-0 <nil>
isEmpty: true, len=0, cap=2, pop=<nil> Failed to pop, stack is empty 
例题:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1:        示例 2:            示例 3:          示例 4:         示例 5:
输入: "()"     输入 "()[]{}"     输入: "(]"        输入: "([)]"    输入: "{[]}"
输出: true     输出: true        输出: false       输出: false     输出: true
// 解题思路:遍历字符串,将左括号放放入栈中,如果是右括号,就将栈顶括号取出来,看能否闭合,
无法闭合就返回false,能闭合并且最终栈为空就返回true

func isMatch(str string) bool {
    a := stack.NewArrayStack()

    for _, k := range str {
        v := string(k)
        switch v {
        case "(":
            a.Push(v)
        case "[":
            a.Push(v)
        case "{":
            a.Push(v)
        case ")":
            top, err := a.Pop()
            if err != nil || top != "(" {
                return false
            }
        case "]":
            top, err := a.Pop()
            if err != nil || top != "[" {
                return false
            }
        case "}":
            top, err := a.Pop()
            if err != nil || top != "{" {
                return false
            }
        }
    }
    if a.Len() != 0 {
        return false
    }
    return true
}
// 测试
func main() {
    var (
        str1 = "({}{}())" //1
        str2 = "({{)}}()" //2
        str3 = "(}"       //2
        str4 = "({})"     //1
        str5 = "(({})"    //2
    )

    fmt.Println(isMatch(str1))
    fmt.Println(isMatch(str2))
    fmt.Println(isMatch(str3))
    fmt.Println(isMatch(str4))
    fmt.Println(isMatch(str5))
}
// 测试结果
true
false
false
true
false

有bug欢迎指出,转载请注明出处。

上一篇下一篇

猜你喜欢

热点阅读