数据结构与算法基础-Go语言版-2.栈

本文主要是介绍数据结构与算法基础-Go语言版-2.栈，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

一、栈的定义及特点？

二、栈的实现

2.1 顺序栈

2.1.1 顺序栈的结构定义

2.1.2 顺序栈的初始化

2.1.3 判断栈空与栈满

2.1.4 入栈

2.1.5 出栈

2.1.6 预览栈顶元素

2.2 链栈

2.2.1 链栈的结构定义

2.2.2 链栈的初始化

2.1.3 判断栈空

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

2.2.5 出栈

三、练习

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

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

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

总结

前言

本文将会系统介绍栈的结构及其特点，同时给出go语言如何实现顺序结构和链式结构的栈，最后使用顺序栈来完成几道习题。

一、栈的定义及特点？

栈的定义：栈是限定仅在表尾进行插入和删除操作的线性表
栈的特点：先进后出，后进先出

二、栈的实现

2.1 顺序栈

2.1.1 顺序栈的结构定义

栈的容器结构设计如下

代码实现

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 / -]
}

总结

以上就是使用go语言构建栈并进行一些相关应用的介绍。如果有错希望大家能够纠正。

生命不息，coding不止！

这篇关于数据结构与算法基础-Go语言版-2.栈的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Go教程

数据结构与算法基础-Go语言版-2.栈

前言

一、栈的定义及特点？

二、栈的实现

2.1 顺序栈

2.1.1 顺序栈的结构定义

2.1.2 顺序栈的初始化

2.1.3 判断栈空与栈满

2.1.4 入栈

2.1.5 出栈

2.1.6 预览栈顶元素

2.2 链栈

2.2.1 链栈的结构定义

2.2.2 链栈的初始化

2.1.3 判断栈空

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

2.2.5 出栈

三、练习

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

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

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

总结

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