数据结构第二篇,本文简单介绍一下,一个在计算机科学界如雷贯耳
且堪称中流砥柱
,但是在搬砖过程中几乎用不到的数据结构:栈。
栈在计算机领域名声非常大,大家都知道它是一种后进先出、先进后出
的数据结构。有些资料上将其称为功能受限
的线性表,只能在尾部进行插入或弹出操作,不能像数组那样随机访问,不能简单遍历。这确实是一种很贴切的说法。
子弹只能从头部一个个装进来,也只能在头部被一颗颗打出去。核心实现样例如下:
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
神奇不神奇?算法的实现相对简单,但是要创造这些算法需要多么强悍的大脑!
操作系统给每个线程都分配了一块独立的内存空间,这块内存空间被组织成栈的结构,其中存放着函数的临时变量。函数的调用过程,也就是一块块栈帧不断被创建和销毁,不断地压栈弹栈的过程。
在这快速变化的时代,多学习这些不变的知识,基础数据结构、算法、数学··· 也许才能真正做到以不变应万变。(搬砖后的小感慨)