栈 Stack

栈的介绍：

• 有些程序员也把栈称为堆栈，即栈和堆栈是同一个概念；
• 栈的英文为stack
• 栈是一个先入后出(FILO--First In Last Out)的有序列表；
• 栈 是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表；
  • 允许插入和删除的一端，为变化的一端，称为栈顶(Top),
  • 另一端为固定的一端，称为栈底(Bottom).
• 根据堆栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶；
  • 而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除；

栈的应用场景：

• 1.子程序的调用：在跳往子程序前，会先将下个指定的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中；
• 2.处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中；
• 3.表达式的转换与求值；
• 4.二叉树的遍历；
• 5.图形的深度优先(depth---first)搜索法。

栈的快速入门：

• 用数组模拟栈的使用，由于堆栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟 栈的出栈，入栈和遍历等操作。

//Version 0.0.1 
//只能计算 + - * / 
//并且数字只能识别1位数；
package main

import (
    "errors"
    "fmt"
)

//使用数组来模拟一个栈的使用
type Stack struct {
    MaxTop int    //表示我们栈最大可以存放数的个数；
    Top    int    // 表示栈顶，因为栈底是固定的，因此我们只定义Top
    arr    [5]int //数组模拟；
}

//Push 入栈
func (this *Stack) Push(val int) (err error) {

    //先判断栈是否已经满了；
    if this.Top == this.MaxTop-1 {
        fmt.Println("Stack Full")
        return errors.New("stack full")
    }

    this.Top++
    //放入数据
    this.arr[this.Top] = val
    return
}

//Pop 出栈
func (this *Stack) Pop() (val int, err error) {
    //判断栈是否为空；
    if this.Top == -1 {
        fmt.Println("Stack Empty")
        return 0, errors.New("stack empty")
    }

    //先取值，再this.Top--
    val = this.arr[this.Top]
    this.Top--
    return val, nil

}

//遍历栈，注意：需要从栈顶开始遍历
func (this *Stack) List() {
    //先判断栈是否为空
    if this.Top == -1 {
        fmt.Println("Stack Empty")
        return
    }

    fmt.Println("栈的情况如下:")
    for i := this.Top; i >= 0; i-- {
        fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
    }
}

func main() {
    stack := &Stack{
        MaxTop: 5,  //表示最多存放5个数到栈中 ；
        Top:    -1, //当栈顶为-1，表示栈为空；
    }

    //入栈
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    stack.Push(4)
    stack.Push(5)
    stack.Push(6)

    //显示
    stack.List()

    //出栈：
    val, _ := stack.Pop()
    fmt.Println("出栈val=", val)
    stack.List()
    fmt.Println()

    val, _ = stack.Pop()
    fmt.Println("出栈val=", val)
    stack.List()
    fmt.Println()

    val, _ = stack.Pop()
    val, _ = stack.Pop()
    val, _ = stack.Pop()
    val, _ = stack.Pop()
    fmt.Println("出栈val=", val)
    stack.List()
    fmt.Println()
}

栈实现综合计算器：

算法分析：

• 1.创建两个栈：numStack,operStack
• 2.numStack存放数，operStack存放操作符；
• 3.index := 0,表示 字符串表达式的索引；
• 4.exp计算表达式，是一个字符串；
• 5.如果扫描发现是一个数组，则直接入numStack；
• 6.如果发现是一个运算符：
  • 6.1 如果operStack是一个空栈，则直接入栈；
  • 6.2 如果operStack不是一个空栈：
    • 6.2.1 如果发现operStack栈顶的运算符的优先级大于等于当前准备入栈的运算符的优先级，就从operStack pop出来，并从numStack也pop出两个数，进行计算，运算后的结果再重新入栈到numStack，遍历到的运算符再入栈到operStack；
    • 6.2.2 否则，运算符直接入栈operStack；
• 7.如果扫描表达式完毕，依次从符号栈取出符号，然后从numStack取出两个数，进行运算，运算后的结果，入numStack，直到operStack为空；

package main

import (
    "errors"
    "fmt"
    "strconv"
)

//使用数组来模拟一个栈的使用
type Stack struct {
    MaxTop int     //表示我们栈最大可以存放数的个数；
    Top    int     // 表示栈顶，因为栈底是固定的，因此我们只定义Top
    arr    [20]int //数组模拟；
}

//Push 入栈
func (this *Stack) Push(val int) (err error) {

    //先判断栈是否已经满了；
    if this.Top == this.MaxTop-1 {
        fmt.Println("Stack Full")
        return errors.New("stack full")
    }

    this.Top++
    //放入数据
    this.arr[this.Top] = val
    return
}

//Pop 出栈
func (this *Stack) Pop() (val int, err error) {
    //判断栈是否为空；
    if this.Top == -1 {
        fmt.Println("Stack Empty")
        return 0, errors.New("stack empty")
    }

    //先取值，再this.Top--
    val = this.arr[this.Top]
    this.Top--
    return val, nil

}

