implémentation de la pile Golang

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.

1. 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.

2. 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
}

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
}

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

2.2 Implémentation de liste chaînée

3. 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
}

Dans l'implémentation, nous définissons d'abord une structure node pour représenter chaque nœud de la liste chaînée. Chaque nœud contient un élément val et un pointeur vers le nœud suivant next. Ensuite, nous définissons la structure Stack pour représenter la pile, où le pointeur head pointe vers l'élément supérieur de la pile ; insère les éléments dans l'en-tête de la liste chaînée à son tour ; La fonction Pop() réalise l'opération pop en obtenant d'abord la valeur dans le nœud principal, puis en pointant le pointeur principal vers le nœud suivant ; la fonction IsEmpty() détermine si la pile est vide.

Utiliser la stack

4. 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 :
rrreee
Dans l'évaluation d'expression, nous utilisons l'idée de​​la pile pour traiter les expressions polonaises inversées. Divisez d’abord l’expression par espaces, puis traitez chaque partie. S'il s'agit d'un opérateur (+ - * /), les deux éléments en haut de la pile sont retirés, l'opération correspondante est effectuée et le résultat est poussé sur la pile s'il s'agit d'un opérande, il est poussé dessus ; la pile directement. Enfin, si la pile n'est pas vide, la valeur en haut de la pile est renvoyée comme résultat de l'opération.
🎜Résumé🎜🎜🎜Stack est une structure de données très pratique, qui a un large éventail d'applications dans de nombreuses situations. Il existe de nombreuses façons d'implémenter des piles à l'aide de Golang. Cet article présente principalement deux méthodes d'implémentation : les tranches et les listes chaînées. La mise en œuvre du découpage est simple et facile à comprendre, mais lorsque les éléments atteignent une grande taille, l'efficacité de l'allocation de mémoire diminuera ; la mise en œuvre de l'allocation de mémoire par liste chaînée est plus flexible, mais la complexité du code augmente également. Une sélection raisonnable des méthodes de mise en œuvre peut éviter un gaspillage inutile de ressources dans les applications pratiques et améliorer l'efficacité de l'exécution du programme. 🎜

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!