type stack struct{
    top int  // 指向栈顶元素的下一个位置
    base int // 始终指向栈底
    container []int //使用切片可以动态扩容
    length int // 记录当前栈内的元素个数
    size int // 记录当前栈的最大容量
}

2.1.2 顺序栈的初始化

func initStack(size int)*stack{
    return &stack{
        top:0,
        base:0,
        container:make([]int,size,size), //这里有两种方式，一种是定义长度为0，入栈时用append()函数追加,但是在弹栈时要相应抹去底层数组的值，比较麻烦，一种是定义长度为size，入栈时直接索引赋值
        length:0,
        size:size,
    }
}

2.1.3 判断栈空与栈满

func (s *stack)isValid()bool{
    return s.length==0
}

func (s *stack)isFull()bool{
    return s.length==s.size
}

2.1.4 入栈

func (s *stack)push(data int)error{
    if s.isFull(){
        return errors.New("the stack is full,can not push any value\n")
    }
    s.container[s.top]=data //往表尾(既栈顶)追加元素
    s.top++ // 保持top指向栈顶元素的下一个位置
    s.length++ 
    return nil
}

2.1.5 出栈

func (s *stack)pop()(int,error){
    if s.isValid(){
        return -1,errors.New("the stack is valid,can not pop any value\n")
    }
    s.top--  // 先将top指向当前栈顶元素
    s.length-- 
    return s.container[s.top],nil
}

2.1.6 预览栈顶元素

func (s *stack)peek()string{
    return s.container[top-1]
}

2.2 链栈

2.2.1 链栈的结构定义

type sNode struct{
    data int
    next *sNode
}

func newSNode(data int)*sNode{
    return &sNode{
        data:data,
        next:nil,
    }
}

type lStack struct{
    top *sNode //top指针指向链表头节点，不存放数据，头节点始终指向栈顶元素
    length int
}

2.2.2 链栈的初始化

// 链栈的初始化
func initLStack()*lStack{
    return &lStack{
        top:newSNode(-1),
        length:0,
    }
}

2.1.3 判断栈空

// 判断链栈是否为空
func (ls *lStack)isValid()bool{
    return ls.length==0
}

2.2.4 入栈(此处使用的是链表的头插法)

思路
代码实现如下?

// 链栈入栈
func (ls *lStack)push(data int){
    temp := newSNode(data)
    temp.next =ls.top.next
    ls.top.next=temp
    ls.length++
}

2.2.5?出栈

思路
?代码实现如下

// 链栈出栈
func (ls *lStack)pop()(int,error){
    if ls.isValid(){
        return -1,errors.New("the stack is valid,can not pop any value\n")
    }
    result := ls.top.next
    ls.top.next = result.next
    result.next = nil
    ls.length--
    return result.data,nil
    
}

三、练习

3.1 进制转换，设计一个函数，要求输入一个10进制数，可以输出转换成对应进制的数。

思路

?代码实现如下

const(
    Binary = 2
    Octcal = 8
    Hex = 16
)


// 本函数默认输入的data范围是[0,255]，且不考虑16进制大于9时转换成A.B,C,D,E
func trans(data int,convert int)[]int{
    s := initStack(8)
    result := make([]int,0,8)
    remainder := data % convert // 求余数
    for data != 0{ // 最终data会除到0
        s.push(remainder) // 将余数入栈
        data = data /  convert // 更新data
        remainder = data % convert
    }
    
    length := s.length
    for i:=0 ; i < length ; i++{
        result = append(result,s.pop())
    }
    return result
}

3.2 括号匹配，输入任意数量只含括号的字符串，函数能判断字符串中括号的数量及类型是否匹配

思路
- 遇到左括号"(","[","{"入栈
- 遇到右括号则弹栈，同时进行符号匹配，如果不匹配则返回false，如果栈空了，说明右括号多了
- 当扫描完字符串后，判断栈是否非空，如果非空，说明栈中还有左括号，既左括号多了

代码实现如下

func match(str string)bool{
    s := initStack(len(str)) // 初始化一个栈
    for _,v := range str{ 
        switch string(v){ // for range的每个v都是一个rune类型，要转换成字符串才能比较
            case "(","[","{":
                s.push(string(v))    // 遇到左括号则入栈
            case ")":      
                temp,err := s.pop()  // 遇到右括号则开始匹配，如果不匹配或者栈空了(栈空pop()会返回错误)则返回fasle
                if err != nil || temp != "("{
                    return false
                }
            case "]":
                temp,err := s.pop()
                if err != nil || temp != "["{
                    return false
                }
            case "}":
                temp,err := s.pop()
                if err != nil || temp != "{"{
                    return false
                }
            default:
                return false
                
        }
    }
    
    if !s.isValid(){  //如果字符串扫描完毕栈非空，说明左括号多余
        return false
    }
    
    return true
    
}

func main(){
    str1 := "(()"
    str2 := "())"
    str3 := "{[()]}"
    
    fmt.Println(match(str1))  //输出false
    fmt.Println(match(str2))  //输出false
    fmt.Println(match(str3))  //输出true
}

3.3 逆波兰表达式，要求输入中缀表达式，输出后缀表达式

思路：扫描到数字直接输出，扫描到运算符：
- 优先级比栈顶运算符高级，直接入栈
- 优先级比栈顶运算符低级，弹出栈顶运算符并输出，直到栈顶运算符优先级比当前扫描的运算符低级，然后入栈当前扫描的运算符
- 遇到"("时无条件入栈，直到遇到")"时，将两个括号之间所有运算符全部弹栈并输出
- 扫描完字符串后，弹出栈中剩余的元素
代码实现如下

func postFix(str string)[]string{
    s := initStack(len(str)) // 初始化一个栈
    result := make([]string,0,len(str)) // 初始化一个切片用于装结果
    
    for _,v := range str{
        switch string(v){
            case "1","2","3","4","5","6","7","8","9":
                result = append(result,string(v)) // 遇到数字直接追加到结果
               case "*","/": // 遇到"*","/"，弹出栈顶的"*","/"
                temp := s.peek()
                for temp=="*"||temp=="/"{
                    result = append(result,string(temp))
                    s.pop()
                    temp = s.peek()
                }
                s.push(string(v))
            case "+","-": //遇到"+","-"，优先级最低，把栈中所有符号全部弹出
                temp := s.peek()
                for temp=="*"||temp=="/"||temp=="+"||temp=="-"{
                    result = append(result,string(temp))
                    s.pop()
                    temp = s.peek()
                }
            case "(":
                s.push(string(v))
            case ")": //遇到右括号，弹出左右括号间包含的所有括号
                temp := s.peek()
                for temp != "("{
                    result = append(result,string(temp))
                    s.pop()
                    temp = s.peek()
            
                }
                s.pop() //弹出左括号
            default:
                break      
        }
        
    }
    
    // 弹出栈中剩余符号
    length := s.length
    for i:=0;i<length;i++{
        v ,_:= s.pop()
        result = append(result,v)
    }
    
    return result
}

func main() {
    str := "1+2*(4-3*7/2)-5/6"
    result := postFix(str)
    fmt.Println(result) // 输出:[1 2 4 3 7 * 2 / - * + 5 6 / -]
}