//遍历栈，注意：需要从栈顶开始遍历
func (this *Stack) List() {
    //先判断栈是否为空
    if this.Top == -1 {
        fmt.Println("Stack Empty")
        return
    }

    fmt.Println("栈的情况如下:")
    for i := this.Top; i >= 0; i-- {
        fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
    }
}

//判断一个字符是不是一个运算符[+,-,*,/]
func (this *Stack) IsOper(val int) bool {
    if val == 42 || val == 43 || val == 45 || val == 47 {
        return true
    } else {
        return false
    }
}

//运算的方法：
func (this *Stack) Cal(num1 int, num2 int, oper int) int {
    res := 0
    switch oper {
    case 42:
        res = num2 * num1
    case 43:
        res = num2 + num1
    case 45:
        res = num2 - num1
    case 47:
        res = num2 / num1
    default:
        fmt.Println("运算符错误...")
    }
    return res
}

//编写一个方法，返回某个运算符的优先级[程序员定义]
// [* / ==> 1    + - ==> 0]
func (this *Stack) Priority(oper int) int {
    res := 0
    if oper == 42 || oper == 47 {
        res = 1
    } else if oper == 43 || oper == 45 {
        res = 0
    }
    return res
}

func main() {

    //数栈
    numStack := &Stack{
        MaxTop: 20,
        Top:    -1,
    }

    //符号栈
    operStack := &Stack{
        MaxTop: 20,
        Top:    -1,
    }

    exp := "3+3*6-4"
    //定义一个index，帮助扫描表达式
    index := 0

    //为了配合运算，我定义需要的变量；
    num1 := 0
    num2 := 0
    oper := 0
    result := 0

    for {
        ch := exp[index : index+1] //字符串
        // ch ==> "+" ==> 43,
        temp := int([]byte(ch)[0])  //就是字符对应的ASCII码；
        if operStack.IsOper(temp) { //说明是符号；
            //分两个逻辑
            //如果operStack是一个空栈，直接入栈
            if operStack.Top == -1 { //空栈
                operStack.Push(temp)
            } else { //不是空栈：
                //如果发现operStack栈顶的运算符的优先级大于等于当前准备入栈的运算符的优先级，
                //就从operStack pop出来，并从numStack也pop出两个数，进行计算，
                //运算后的结果再重新入栈到numStack，遍历到的运算符再入栈到operStack
                if operStack.Priority(operStack.arr[operStack.Top]) >= operStack.Priority(temp) {
                    num1, _ = numStack.Pop()
                    num2, _ = numStack.Pop()
                    oper, _ = operStack.Pop()
                    result = operStack.Cal(num1, num2, oper)
                    //将计算结果重新入数栈
                    numStack.Push(result)
                    //将当前的符号压入operStack
                    operStack.Push(temp)
                } else {
                    operStack.Push(temp)
                }
            }
        } else { //说明是数
            val, _ := strconv.ParseInt(ch, 10, 64)
            numStack.Push(int(val))
            // numStack.Push(temp)   //错误，3 ==> 51
        }

        //继续扫描
        //先判断index是否已经扫描到计算表达式的最后：
        if index+1 == len(exp) {
            break
        }
        index++
    }

    //7.如果扫描表达式完毕，依次从符号栈取出符号，然后从numStack取出两个数，进行运算，
    //运算后的结果，入numStack，直到operStack为空；
    for {
        if operStack.Top == -1 {
            break //退出条件；
        }

        num1, _ = numStack.Pop()
        num2, _ = numStack.Pop()
        oper, _ = operStack.Pop()
        result = operStack.Cal(num1, num2, oper)
        //将计算结果重新入数栈
        numStack.Push(result)
    }

    //如果我们的算法没有问题，表达式也是正确的，则结果就是numStack最后的数；
    res, _ := numStack.Pop()
    fmt.Printf("表达式%s = %v\n", exp, res)
}

Version2:处理了多位数问题：

package main

import (
    "errors"
    "fmt"
    "strconv"
)

//使用数组来模拟一个栈的使用
type Stack struct {
    MaxTop int     //表示我们栈最大可以存放数的个数；
    Top    int     // 表示栈顶，因为栈底是固定的，因此我们只定义Top
    arr    [20]int //数组模拟；
}

//Push 入栈
func (this *Stack) Push(val int) (err error) {

    //先判断栈是否已经满了；
    if this.Top == this.MaxTop-1 {
        fmt.Println("Stack Full")
        return errors.New("stack full")
    }

    this.Top++
    //放入数据
    this.arr[this.Top] = val
    return
}

