线性表又有多种分类

1. 顺序表（数组）

2. 链表

2.1 单链表

2.2 双链表

3. 栈

自定义栈帧实现

  1. const MaxSize int = 20
  3. type Stack struct {
  4.     Data []string
  5.     top  int
  6. }
  8. // 创建一个栈帧
  9. func CreateStack() *Stack {
  10.     return &Stack{Data: make([]string, MaxSize), top: -1}
  11. }
  12. // 栈帧是否为空
  13. func (s *Stack) IsEmpty() bool {
  14.     return s.top == -1
  15. }
  16. // 栈帧是否满了
  17. func (s *Stack) IsFull() bool {
  18.     return s.top == MaxSize-1
  19. }
  20. // 入栈
  21. func (s *Stack) push(ele string) bool {
  22.     if s.IsFull() {
  23.         return false
  24.     }
  25.     s.top++
  26.     s.Data[s.top] = ele
  27.     return true
  28. }
  29. // 出栈
  30. func (s *Stack) pop() string {
  31.     // 
  32.     if s.IsEmpty() {
  33.         return "" // go语言的默认值就是"",且不能赋值nil
  34.     }
  35.     ele := s.Data[s.top]
  36.     s.Data[s.top] = "" // 置空
  37.     s.top--
  38.     return ele
  39. }

3.1 栈在括号匹配中的运用

最后出现的左括号最先被匹配（LIFO）,使用上面的栈帧实现

  1. func checkBracket(str string, stack *Stack) {
  2.     for _, s := range str {
  3.         ele := string(s)
  4.         if ele == "{" || ele == "(" || ele == "[" {
  5.             stack.push(string(s))
  6.         } else if ele == "}" {
  7.             curr := stack.pop()
  8.             if curr != "{" {
  9.                 fmt.Println("}匹配错误，期望出现{，但是匹配到", curr)
  10.             }
  11.         } else if ele == "]" {
  12.             curr := stack.pop()
  13.             if curr != "[" {
  14.                 fmt.Println("]匹配错误，期望出现[，但是匹配到", curr)
  15.             }
  16.         } else if ele == ")" {
  17.             curr := stack.pop()
  18.             if curr != "(" {
  19.                 fmt.Println(")匹配错误，期望出现(，但是匹配到", curr)
  20.             }
  21.         }
  22.     }
  23.     if !stack.IsEmpty() {
  24.         fmt.Print("括号不匹配,未找到配对：")
  25.         for i := 0; i <= stack.top; i++ {
  26.             fmt.Print(stack.Data[i], " ")
  27.         }
  28.     }
  29. }
  31. // main
  32. func main() {
  33.     var str = "((([[{}]]))"
  34.     stack := CreateStack()
  35.     checkBracket(str, stack)
  36. }

3.2 中缀表达式转后缀表达式

利用前面实现的栈帧实现中缀表达式，转后缀表达式

中缀表达式a + bc + (d e + f) g，其转换成后缀表达式则为a b c + d e f + g +。

