分享 数据结构之 stack/ 栈

early · 2018年10月17日 · 3053 次阅读

数据结构第二篇,本文简单介绍一下,一个在计算机科学界如雷贯耳且堪称中流砥柱,但是在搬砖过程中几乎用不到的数据结构:栈。

什么是栈

栈在计算机领域名声非常大,大家都知道它是一种后进先出、先进后出的数据结构。有些资料上将其称为功能受限的线性表,只能在尾部进行插入或弹出操作,不能像数组那样随机访问,不能简单遍历。这确实是一种很贴切的说法。 弹夹就是一个栈

子弹只能从头部一个个装进来,也只能在头部被一颗颗打出去。核心实现样例如下:

type Stack []interface{}

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

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

当初刚学习栈的时候,觉得这玩意太简单,疑惑它到底有什么用。随着阳光一点点地晒进了井底,我才慢慢理解,数据结构本质上表达的是数据的组织方式,而组织方式本身蕴含着无穷的智慧。接下来,就通过简单的例子,来一窥栈的神奇。

栈的应用

二叉树遍历

简单的二叉树递归中序遍历,如下:

func Traval(parent TreeNode){
    if parent == nil{
        return 
    }
    Traval(parent.left)
    fmt.Println(parent.val)
    Traval(parent.right)
}

但如果不用递归,怎么实现遍历呢?这时候就可以用栈来追踪父节点:

func (tree *Tree) TraverseN(node TreeNode){ 
    var stack Stack 
    for node != nil or len(stack) != 0{
        for (node != nil){   //往左一直走到底
            stack.Push(node) //保存父节点
            node = node.left 
        }
        node,e := stack.Pop() //往回走
        fmt.Println(node.val)
        node = node.right // 往右边走
    }
}

语法检查

hash[get(find()[0][user(){find([touch()]{create()})])]

检查上面的表达式中符号有没有正常闭合。记得以前刚看到这种题目时,那是十分的迷茫,完全不知道怎么下手。神奇的栈可以很巧妙地搞定它,按照下面的算法:

从第一个字符开始扫描,
遇到普通字符直接忽略,
遇到左括号时压入栈中,
遇到右括号时从栈中弹出栈顶元素,进行左右匹配,
     - 匹配成功则继续下一个,
     - 匹配失败则报错终止。
结束时:
      成功: 所有字符扫描完毕,栈为空
      失败: 匹配失败,或者扫描完毕后栈不为空

实现如下:

func check(str *string) bool{
    var stack Stack
    strPair := map[string]string{"(":")", "{":"}","[":"]"}
    var leftStr string = "([{"
    var rightStr string = ")]}"
    for i := 0; i<len(*str);i++{
        current := string((*str)[i])
        if strings.Contains(leftStr, current){
            stack.Push(current)
            continue
        }
        if strings.Contains(rightStr, current){
            current_top, _ := stack.Pop()
            if strPair[current_top.(string)] != string(current){
                return false
            }
        }
    }
    return len(stack) == 0
}

var str1 string = "hash[get(find()[0][user(){find([touch()]{create()})])]"
var str string = "{(({}){[]}[()])}"
ret1 := check(&str1) // false
ret2 := check(&str) // true

是不是很神奇。

表达式运算

"8+(3-1)*5"

计算上面的表达式的值。继续看栈的表演,按照下面的算法,遍历上面的中缀表达式将其变成后缀表达式 : (这是编译器的工作内容之一)

数字直接输出
符号:
    左括号直接进栈
    运算符: 和栈顶符号比较优先级(左括号优先级最低)
            栈顶优先级低,直接进栈
            否则将栈顶弹出输出,之后进栈
    又括号: 将栈顶符号弹出并输出,直到遇到左括号
结束: 将栈中所有符号弹出并输出
(输出是指: 将字符追加到后缀表达式)

实现如下:

func transform(str string) string {
    var stack Stack 
    var expression string = "" //初始化后缀表达式
    priority := map[string]int{"(":0,"+":1, "-":1, "*":2, "/":2}
    for i := 0; i < len(str); i++{
        current := string(str[i])
        if  match, _ := regexp.MatchString("\\d+", current); match {
            expression += current
        }else if current == "(" {
            stack.Push(current)
        }else if current == ")" {
            current_top, _ := stack.Pop() 
            for (current_top.(string) != "("){
                expression += current_top.(string)
                current_top, _ = stack.Pop()
            }
        }else{
            current_top, _ := stack.Top()
            if len(stack) == 0 || priority[current_top.(string)] < priority[current] {
                stack.Push(current)
            }else{
                current_top, _ := stack.Pop()
                expression += current_top.(string)
                stack.Push(current)
            }
        }
    }
    for len(stack) > 0{
        current_top, _ := stack.Pop()
        expression += current_top.(string)
    }
    return expression
}

expression := transform("8+(3-1)*5") //  831-5*+

然后遍历后缀表达式,按照下面的算法,将值计算出来(这是计算机的工作)

数字: 进栈
符号: 
    从栈中弹出右操作数
    从栈中弹出左操作数
    根据符号进行计算
    将运算结果压入栈中
结束时: 栈中的唯一数字为计算结果

简单实现如下:

func compute(str string) int { 
    var stack Stack 
    var result int = 0
    var right, left int
    for i := 0; i < len(str); i++{
        current := string(str[i])
        if match, _ := regexp.MatchString("\\d+", current); match {
            integer, _:=strconv.Atoi(current)
            stack.Push(integer)
        }else{
            r, _ := stack.Pop()
            l, _ := stack.Pop()
            right = r.(int)
            left = l.(int)
            switch current{
            case "-":
                result = left - right
            case "+":
                result = left + right
            case "*":
                result = left*right
            case "/":
                result = left/right
            }
            stack.Push(result)
        }   
    }
    coputingResult, _ := stack.Pop()
    return coputingResult.(int)
}
result := compute("831-5*+")  //18

神奇不神奇?算法的实现相对简单,但是要创造这些算法需要多么强悍的大脑!

函数调用

操作系统给每个线程都分配了一块独立的内存空间,这块内存空间被组织成栈的结构,其中存放着函数的临时变量。函数的调用过程,也就是一块块栈帧不断被创建和销毁,不断地压栈弹栈的过程。

函数执行过程

总结

在这快速变化的时代,多学习这些不变的知识,基础数据结构、算法、数学··· 也许才能真正做到以不变应万变。(搬砖后的小感慨)

暂无回复。
需要 登录 后方可回复, 如果你还没有账号请 注册新账号