Pile, file d'attente

[sandrine_guillerme]

Bonsoir,

Voici un autre chapitre (simple je crois) mais j'ai du mal,

commençons par le début du commencement :

écrivons une procèdure pour empiler une valeur (?)

procedure Empiler (E val : type)
{


/*alors bon j'imagine que l'idée est la suivante: on alloue un espace de mémoire pour p (pointeur) on demande à p de pointer sur données qui à son tour on lui affecte une valeur .. et ensuite on passe à l'élèment suivant on dit à p de pointer sur lien qu'on lui demande de prendre une pile (c'est un pointeur ?) j'aimagine que c'est une variable globale ? bref, je comprends pas trop .. */
p: pointeur
p données lien <- pile
pile <- p

}

je compte sur votre aide,

Merci ..

[Dominique Lefebvre]

Bonsoir Sandrine,

Quelle type de pile? FIFO?

[sandrine_guillerme]

Bonsoir Dominique,

Beuh je sais pas,
je te dis la définition :

C'est une structure (tableau ou liste) qui permet de sauvegarder temporairement l'information, en respectant l'ordre,

on peut empiler ou dépiler les élèments,

procèdure dépiler (E/S val : type )
{
si (pile != NUL ) alors
{

val donnée
pile lien

}

sinon
afficher ("Erreur la pile est vide ")

}

Donc voilà je ne sais pas ce que sait FIFO moi, je débute encore.. !

EDIT : ensuite on me parle de la file d'attente, (liste avec pointeur à la fin pour la rapidité d'insertion)
Insertion : fin de la file
Suppression : début

(...)

Peut être touche tu mon problème maintenant ?

[Joker62]

Alors je t'explique ce qu'a voulu dire Dominique.

Tu as le type de pile FIFO : First In First Out
Premier entré Premier Sorti
En fait, on l'apelle plutôt " File " Mais bon c'est pareil :)

Après tu as le type de pile FILO : First In Last Out
Premier entré Dernier Sorti


Donc voilà un exemple de Pile :)

Structure Element
{
Valeur : Type
pSuivant : Pointeur_Element //Pointeur sur l'élément suivant
};

Structure Pile
{
pFirst : Pointeur_Element //Pointeur sur le premier élément
pCurrent : Pointeur_Element; //Pointeur sur l'élément courant
};

Procedure Init ( p : Pointeur_Pile )
{
p -> pFirst = NULL;
p -> pCurrent = NULL;
}

Fonction EstVide ( p : Pointeur_Pile ) : boolean
{
Si (p -> pFirst == NULL)
Alors retourner VRAI
Sinon retourner FAUX
}

Fonction Push ( p : Pointeur_Pile ; Val : Pointeur_Element );
{
//C'est la fonction empiler ici : on rajoute un élément dans la boite...

SI Est Vide( p ) == VRAIE

Alors //Si la pile est vide
{
p -> pFirst = Val; //Alors le premier et le courant c'est la même chose
p -> pCurrent = Val;
}
Sinon
{
//Sinon, le suivant après le dernier element c'est Val
p -> pCurrent -> pSuivant = Val;
// Et on avance le pointeur Current sur le dernier.
p -> pCurrent = p -> pCurrent -> pSuivant;
}
}

Fonction : Pop ( p : Pointeur_Pile )
{
//La fonction qui enlève un élément
//On doit enlever le dernier élément
//On récupère l'avant dernier, et on supprime le dernier

Temp : Pointeur

Temp = p -> pFirst;

//Ici on avance jusque l'avant dernier
Tant que ( Temp -> pSuivant différent de p->pCurrent )
Temp = Temp -> pSuivant;

Free ( Temp -> pSuivant ); //On libère la mémoire du dernier
TEmp -> pSuivant = NULL; // et voilà
}

Voilà un joli exemple complet de pile :)
Enfin, complet, c'est pas rigoureux...

[sandrine_guillerme]

Merci pour l'exemple mais il est assez compliqué pour moi ..

Ce que j'ai cru comprendre de la file, c'est, comme un guichet de poste ..
et de la pile ça va dans les deux sens,

pour écrire un programme :

commencons par la file ,,

Procedure insertion_element (E val : type )
{

Si (tête = NUL) alors
{
insert_debut(tête,val) /*oui puisq'une file est caractérisée par tête et la queue me semble t il queue et tête sont deux pointeurs*/

queue lien, val )
queue lien

}

[Joker62]

Ouai voilà la file c'est la queue de la poste
et la pile, c'est la tour de cd :D

[sandrine_guillerme]

>Tout à fait ! :id:

Mais bon c'est vieux comme le monde ça, j'ai l'impression de devenir moins ringarde ..


J'attaque maintenant la réccursivité, (si tu veux savoir, je fais un survol sur le cours, et ensuite j'attaque les Tds, si tu as des idées à propos de la réccursivité je suis preuneuse, sois juste patient, je créerais taleur un post à propos;

Merci pour ton audace, c'est pas facile, je sais .. :girl2:

[Joker62]

Ben la récursivité, on commence toujours par la factorielle :D

[sandrine_guillerme]

Ben la récursivité, on commence toujours par la factorielle

Oui Oui en effet ..