Go accepte des tableaux de taille variable, les 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.
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
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.
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.
Nous allons reprendre ici une 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.
On commence par définir la taille maximale de la pile. On utilise pour cela une constante.
const N = 1000
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
}
Il suffit de lire l'information sur la taille de la pile.
func EST_VIDE(P []int) bool {
/* renvoie true si la pile P est vide */
return P[N] == 0
}
On peut d'ailleurs prévoir une fonction pour lire la taille de la pile.
func LONGUEUR(P []int) int {
/* renvoie true si la pile P est vide */
return P[N]
}
Puisque notre pile a une taille maximale, on veut pouvoir tester si elle est pleine.
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]
}
Retrouvez le fichier suivant dans GoPlayground.
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]
}