Bonsoir tout le monde,
 
C'est mon premier message, et j'ai un petit souci j'aimerais que quelqu'un m'explique le fonctionnement des piles et files d'attentes,  
 
ou en gros m'expliquer ce que veut dire ce petit programme parceque je ne comprends pas trop ..  
 
 
é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<- allouer élèment_liste  
p-> données <- val  
p-> lien <- pile  
pile <- p  
 
}
 
 
Pourriez vous donc m'expliquer simplement le mécanisme
(je comprends ce que ça veut dire pointeur)
 
Merci D'avance..

C'est un peu vague comme question, le problème c'est le fonctionnement des piles et files ou leur implémentation

Commençons par le début du commencement,  
 
le fonctionnement des piles et files .. stp ..

Piles et files sont deux types de conteneurs permettant de stocker des données (potentiellement quelconques, après ça dépend de l'implémentation).
 
Une pile (Stack, en anglais) c'est exactement ce que tu peux te représenter en pensant à une pile d'objets (de feuilles de papier par exemple):

 
Une pile est créée vide, quand on ajoute un objet à une pile il se place "sur le dessus" (conceptuellement), donc quand on enlève un objet de la pile on enlève le dernier objet ajouté (Last In, First Out, le dernier arrivé part en premier)
 
Une file (Queue en anglais), ça correspond à une file d'attente (à un gichet de la poste si ton ordinateur est très lent):
(désolé j'ai pas de joli dessin)
 
Une file est créée vide, quand on ajoute un objet à une file il se met "en premier", et les suivants sont ajoutés "derrière". Donc quand on enlève un objet de la file, on enlève le premier objet ajouté, celui qui est en tête de file (First In First Out, le premier arrivé est le premier à partir)

Je vois, c'est bien expliqué .. merci ..
 
Donc maintenant tu peux m'expliquer stp l'enchainement du programme (ce que j'ai marqué comme explication est ce correct ? stp ?)  
 
Merci encore..

J'imaginais quelque chose de plus olé olé    
Tu empiles des pointeurs qui pointe sur la pile
Si la donnée est un entier ta pile pourrait ressebler a ca :
 
p->5          |
p->la pile    |
                | la pile
p->3          |  
p->la pile    |
                |
....            |

Pour une pile

• On commence par construire une structure "pile", qui contient simplement un pointeur (nul initialement) qui va représenter le dessus de la pile ("top" )
• À chaque ajout à la pile, one crée une "node". Une node est une structure très simple: un pointeur vers une donnée (ou la donnée directement si c'est un entier par exemple) et un pointeur vers l'élément suivant ("next" ). On fait pointer "next" sur le "top" courant de la pile, puis on fait pointer "top" sur la node qu'on vient de créer.
• Quand on veut enlever un élément de la pile, il faut d'abord vérifier s'il y a un élément dedans (donc si "top" n'est pas nul), s'il n'y a pas d'élément on génère une erreur, s'il y a un élément

   => on stocke la valeur contenue dans "top" dans une variable temporaire
    => on template "top" par "top.next" (on place la node suivante en tête de pile)
    => on détruit l'ancien top (donc il faut le conserver dans un coin)
    => on renvoie la valeur stockée initialement
 
http://fr.wikipedia.org/wiki/Pile_%28informatique%29
http://en.wikipedia.org/wiki/Stack [...] ructure%29

Oki Je vois carrèment mieux là ..  
 
Merci beaucoup ..  
 
 
2ème question:  
 
Peux tu maintenant m'expliquer s'il te plait le principe de la file d'attente tout ce que je sais c'est  
Insertion in de la file  
Supression au début (comme tu l'a dis d'ailleurs ..
 
Merci

Pour une file:
 

• On commence par créer une structure FILE, on va commencer par créer une FILE simple, insertion en O(n) et extraction en O(1), donc notre structure a là encore un unique pointeur (initialement nul) qu'on va appeler "head"
• On utilise la même structure node que précédement
• Le retrait d'un élément de la pile est le même que pour la pile (sauf qu'on utilise un pointeur "head" au lieu de "top", c'est la seule différence)
• Par contre pour ajouter un élément à la file, il faut l'ajouter tout à la fin de la file, donc:

   => On créer un nouveau pointeur sur la premier node (head)
    => Tant qu'il y a une node suivante (node.next != null) on va à la node suivante
    => Quand on arrive à la queue de la file (la node avec node.next == null), on crée une nouvelle node "newNode" avec "next" à "null" et la valeur à ajouter à la file
    => On donne au "next" de la node actuelle (pas newNode, l'autre) la valeur du pointeur sur newNode
 
Done.  
 
Par contre comme tu le remarques on doit parcourir toute la liste pour y ajouter un élément, ce qui peut être très coûteux. Ce n'est pas nécessairement grave pour des exercices scolaires, mais si on a besoin d'un peu plus de performances une optimisation possible, c'est d'ajouter à la structure "file" un second pointeur "tail" sur le dernier élément de la liste. De cette manière, on peut sauter tout l'étape 2 de l'ajout de node en se plaçant sur la node sur laquelle pointe "tail". Par contre il faut penser à modifier "tail" (pour pointer sur newNode) quand on a fini, sinon ça ne sert à rien.

Parfait !
 
C'est clair ..  
 
Merci beaucoup !