implémentation de la pile Golang-Golang-php.cn

implémentation de la pile Golang

王林

Libérer： 2023-05-16 11:06:37

original

659 Les gens l'ont consulté

Golang est un langage de programmation efficace, évolutif et simultané, largement utilisé et respecté dans l'industrie Internet. Pour les développeurs Golang, les structures de données et les algorithmes font partie des compétences de base, et la mise en œuvre de la pile est une partie essentielle. Dans cet article, nous examinerons en profondeur comment implémenter une pile dans Golang.

Qu'est-ce qu'une pile ?

La pile est une structure linéaire spéciale qui ne peut être utilisée qu'à une seule extrémité, c'est-à-dire que les éléments ne peuvent être insérés et supprimés qu'en haut de la pile. Par conséquent, la méthode d’accès aux données de la pile est « premier entré, dernier sorti ». Il s'agit d'une structure de données adaptée à de nombreuses occasions, telles que la mise en cache, l'évaluation d'expressions, l'appel de fonction, etc.

Les opérations de pile couramment utilisées incluent le push et le pop. Lors du push, le nouvel élément est toujours placé en haut de la pile ; lors du popping, l'élément supérieur est toujours supprimé, donc la longueur de la pile continuera à changer.

Comment implémenter la pile

Il existe deux façons d'implémenter la pile dans Golang : l'une consiste à utiliser Slice et l'autre à utiliser Linked List.

2.1 Implémentation de tranches

Lorsque vous utilisez des tranches pour implémenter une pile, notre structure de pile ne doit contenir qu'une seule tranche. Ce qui suit est un exemple simple de pile d'implémentation de tranche :

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
}

Copier après la connexion

Dans l'implémentation, nous définissons d'abord une structure Stack, qui contient une tranche données. La fonction Push() pousse les éléments en haut de la pile et ajoute les éléments à la fin de la tranche à leur tour ; la fonction Pop() fait apparaître les éléments du haut de la pile ; la pile en récupérant le dernier élément de la tranche. Un élément est ensuite supprimé de la tranche ; la fonction IsEmpty() détermine si la pile est vide. 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
}

Copier après la connexion

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

2.2 Implémentation de liste chaînée

La logique de base de la pile d'implémentation de liste chaînée est d'utiliser la tête de la liste chaînée comme haut de la pile Chaque fois qu'un élément est inséré, il est placé en tête, et à chaque fois qu'un élément est inséré. L'élément est sorti, l'élément en tête est supprimé. Voici un exemple de pile d'implémentation de liste chaînée :

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
}

Copier après la connexion

node

val

next

Stack

head

Pop()

IsEmpty()

Utiliser la stack

Les fonctions fournies par la stack sont un moyen d'améliorer le traitement de problèmes complexes. Les problèmes tels que l'évaluation d'expressions et la correspondance entre crochets peuvent être bien résolus en utilisant la pile. Voici un exemple de code d'évaluation d'expression implémenté à l'aide du découpage :

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!