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

什么是栈

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

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

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

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

函数调用

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

总结

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