目录

• 数据结构——栈
• • 顺序栈
  • • 1. 定义结构体
    • 2. NewStack()
    • 3. Length()
    • 4. IsFull()
    • 5. IsEmpty()
    • 6. Push()
    • 7. Pop()
    • 8. Peek()
  • 链式栈
  • • 1. 定义结构体
    • 2. IsEmpty()
    • 3. Length()
    • 4. Push()
    • 5. Pop()
    • 6. Peek()
    • 7. Traverse()
  • 应用场景
  • • 1. 表达式求值
    • 2. 括号匹配

数据结构——栈

顺序栈

1. 定义结构体

type SequentialStack struct {items []any // 栈内元素top   int   // 栈顶,也是栈内元素数size  int   // 栈容量
}

2. NewStack()

// NewStack 初始化栈
func NewStack(size int) *SequentialStack {return &SequentialStack{size:  size,top:   0,items: make([]any, size),}
}

3. Length()

// Length 获取栈内元素个数
func (stack *SequentialStack) Length() int {return stack.top
}

4. IsFull()

// IsFull 判断栈是否已满
func (stack *SequentialStack) IsFull() bool {return stack.top == stack.size // 如果top=设定的栈最大长度，说明栈满
}

5. IsEmpty()

// IsEmpty 判断栈是否已空
func (stack *SequentialStack) IsEmpty() bool {return stack.top == 0
}

6. Push()

// Push 入栈
func (stack *SequentialStack) Push(item any) bool {if stack.IsFull() {fmt.Println("栈满")return false}stack.items[stack.top] = itemstack.top++return true
}

7. Pop()

// Pop 出栈
func (stack *SequentialStack) Pop() any {if stack.IsEmpty() {fmt.Println("栈已空")return nil}stack.top-- // 栈顶指针下移return stack.items[stack.top]
}

8. Peek()

// Peek 获取栈顶元素但不出栈
func (stack *SequentialStack) Peek() any {if stack.IsEmpty() {fmt.Println("栈空")return nil}return stack.items[stack.top-1]
}

链式栈

1. 定义结构体

type SequentialStack struct {items []any // 栈内元素top   int   // 栈顶,也是栈内元素数size  int   // 栈容量
}

2. IsEmpty()

// IsEmpty 判断栈是否为空
func (stack *LinkedStack) IsEmpty() bool {return stack.headNode == nil
}

3. Length()

// Length 获取栈内元素个数
func (stack *LinkedStack) Length() int {if stack.IsEmpty() {return 0}currentNode := stack.headNodecount := 0for currentNode != nil {count++currentNode = currentNode.Next}return count
}

4. Push()

// Push 入栈
func (stack *LinkedStack) Push(data any) {node := &Node{Data: data}node.Next = stack.headNodestack.headNode = node
}

5. Pop()

// Pop 出栈
func (stack *LinkedStack) Pop() any {if stack.headNode == nil {fmt.Println("栈已空")return nil}data := stack.headNode.Datastack.headNode = stack.headNode.Nextreturn data
}

6. Peek()

// Peek 获取栈顶元素但不出栈
func (stack *LinkedStack) Peek() any {if stack.IsEmpty() {fmt.Println("栈已空")return nil}return stack.headNode.Data
}

7. Traverse()

// Traverse 遍历链式栈
func (stack *LinkedStack) Traverse() {if stack.headNode == nil {fmt.Println("空栈")return}currentNode := stack.headNodefor currentNode.Next != nil {fmt.Printf("%v -> ", currentNode.Data)currentNode = currentNode.Next}fmt.Println(currentNode.Data)
}

应用场景

1. 表达式求值

一个表达式包含两个部分，数字和运算符。我们用两个栈来实现表达式求值，一个栈用来存储数字，一个栈用来存储运算符。

假设有这么一个表达式1000+5*6-6，从左向右遍历表达式，当遇到数字时，将数字放入到存储数字的栈；如果遇到运算符，将存储运算符栈的栈顶元素取出，进行优先级比较。

如果比运算符栈顶元素优先级高，则将当前运算符压入到存储运算符的栈中；如果比运算符栈顶元素低或优先级一样，则从存储数字的栈中取出两个元素，然后进行计算，将计算的结果放入到存储数字的栈中。
代码实现（例如“1000+5*6-6”这样简单的正整数运算，不包括() [] ）：

