GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Implémentation d'une pile en Go ======

===== Choix de structure =====

Go accepte des tableaux de taille variable, les [[nsi:langages:go:tableaux|slices]]. On pourrait s'en servir pour stocker une pile qui a par définition une taille variable. Mais les slices permettent seulement d'ajouter des éléments pas d'en enlever. Je vais donc utiliser une approche semblable à celle que l'on aurait en C, avec une pile stockée dans un tableau avec une taille maximale fixée au départ, ce qui est une façon de faire très courante.

Notre pile sera donc contenue dans un tableau initialisée avec une taille fixe et connue. Comme la pile a une taille variable, à un moment de l'exécution, elle n'utilise qu'une partie du tableau. La dernière case du tableau sera un entier indiquant le nombre d'élément dans la pile.

<code lang-none linenums>
pile vide : [?, ?, ?, ?, ..., 0]
empiler 15 : [15, ?, ?, ?, ..., 1]
empiler 28 : [15, 28, ?, ?, ..., 2]
empiler 34 : [15, 28, 34, ?, ..., 3]
dépiler : [15, 28, ?, ?, ..., 2] et renvoie 34
</code>

<WRAP tip>Remarquez qu'à la dernière ligne, //dépiler//, il n'est pas nécessaire d'effacer 34 dans le tableau. Le tableau contient toujours le nombre 34 dans cette case. Le ""?"" indiqué en 3e position indique seulement qu'il y a une valeur à cette endroit et que cette valeur n'a plus aucune importance.\\ Lors du prochain empilement, cette valeur sera remplacée par la valeur empilée.</WRAP>

<WRAP tip>Cette technique fonctionne puisque notre pile contiendra des entiers. Nous pouvons donc prévoir un tableau d'entiers qui contiendra les éléments de la pile et la taille de la pile. Si notre pile avait dû contenir des caractères, le tableau n'aurait pas pu contenir à la fois les caractères de la pile et la taille de la pile... Il faudrait alors utiliser une structure contenant d'une part un tableau pour contenir les éléments de la pile, et un entier pour la taille de la pile.</WRAP>

===== Beaucoup plus simple qu'en C =====

Nous allons reprendre ici une [[nsi:langages:c:solutions:pile|implantation]] similaire à celle de C, mais ce sera beaucoup plus simple car Go -- c'est justement le but de Go, faire du C plus simplement -- car nous n'aurons plus à gérer des pointeurs ou l'allocation mémoire.


===== Les détails =====

==== Création de la pile vide ====

On commence par définir la taille maximale de la pile. On utilise pour cela une constante.

<code go linenums:9>
const N = 1000
</code>

<code go linenums:30>
func CREER_PILE_VIDE() []int{
  /* retourne une pile de contenu vide */
  p := make([]int, N+1) // N cases pour la pile + 1 pour la taille
  p[N] = 0      // Dernière case contient la taille
  return p
}
</code>

==== La pile est-elle vide ? ====

Il suffit de lire l'information sur la taille de la pile.

<code go linenums:37>
func EST_VIDE(P []int) bool {
  /* renvoie true si la pile P est vide */
  return P[N] == 0
}
</code>

On peut d'ailleurs prévoir une fonction pour lire la taille de la pile.

<code go linenums:42>
func LONGUEUR(P []int) int {
  /* renvoie true si la pile P est vide */
  return P[N]
}
</code>

==== La pile est-elle pleine ? ====

Puisque notre pile a une taille maximale, on veut pouvoir tester si elle est pleine.

<code go linenums:47>
func EST_PLEINE(P []int) bool {
  /* renvoie true si la pile P est pleine */
  return P[N] == N
}
</code>

==== Empiler un élément ====

<code go linenums:52>
func EMPILER(P []int, e int) int {
  /* qui empile l'élément e sur le dessus de la pile.
     renvoie la nouvelle taille de P (après ajout de e)
     s'utilise donc ainsi P = EMPILER(P, e)
  */
  if EST_PLEINE(P) {
    // On pourrait provoquer une erreur ici.
    // Pour rester simple on se contente de ne pas modifier P
    // mais on renvoie tout de même la taille de P
    return N
  }
  var i int=P[N]
  P[i] = e
  P[N] = i + 1
  return P[N]
}
</code>

==== Dépiler un élément ====

<code go linenums:69>
func DEPILER(P []int) int {
  /* qui extrait le dernier élément de la pile et le retourne.  */
  if EST_VIDE(P) {
    // On pourrait provoquer une erreur ici.
    // Pour rester simple on se contente de ne pas modifier P
    // et de renvoyer 0
    return 0
  }
  var i int=P[N]
  P[N] = i - 1
  return P[i-1]
}
</code>

===== Fichier complet =====

Retrouvez le fichier suivant dans [[https://play.golang.org/p/EVIwN8qU89m|GoPlayground]].

<code go linenums>
package main

/*
  définition d'une pile contenant des entiers int
*/

import "fmt"

const N = 1000;

func main(){
    p:= CREER_PILE_VIDE()
    fmt.Println("Pile vide, taille : ", LONGUEUR(p))
    EMPILER(p, 45);
    fmt.Println("Empilement de 45 -> taille : ", LONGUEUR(p))
    EMPILER(p, 17);
    fmt.Println("Empilement de 17 -> taille : ", LONGUEUR(p))
    EMPILER(p, 19);
    fmt.Println("Empilement de 19 -> taille : ", LONGUEUR(p))
    EMPILER(p, 50);
    fmt.Println("Empilement de 50 -> taille : ", LONGUEUR(p))
    x := DEPILER(p);
    fmt.Println("Élément poppé : ", x)
    fmt.Println("Taille pile : ", LONGUEUR(p))
    x = DEPILER(p);
    fmt.Println("Élément poppé : ", x)
    fmt.Println("Taille pile : ", LONGUEUR(p))
}

func CREER_PILE_VIDE() []int{
  /* retourne une pile de contenu vide */
  var p[N+1]int // N cases pour la pile + 1 pour la taille
  p[N] = 0      // Dernière case contient la taille
  return p
}

func EST_VIDE(P []int) bool {
  /* renvoie true si la pile P est vide */
  return P[N] == 0
}

func LONGUEUR(P []int) int {
  /* renvoie true si la pile P est vide */
  return P[N]
}

func EST_PLEINE(P []int) bool {
  /* renvoie true si la pile P est pleine */
  return P[N] == N
}

func EMPILER(P []int, e int) int {
  /* qui empile l'élément e sur le dessus de la pile.
     renvoie la nouvelle taille de P (après ajout de e)
     s'utilise donc ainsi P = EMPILER(P, e)
  */
  if EST_PLEINE(P) {
    // On pourrait provoquer une erreur ici.
    // Pour rester simple on se contente de ne pas modifier P
    // mais on renvoie tout de même la taille de P
    return N
  }
  var i int=P[N]
  P[i] = e
  P[N] = i + 1
  return P[N]
}

func DEPILER(P []int) int {
  /* qui extrait le dernier élément de la pile et le retourne.  */
  if EST_VIDE(P) {
    // On pourrait provoquer une erreur ici.
    // Pour rester simple on se contente de ne pas modifier P
    // et de renvoyer 0
    return 0
  }
  var i int=P[N]
  P[N] = i - 1
  return P[i-1]
}
</code>