golang栈实现

2023-05-16 11:05:13 Golang

golang是一种高效、可扩展和并发性强的编程语言，在互联网行业中被广泛使用和推崇。对于Golang的开发者来说，数据结构和算法是基本功之一，而其中栈(Stack)的实现是必不可少的一部分。在本文中，我们将深入探讨如何在Golang中实现栈。

  1. 什么是栈？

栈是一种特殊的线性结构，它只能在一端进行操作，即只能在栈顶进行元素的插入和删除。因此，栈的数据访问方式是“先进后出”。它是一个适用于多种场合的数据结构，如缓存、表达式求值、函数调用等。

常用的栈操作有入栈(push)和出栈(pop)两种操作，入栈时，新的元素总是放在栈顶位置；出栈时，总是删除栈顶元素，因此栈的长度会不断的变化。

  1. 栈的实现方式

在Golang中实现栈有两种方式：一种是使用切片(Slice)，另一种是使用链表(Linked List)。

2.1 切片实现

在使用切片实现栈时，我们的栈结构体只需要包含一个切片即可。下面是切片实现栈的简单示例：

type Stack struct {
  data []interface{}
}

func (s *Stack) Push(val interface{}) {
    s.data = append(s.data, val)
}

func (s *Stack) Pop() interface{} {
    if s.IsEmpty() {
        return nil
    }
    last := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return last
}

func (s *Stack) IsEmpty() bool {
    return len(s.data) == 0
}

在实现中，我们首先定义了一个结构体Stack，它包含一个切片data。Push()函数将元素压入栈顶，依次将元素添加到切片末尾；Pop()函数将元素从栈顶弹出，通过获取切片中的最后一个元素，然后将该元素从切片中删除；IsEmpty()函数判断栈是否为空。

2.2 链表实现

链表实现栈的基本逻辑是使用链表的头部作为栈顶，每插入一个元素，就将其放在头部，每弹出一个元素就将头部的元素删除。下面是链表实现栈的示例：

type node struct {
  val  interface{}
  next *node
}

type Stack struct {
  head *node
}

func (s *Stack) Push(val interface{}) {
  s.head = &node{val, s.head}
}

func (s *Stack) Pop() interface{} {
  if s.head == nil {
    return nil
  }
  val := s.head.val
  s.head = s.head.next
  return val
}

func (s *Stack) IsEmpty() bool {
  return s.head == nil
}

在实现中，我们首先定义一个结构体node表示链表的每一个节点。每个节点都包含一个元素val，和一个指向下一个节点的指针next。然后我们定义结构体Stack表示栈，其中head指针指向栈顶元素；Push()函数依次将元素插入到链表头部；Pop()函数通过先获取头部节点中的值，然后再将头部指针指向下一个节点实现弹出操作；IsEmpty()函数判断栈是否为空。

  1. 使用栈

栈所提供的功能是加强复杂的问题处理的一种方式。对于表达式求值、括号匹配等问题，使用栈都能够得到良好的解决。下面是使用切片实现的表达式求值代码示例：

func EvaluateExpression(expression string) (float64, error) {
  stack := Stack{}
  tokens := strings.Split(expression, " ")
  for _, token := range tokens {
    switch token {
      case "+", "-", "*", "/":
        if stack.IsEmpty() {
          return 0, errors.New("Invalid expression")
        }
        b, err := stack.Pop().(float64)
        if !err {
          return 0, errors.New("Invalid expression")
        }
        if stack.IsEmpty() {
          return 0, errors.New("Invalid expression")
        }
        a, err := stack.Pop().(float64)
        if !err {
          return 0, errors.New("Invalid expression")
        }
        var result float64
        switch token {
          case "+":
            result = a + b
          case "-":
            result = a - b
          case "*":
            result = a * b
          case "/":
            result = a / b
        }
        stack.Push(result)
      default:
        num, err := strconv.ParseFloat(token, 64)
        if err != nil {
          return 0, errors.New("Invalid expression")
        }
        stack.Push(num)
    }
  }
  if stack.IsEmpty() {
    return 0, errors.New("Invalid expression")
  }
  result, err := stack.Pop().(float64)
  if !err || !stack.IsEmpty() {
    return 0, errors.New("Invalid expression")
  }
  return result, nil
}

在表达式求值中，我们使用了栈的思想来处理逆波兰表达式。首先将表达式按照空格分割开来，然后对每一部分进行处理。如果是操作符（+ - * /），则取出栈顶的两个元素进行相应的运算，并将结果压入栈中；如果是操作数，则直接将其压入栈中。最后，如果栈不为空，将栈顶的值作为运算结果返回。

  1. 总结

栈是一种非常实用的数据结构，它在很多场合都有着广泛的应用。使用Golang实现栈的方法有很多种，本文主要介绍了切片和链表两种实现方式。切片的实现方式简单易懂，但当元素达到较大规模时，会导致内存分配的效率下降；链表的实现方式内存分配更加为灵活，但代码的复杂度也有所增加。合理选择实现方式可以在实际应用中避免浪费不必要的资源，提高程序的执行效率。

以上就是golang栈实现的详细内容，更多请关注其它相关文章！

相关文章