Scribd
Importer
6 vues13 pages

Piles et Files : Structures de Données

Le document présente les structures de données Pile et File, expliquant leur fonctionnement selon les principes LIFO et FIFO respectivement. Il décrit les opérations de base pour empiler et dépiler des éléments dans une pile, ainsi que les opérations d'insertion et de suppression dans une file. Les implémentations sont illustrées par des exemples de code utilisant des listes chaînées.

Transféré par

joseph
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
6 vues13 pages

Piles et Files : Structures de Données

Le document présente les structures de données Pile et File, expliquant leur fonctionnement selon les principes LIFO et FIFO respectivement. Il décrit les opérations de base pour empiler et dépiler des éléments dans une pile, ainsi que les opérations d'insertion et de suppression dans une file. Les implémentations sont illustrées par des exemples de code utilisant des listes chaînées.

Transféré par

joseph
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

3ème année GIIE-FID

Pile et File

Mohamed El yaakoubi
Pile
La pile est une structure de données, qui permet de stocker les données dans l'ordre LIFO (Last
In First Out) - en français Dernier Entré Premier Sorti).
La récupération des données sera faite dans l'ordre inverse de leur insertion.
Le fonctionnement est celui d'une pile d'assiettes : on ajoute des assiettes sur la pile, et on les
récupère dans l'ordre inverse, en commençant par la dernière ajoutée.
Les opérations qu’on peut faire sur une pile :
• Retourner l'élément au sommet de la pile
• Empiler un élément au sommet de la pile.
• Dépiler et délivrer l'élément au sommet de la pile p. La nouvelle pile est
aussi délivrée.
Modélisation par tableau

Généralement, il y a deux façons de représenter une pile. La première s'appuie sur la structure de
liste chaînée. La seconde manière utilise un tableau.

struct Pile {
ELEMENT tab[NMAX];
int n;
};
Modélisation par tableau

NMAX

n
n
Modélisation par liste chainée

• Pour l'implémentation, nous avons choisi une liste simplement chaînée, présentée sur la
verticale.
• L'insertion se faisant toujours au début de la liste, le 1er élément de la liste sera le dernier
élément saisi, donc sa position est en haut de la pile
• Ce qui nous intéresse c'est que le dernier élément entré, sera le 1er élément récupéré.
struct node {
int data; struct Stack{
node *next; node *top;
}; int size;
};

Empiler une donnée dans la pile

Stack *push(Stack *stack,int data)


{
node *other = new node();
other->data=data;
other->next = stack->top;
stack->top=other;
stack->size++;
return stack
}
Dépiler une donnée dans la pile

int pop(Stack *stack)


{
if(stack->top==NULL)
{
cout << "Empty stack ...." << endl;
exit(-1);
}
else {
int data;
node *tmp = stack->top;
data = tmp->data;
stack->top = tmp->next;
stack->size--;
delete(tmp);
return data;
}
}
int top(Stack *stack){
if(stack->top==NULL)
{
cout << "Empty stack ...." << endl;
exit(-1);
}
else
return stack->top->data;
}
File

La file est une structure de données, qui permet de stocker les données dans l'ordre FIFO (First
In First Out) - en français Premier Entré Premier Sorti).
Pour l'implémentation, on a choisi une liste simplement chaînée. L'insertion dans la file se fera
dans l'ordre normal, le 1er élément de la file sera le premier élément saisi, donc sa position est
au début de la file.
Pour avoir le contrôle de la file, il est préférable de sauvegarder certains éléments : le premier élément, le dernier
élément, le nombre d'éléments.

struct File{
node *first;
node *last;
};
File *push(File *file,int data){
node *other = new node();
other->data=data;
if(file->last==NULL)
{
file->first=other;
file->last=other;

}
else {
file->last->next=other;
file->last=other ;
}
return file;
}
int pop(File *file){
if(file->top==NULL)
{
cout << "enpty file ..." << endl;
exit(-1);
}
else{
int data= file->first->data;
node *tmp=file->first;
file->first=tmp->next;
if(file->first==NULL)
file->last=NULL;
delete(tmp);
return data;
}
}

Vous aimerez peut-être aussi