Structures de données
Piles
Pr. Issam QAFFOU
Laboratoire Ingénierie des Systèmes Informatique
Département d’Informatique
FSSM-UCA
Principe
• C’est une variante d’une liste chainée.
• C’est une structure de données dont toutes les opérations
s’effectuent à partir d’un seul lieu (extrémité) qu’on appelle
"sommet" de la pile.
• Une pile suit le principe ‘dernier arrivé, premier servi’, qu’on
appelle en anglais ‘Last In First Out’.
• On peut l’assimiler au principe de se servir des assiettes.
Piles 2
Principe
In
C B A
Sommet de la
pile
Pile (LIFO)
Piles 3 / 20
Principe
C
Sommet de la
pile B
Pile (LIFO)
Piles 4 / 20
Principe
Out
C
Sommet de la
pile B
Pile (LIFO)
Piles 5 / 20
Principe
Out
B C
Sommet de la
pile
Pile (LIFO)
Piles 6 / 20
Principe
• L’insertion ou la suppression se font à partir du sommet de la
pile.
• Pour pouvoir insérer un élément dans la pile, il doit y avoir de
l’espace (elle ne doit pas être pleine).
• Pour retirer un élément de la pile, elle ne doit pas être vide.
• Les opérations principales sur les piles sont alors:
– La création
– Tester si une pile est vide
– Tester si une pile est pleine.
– L’insertion
– La suppression
– L’affichage du contenu
Piles 7
Représentation d’une pile
• Deux manières pour représenter une pile, en utilisant
une:
– Représentation contigue (Tableaux)
• Déclarer un tableau d’une taille fixe (qui détermine la taille
maximale de la pile).
• Maintenir une variable qui pointe toujours sur la tête de la pile.
– Représentation chainée (Pointeurs)
• Simuler une pile à une liste chainée.
• Une variable pointeur top pointant sur le début de la liste.
• Le premier élément de la liste chainée est considéré comme la tête
de la pile.
Piles 8 / 20
Pile en utilisant des tableaux
EMPILER
top
Piles 9 / 20
Pile en utilisant des tableaux
EMPILER
top
Piles 10 / 20
Pile en utilisant des tableaux
DEPILER
top
Piles 11 / 20
Pile en utilisant des tableaux
DEPILER
top
Piles 12 / 20
Pile en utilisant liste chainée
EMPILER
top
Piles 13 / 20
Pile en utilisant liste chainée
DEPILER
top
Piles 14 / 20
Piles: Fonctions principales
(en langage C)
Soit p une pile d’entiers, les prototypes des
fonctions principales pour implementer une pile
sont:
void creer (pile *p);
/* Créer une nouvelle pile*/
int estVide (pile *p);
/* Vérifier si la pile est vide*/
int estPlein(pile *p);
/* Vérifier si la pile est pleine */
void empiler(pile *p, int element);
/* Insérer un élément dans la pile */
int depiler(pile *p);
/* enlever un élément de la pile */
Piles 15 / 20
Implémentation des Piles
(avec Tableau)
Déclaration
Définition de la structure correspondante
#define MAXSIZE 100
struct lifo{
int st[MAXSIZE];
int top;
};
typedef struct lifo pile;
Piles 17 / 20
Création de la Pile
void creer (pile *s){
s->top = -1;
/* s->top pointe sur le
dernier élément empilé;
initialisé à -1 */
}
Piles 18 / 20
Fonction empiler
void empiler(pile *s, int element){
if (s->top == (MAXSIZE-1)){
printf (“\n débordement ”);
EXIT_FAILURE;
}
else s->st[++s->top] = element;
}
Piles 19 / 20
Dépiler un élément de la pile
int depiler(pile *s){
if (s->top == -1){
printf (“\n Rien à dépiler”);
EXIT_FAILURE;
}
else return (s->st[s->top--]);
}
Piles 20 / 20
Fonction estVide
int estVide(pile *s){
if (s->top == -1)
return 1;
else
return 0;
}
Piles 21 / 20
Fonction estPlein
int estPlein(pile *s){
if (s->top == MAXSIZE–1))
return 1;
else
return 0;
}
Piles 22 / 20
Fonction d’affichage
void afficher(pile *p){
if(estVide(p)){
printf("Pile vide!");
EXIT_FAILURE;
}
int i;
for(i=0;i<p->top+1;i++)
printf("%d ",p->st[i]);
printf("\n");
}
Piles 23 / 20
Tester dans le main()
int main()
{
pile A;
creer(&A);
empiler(&A,10);
empiler(&A,20);
empiler(&A,30);
afficher(&A);
depiler(&A);
depiler(&A);
depiler(&A);
afficher(&A);
return 0;
}
Piles 24 / 20
Implémentation des Piles
(avec Liste chainée)
Déclaration
Définition de la structure
struct lifo{
int val;
struct lifo *next;
};
typedef struct lifo pile;
Piles 26 / 20
Création de la Pile
void creer (pile **top){
*top = NULL;
/* top pointe sur NULL, en
indiquant une pile vide */
}
Piles 27 / 20
Fonction empiler
void empiler (pile **top, int element){
pile *new;
new = (pile*) malloc(sizeof(pile));
if (new == NULL){
printf (“\n Pile est pleine”);
EXIT_FAILURE;
}
new->val = element;
new->next = *top;
*top = new;
}
Piles 28 / 20
int depiler(pile **top){
int t; // Pour la valeur dépilée
pile *p;
if (*top == NULL){
printf (“\n pile vide”);
EXIT_FAILURE;
}
else {
t = (*top)->val;
p = *top;
*top = (*top)->next;
free (p);
return t;
}
}
Piles 29 / 20
Fonction estVide
int estVide(pile *top){
if (top == NULL)
return (1);
else
return (0);
}
Piles 30 / 20
Fonction estPlein
• N’est pas obligatoire aves les listes chainées
• Dans la fonction depiler(), on peut vérifier la
valeur retournée de malloc().
– Si -1, allors la mémoire ne pourra pas
être allouée.
Piles 31 / 20
Fonction d’affichage
void afficher(pile *top){
if (estVide(top)==1) {
printf(“Pile vide. Rien a afficher\n");
EXIT_FAILURE;
}
while (top != NULL) {
printf ("%d ", top->val);
top = top->next;
}
}
Piles 32 / 20
Tester dans le main()
int main()
{
pile *A;creer(&A);
afficher(A); empiler(&A,10);
empiler(&A,20);
empiler(&A,30);
printf("Les valeurs empilees: ");
afficher(A);
depiler(&A);
printf("\nApres depilement: ");
afficher(A);
return 0;
}
Piles 33 / 20
FIN des Piles
Piles 34
Structures de données
SMI/SMA-S4
Files
Pr. Issam QAFFOU
Laboratoire Ingénierie des Systèmes Informatique
Département d’Informatique
FSSM-UCA
Principe
• Une file est une variante des structures de
données linéraires.
• Une file est une collection d’éléments de
même type.
• Une file est repérée par une tête et une
queue.
• Les éléments sont insérés (on dit enfilés)
par la queue et supprimés (on dit défilés)
par la tête.
• Aucune opération ne peut être effectuée du
milieu de la file. Les éléments du milieu sont
logiquement inaccessibles.
• Imaginer une file d’attente devant un
guichet.
File 36
Liste FIFO: First In First Out
In Out
C B A
FILE
Queue Tête
Enfiler
File 37
Liste FIFO: First In First Out
In Out
C B A
FILE
Queue Défiler Tête
File 38
Les files: First-In-First-Out
Les opérations à effectuer sur une file
Soit q une file dont les éléments sont des valeurs entières.
void enfiler (file *q, int element);
/* Insérer un élément dans une file */
int defiler (file *q);
/* Supprime un élément de la file */
file *creer();
/* Créer une nouvelle file */
int estVide (file *q);
/* Vérifie si la file est vide*/
int estPleine (file *q);
/* Retourne le nombre d’éléments dans la file */
File 39
Les files: First-In-First-Out
• Une file peut être représentée par deux
approches
– Approche « tableau » :
• Les éléments de la file sont stockés dans un tableau
• La tête et la queue sont référencés par deux entiers
– Approche « chaînée » :
• Les éléments sont chaînés par des pointeurs
• La tête et la queue sont représentées par deux pointeurs
• On utilise deux structures; une pour les éléments et
l’autre pour la file.
File 40
Implémentation d’une file par
liste chainée
Idée de base
– Créer une liste chainée à laquelle les éléments sont
ajoutés d’un côté et supprimés de l’autre côté.
– On aura besoin de deux pointeurs:
• Un pointant sur la tête de la liste (d’où les éléments seront
supprimés)
• Un autre pointant sur la queue de la liste (d’où les éléments
seront insérés).
queue
Tête
Suppression Insertion
File 42
File: par liste chainée
Tête Queue
Enfiler
File 43
File: par liste chainée
Tête Queue
Défiler
File 44
Exemple
On utilise deux structures; une pour les éléments et l’autre pour
la file.
struct noeud{
int val;
struct noeud *suiv;
};
typedef struct noeud fifo;
typedef struct {
fifo *tete, *queue;
} file;
File 45
creer-estVide
void creer(file *q)
{
q->tete= q->queue=NULL;
}
int estVide(file *q)
{
if(q==NULL) return 1;
else return 0;
}
File 46
Fonction enfiler
fifo *enfiler (file *q, int n) {
fifo *temp;
temp= (fifo *)malloc(sizeof(fifo));
if (temp==NULL) {
printf("Erreur d’allocation \n");
return NULL;
}
temp->val=n;
else {
temp->suiv=NULL;
q->queue->suiv=temp;
if(q->queue==NULL) {
q->queue=temp;
q->queue = temp;
}
q->tete = q->queue;
return(q->queue);
}
}
File 47
Fonction defiler
void *defiler(file *q) {
if(q->tete==NULL) {
q->queue=NULL;
printf("File est vide!!\n");
return(NULL);
}
int n;
fifo *temp;
n=q->tete->val;
temp=q->tete; if(q->tete==NULL)
q->tete= q->tete->suiv; q->queue=NULL;
free(temp); printf("La valeur defilee: %d",n);
}
File 48
Implémentation avec Tableau
File 49
Implémentation avec Tableau
ENFILER
DEFILER
Zone de stockage effective du tableau de la file se réduit.
0 N
Tête Tête queue queue
Utilisation de l'indexation du tableau circulaire
File 50
Exemple
• Supposons une file de valeurs entières simulée par un tableau.
• Les structures:
#define MAX_SIZE 100
typedef struct {
int val;
} ELEMENT;
typedef struct {
ELEMENT f_elem[MAX_SIZE];
int queue, tete;
int plein,vide;
} file;
File 51
Fonctions: creation, estVide, estPleine
Fonction creation
void creation(file *q) {
q->queue= q->tete= 0;
q->plein=0; q->vide=1;
}
Fonction estVide Fonction estPlein
int estVide(file *q) { int estPlein(file *q){
return(q->vide); return(q->plein);
} }
File 52
Fonction enfiler
void enfiler(file *q, ELEMENT ob){
if(estPlein(q)) {
printf("File est pleine \n");
EXIT_FAILURE;
}
q->queue=(q->queue+1)%(MAX_SIZE);
q->f_elem[q->queue]=ob;
if(q->tete==q->queue) q->plein=1;
else q->plein=0;
q->vide=0;
}
File 53
Fonction defiler
ELEMENT defiler(file *q){
if(estVide(q)) {
printf("File est vide\n");
EXIT_FAILURE;
}
ELEMENT temp;
q->tete=(q->tete+1)%(MAX_SIZE);
temp=q->f_elem[q->tete];
if(q->queue==q->tete) q->vide=1;
else q->vide=0;
q->plein=0;
return(temp);
}
File 54
FIN
File 55
