（1）Go实现栈和leetcode-20解答

栈是一种线性结构遵循先进后出的原则在操作上类似数组的子集只能从一端添加元素也只能从一端取出元素这一端成为栈顶应用地方撤销操作程序调用的系统栈括号匹配等等// 栈类定义和操作方法的实现packagestackimport(github.com/pkg/errors)typearrayStack[]interface{}funcNewArrayStack()*arrayStack{returnarrayStack{}}func(i*arrayStack)Push(charinterface{}){*iappend(*i,char)}func(i*arrayStack)Pop()(interface{},error){j:*i l:len(j)c:cap(j)/4ifl0{returnnil,errors.New(Failed to pop, stack is empty )}// 如果长度小于容量的1/4将容量缩短1/2iflc{buffer:make(arrayStack,0,2*c)fori:0;il;i{bufferappend(buffer,j[i])}jbuffer}value:j[l-1]*ij[:l-1]returnvalue,nil}func(i*arrayStack)Top()(interface{},error){j:*iiflen(j)0{returnnil,errors.New(Out of index,len is 0 )}returnj[len(j)-1],nil}func(i*arrayStack)Len()int{returnlen(*i)}func(i*arrayStack)Cap()int{returncap(*i)}func(i*arrayStack)IsEmpty()bool{returnlen(*i)0}// 做测试funcmain(){test()}functest(){a:stack.NewArrayStack()fori:0;i5;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,len5,cap8,pophello world-4nilisEmpty:false,len4,cap8,tophello world-3nilisEmpty:false,len4,cap8,pophello world-3nilisEmpty:false,len3,cap8,pophello world-2nilisEmpty:false,len2,cap8,pophello world-1nilisEmpty:false,len1,cap4,pophello world-0nilisEmpty:true,len0,cap2,popnilFailed to pop,stack is empty例题 给定一个只包括(){}[]的字符串判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 示例1:示例2:示例3:示例4:示例5:输入:()输入()[]{}输入:(]输入:([)]输入:{[]}输出:true输出:true输出:false输出:false输出:true// 解题思路遍历字符串将左括号放放入栈中如果是右括号就将栈顶括号取出来看能否闭合无法闭合就返回false能闭合并且最终栈为空就返回truefuncisMatch(strstring)bool{a:stack.NewArrayStack()for_,k:rangestr{v:string(k)switchv{case(:a.Push(v)case[:a.Push(v)case{:a.Push(v)case):top,err:a.Pop()iferr!nil||top!({returnfalse}case]:top,err:a.Pop()iferr!nil||top![{returnfalse}case}:top,err:a.Pop()iferr!nil||top!{{returnfalse}}}ifa.Len()!0{returnfalse}returntrue}// 测试funcmain(){var(str1({}{}())//truestr2({{)}}()//falsestr3(}//falsestr4({})//truestr5(({})//false)fmt.Println(isMatch(str1))fmt.Println(isMatch(str2))fmt.Println(isMatch(str3))fmt.Println(isMatch(str4))fmt.Println(isMatch(str5))}// 测试结果truefalsefalsetruefalse