//Pop 出栈
func (this *Stack) Pop() (val int, err error) {
    //判断栈是否为空；
    if this.Top == -1 {
        fmt.Println("Stack Empty")
        return 0, errors.New("stack empty")
    }

    //先取值，再this.Top--
    val = this.arr[this.Top]
    this.Top--
    return val, nil

}

//遍历栈，注意：需要从栈顶开始遍历
func (this *Stack) List() {
    //先判断栈是否为空
    if this.Top == -1 {
        fmt.Println("Stack Empty")
        return
    }

    fmt.Println("栈的情况如下:")
    for i := this.Top; i >= 0; i-- {
        fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
    }
}

//判断一个字符是不是一个运算符[+,-,*,/]
func (this *Stack) IsOper(val int) bool {
    if val == 42 || val == 43 || val == 45 || val == 47 {
        return true
    } else {
        return false
    }
}

//运算的方法：
func (this *Stack) Cal(num1 int, num2 int, oper int) int {
    res := 0
    switch oper {
    case 42:
        res = num2 * num1
    case 43:
        res = num2 + num1
    case 45:
        res = num2 - num1
    case 47:
        res = num2 / num1
    default:
        fmt.Println("运算符错误...")
    }
    return res
}

//编写一个方法，返回某个运算符的优先级[程序员定义]
// [* / ==> 1    + - ==> 0]
func (this *Stack) Priority(oper int) int {
    res := 0
    if oper == 42 || oper == 47 {
        res = 1
    } else if oper == 43 || oper == 45 {
        res = 0
    }
    return res
}

func main() {

    //数栈
    numStack := &Stack{
        MaxTop: 20,
        Top:    -1,
    }

    //符号栈
    operStack := &Stack{
        MaxTop: 20,
        Top:    -1,
    }

    exp := "30+33*6-4-22/10"
    //定义一个index，帮助扫描表达式
    index := 0

    //为了配合运算，我定义需要的变量；
    num1 := 0
    num2 := 0
    oper := 0
    result := 0

    keepNum := ""

    for {
        //这里我们需要增加一个逻辑，
        //处理多位数的问题；

        ch := exp[index : index+1] //字符串
        // ch ==> "+" ==> 43,
        temp := int([]byte(ch)[0])  //就是字符对应的ASCII码；
        if operStack.IsOper(temp) { //说明是符号；
            //如果operStack是一个空栈，直接入栈
            if operStack.Top == -1 { //空栈
                operStack.Push(temp)
            } else { //不是空栈：
                //如果发现operStack栈顶的运算符的优先级大于等于当前准备入栈的运算符的优先级，
                //就从operStack pop出来，并从numStack也pop出两个数，进行计算，
                //运算后的结果再重新入栈到numStack，遍历到的运算符再入栈到operStack
                if operStack.Priority(operStack.arr[operStack.Top]) >= operStack.Priority(temp) {
                    num1, _ = numStack.Pop()
                    num2, _ = numStack.Pop()
                    oper, _ = operStack.Pop()
                    result = operStack.Cal(num1, num2, oper)
                    //将计算结果重新入数栈
                    numStack.Push(result)
                    //将当前的符号压入operStack
                    operStack.Push(temp)
                } else {
                    operStack.Push(temp)
                }
            }
        } else { //说明是数
            // val, _ := strconv.ParseInt(ch, 10, 64)
            // numStack.Push(int(val))
            // numStack.Push(temp)   //错误，3 ==> 51

            //处理多位数的思路
            //1.定义一个变量 keepNum string,做拼接；
            keepNum += ch
            //2.每次要向index的前面字符测试一下，看看是不是运算符，然后处理；

            //如果已经到表达式最后，直接将keepNum
            if index == len(exp)-1 {
                val, _ := strconv.ParseInt(keepNum, 10, 64)
                numStack.Push(int(val))
            } else {
                //向index 后面测试看看是不是运算符 [index]
                if operStack.IsOper(int([]byte(exp[index+1 : index+2])[0])) {
                    val, _ := strconv.ParseInt(keepNum, 10, 64)
                    numStack.Push(int(val))
                    keepNum = ""
                }
            }
        }

        //继续扫描
        //先判断index是否已经扫描到计算表达式的最后：
        if index+1 == len(exp) {
            break
        }
        index++
    }

    //7.如果扫描表达式完毕，依次从符号栈取出符号，然后从numStack取出两个数，进行运算，
    //运算后的结果，入numStack，直到operStack为空；
    for {
        if operStack.Top == -1 {
            break //退出条件；
        }

        num1, _ = numStack.Pop()
        num2, _ = numStack.Pop()
        oper, _ = operStack.Pop()
        result = operStack.Cal(num1, num2, oper)
        //将计算结果重新入数栈
        numStack.Push(result)
    }

    //如果我们的算法没有问题，表达式也是正确的，则结果就是numStack最后的数；
    res, _ := numStack.Pop()
    fmt.Printf("表达式%s = %v\n", exp, res)
}