转换过程需要用到栈，具体过程如下：

  1. 如果遇到操作数，我们就直接将其输出。
  2. 如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
  3. 如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
  4. 如果遇到任何其他的操作符，如（“+”， “”，“（”）等，从栈中弹出元素直到遇到发现*更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。

  5. 如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

    1. func transToEndExpression(str string) (string, bool) {
    2.  // 操作符
    3.  OpMap := map[string]int{
    4.      "+": 1,
    5.      "-": 1,
    6.      "*": 2,
    7.      "/": 2,
    8.      "(": 3,
    9.      ")": 3,
    10.  }
    11.  // 特殊定义左右括号
    12.  BracketMap := map[string]bool{
    13.      "(": true,
    14.      ")": true,
    15.  }
    17.  // 校验括号
    18.  var ops string = ""
    19.  for i := 0; i < len(str); i++ {
    20.      if BracketMap[string(str[i])] {
    21.          ops += string(str[i])
    22.      }
    23.  }
    25.  if len(ops) > 0 {
    26.      canDo := checkBracket(ops, CreateStack())
    27.      if !canDo {
    28.          // 括号不符合规则
    29.          return "", false
    30.      }
    31.  }
    33.  // 处理掉空字符
    34.  exp := strings.ReplaceAll(str, " ", "")
    35.  // 存放操作符的栈
    36.  stack := CreateStack()
    38.  // 最终后缀表达式
    39.  var result string = ""
    40.  // 遍历表达式
    41.  for _, ch := range exp {
    42.      arg := string(ch)
    43.      x := OpMap[arg]
    44.      if x == 0 {
    45.          // 操作数，直接追加到表达式后面
    46.          result = result + arg
    47.      } else {
    48.          // 是否是右括号
    49.          if ")" == arg {
    50.              // 遇到右括号")"，需要弹出栈中所有的操作符，直到遇到左括号"("
    51.              for true {
    52.                  topEle := stack.pop()
    53.                  if topEle == "(" {
    54.                      // 遇到左括号退出循环
    55.                      break
    56.                  }
    57.                  // 将操作符追加到表达式后面
    58.                  result += topEle
    59.              }
    60.          } else {
    61.              for true {
    62.                  // 将栈中所有优先级大于或等于当前操作符的，全部出栈追加到表达式后面
    63.                  topOperator := stack.getTopEle()
    64.                  if "(" != topOperator && OpMap[topOperator] >= OpMap[arg] {
    65.                      result += stack.pop()
    66.                  } else {
    67.                      break
    68.                  }
    69.              }
    70.              // 最后，将当前操作符入栈
    71.              stack.push(arg)
    72.          }
    73.      }
    74.  }
    76.  // 处理栈帧剩余元素
    77.  for !stack.IsEmpty() {
    78.      result += stack.pop()
    79.  }
    80.  return result, true
    81. }

    测试

    1. func main() {
    2.  // a + b - c * (d-f) - r
    3.  var str string = "a + b - c * ((d-f) - r"
    4.  result, err := transToEndExpression(str)
    5.  if !err {
    6.      fmt.Println("表达式:\t\t", str)
    7.      fmt.Println("后缀表达式为:\t", result)
    8.  }
    9. }

    我们实现了中缀转后缀，接下来就是实现计算机如何计算后缀表达式

    3.3 计算后缀表达式结果

    利用go语言模拟计算机计算后缀表达式 ```go

/**

  • 计算后缀表达式 */ func calculateSuffixExp(expression string) (string, bool) { stack := CreateStack() arr := strings.Split(expression, “ “)

    for _, ele := range arr {

    1.  if ele == "" {
    2.      continue
    3.  }
    4.  // 遇到操作数压栈，遇到操作符，取出两个操作数计算
    5.  if "+" == ele {
    6.      second := stack.pop()
    7.      first := stack.pop()
    8.      firstNum, _ := strconv.Atoi(first)
    9.      secondNum, _ := strconv.Atoi(second)
    10.      result := firstNum + secondNum
    11.      // 再压入栈
    12.      stack.push(strconv.Itoa(result))
    13.  } else if "-" == ele {
    14.      second := stack.pop()
    15.      first := stack.pop()
    16.      firstNum, _ := strconv.Atoi(first)
    17.      secondNum, _ := strconv.Atoi(second)
    18.      result := firstNum - secondNum
    19.      // 再压入栈
    20.      stack.push(strconv.Itoa(result))
    21.  } else if "*" == ele {
    22.      second := stack.pop()
    23.      first := stack.pop()
    24.      firstNum, _ := strconv.Atoi(first)
    25.      secondNum, _ := strconv.Atoi(second)
    26.      result := firstNum * secondNum
    27.      // 再压入栈
    28.      stack.push(strconv.Itoa(result))
    29.  } else if "/" == ele {
    30.      second := stack.pop()
    31.      first := stack.pop()
    32.      firstNum, _ := strconv.Atoi(first)
    33.      secondNum, _ := strconv.Atoi(second)
    34.      result := firstNum / secondNum
    35.      // 再压入栈
    36.      stack.push(strconv.Itoa(result))
    37.  } else {
    38.      _, err := strconv.Atoi(ele)
    39.      if err != nil {
    40.          fmt.Println("非数字错误.....")
    41.          return "", true
    42.      }
    43.      stack.push(ele)
    44.  }

    } result := stack.pop() return result, false }

// 

  1. 测试
  2. ```go
  3. func main() {
  5.     var exp string = "1+3+5*5+2-9/3-4"
  6.     // 后缀表达式 1 3 + 5 5 * + 2 + 10 5 / - 3 -
  8.     expression, succ := transToEndExpression(exp)
  9.     if succ {
  10.         // 计算
  11.         result, done := calculateSuffixExp(expression)
  12.         if done {
  13.             return
  14.         }
  15.         fmt.Println("计算结果：", exp, "=", result)
  16.     }
  17. }

卡特兰数

4. 队列

4.1 队列

4.2 双端队列