// 只包括+-*/的简单正整数运算，不包括负数 [] ()
var numStack = NewStack(20)  //储存数字
var operStack = NewStack(20) // 储存运算符// Calculation 表达式计算
// 关键：
//
//	如果遍历到的运算符 优先级高于 栈顶运算符，直接存入运算符栈;
//	反之 计算之前所有存入栈中的数字，然后将结果存入numStack,再将该运算符存入operStack;
func Calculation(expr string) (int, error) {last := -1 // 记录上一个是否是数字for i, s := range expr { // 遍历表达式isNum := GetPriority(s) // 获取 当前 s的优先级if isNum == 0 {         // 如果是数字，直接入栈if last == 0 { // 判断上一个是否是数字，如果是，就需要弹出、拼接、重新入栈lastNum := strconv.Itoa(numStack.Pop().(int))newNum, _ := strconv.Atoi(lastNum + string(s))numStack.Push(newNum)} else { // 如果不是，直接入栈即可num, _ := strconv.Atoi(string(s))numStack.Push(num)if i == len(expr)-1 { // 如果是最后一个字符，进行最终计算for !operStack.IsEmpty() && !numStack.IsEmpty() {first := numStack.Pop()second := numStack.Pop()oper := operStack.Pop().(int32)calResult := GetCalResult(second.(int), first.(int), oper)numStack.Push(calResult)}}}last = isNum // 更新last状态} else { // s 是运算符last = isNumif operStack.IsEmpty() { // 当前运算符栈为空,直接入栈即可operStack.Push(s)continue}topOper := operStack.Peek().(int32)     // 栈顶运算符topOperPriority := GetPriority(topOper) // 获取栈顶运算符优先级if isNum > topOperPriority { // 如果当前运算符优先级>栈底运算符优先级 ，直接入栈operStack.Push(s)continue} else { // 反之，将栈内所有元素弹出进行运算，并将结果入栈，再将该运算符入栈for !operStack.IsEmpty() && !numStack.IsEmpty() {first := numStack.Pop()second := numStack.Pop()oper := operStack.Pop().(int32)calResult := GetCalResult(second.(int), first.(int), oper) // 注意这里first和second的位置numStack.Push(calResult)}operStack.Push(s)}}}return numStack.Peek().(int), nil
}// GetCalResult 获取两数计算结果
func GetCalResult(a, b int, oper int32) int {switch oper {case 42:return a * bcase 43:return a + bcase 45:return a - bcase 47:return a / bdefault:return 0}
}// GetPriority 获取符号优先级 + - * /
func GetPriority(c int32) int {if c == 43 || c == 45 { // + -return 1} else if c == 42 || c == 47 { // * /return 2} else {return 0 // 数字}
}

2. 括号匹配

用栈来解决。从左到右遍历括号串，遇到未匹配的左括号则将其压入栈中，遇到右括号时，从栈顶取出一个左括号，如果能匹配，则继续遍历后边的括号，当遍历完之后，栈为空了，说明这个括号串是匹配的，否则是不匹配的。具体实现如下：

// BracketMatch 括号匹配
func BracketMatch(str string) bool {leftBracketStack := NewStack(10) // 左括号栈for _, s := range str {if s == '[' || s == '(' || s == '{' { // 左括号直接入栈leftBracketStack.Push(s)} else {if leftBracketStack.IsEmpty() { // 如果左括号已经消耗完仍有有括号，直接false即可return false}rightBracket := leftBracketStack.Pop()switch rightBracket {case '(':if s == ')' {continue} else {return false}case '[':if s == ']' {continue} else {return false}case '{':if s == '}' {continue} else {return false}default:fmt.Println("非法字符")return false}}}return leftBracketStack.Length() == 0
}

// BracketMatch2 括号匹配
func  BracketMatch2更简单的方法(str string) bool {brackets := map[int32]int32{')': '(', ']': '[', '}': '{'}var stack []int32for _, s := range str {if s == '[' || s == '(' || s == '{' { // 左括号直接入栈stack = append(stack, s)} else if len(stack) != 0 && brackets[s] == stack[len(stack)-1] { // 如果栈内有左括号，而且栈顶左括号与s匹配，出栈stack = stack[:len(stack)-1]} else {return false}}return len(stack) == 0
}