Introduction
La pile est basé sur l'idée qu'on a une suite de donnée, dans lequel on ajoute un nouvel élément à la fin de cette suite de données, et lorsqu'on enlève une données, c'est toujours la dernière ayant été rajouté allant être enlevé la première. Les anglais surnomment cette technique LIFO, soit Last In First Out, soit le dernier entrée, le premier sortie !
Pile avec un tableau
Il y a deux techniques pour effectuer une pile, la première est effectué à l'aide d'une structure statique (un tableau). Elle est limité à un espace mémoire prédéfinit mais est très rapide. On utilise cette algorithme pour la pile des microprocesseur.
Soit «t» est la position des éléments dans la pile, la variable «N» indique le nombre maximum d'éléments dans la pile et la variable «S» représente le tableau de la pile. Voici son algorithme :
|
MODULE taille RETOURNER t + 1 MODULE estVide RETOURNER t < 0 MODULE haut SI estVide ALORS ERREUR "La pile est vide" FIN SI RETOURNER S[t] MODULE empile(objet) SI taille = N ALORS ERREUR "Débordement de la pile" FIN SI t ← t + 1 S[t] ← objet MODULE depiler(objet) SI estVide ALORS ERREUR "La pile est vide" FIN SI e ← S[t] S[t] ← NIL t ← t - 1 RETOURNER e |
Exemple
L'exemple suivant, écrit en langage de programmation C, permet de créer une pile de nombre entier avec un tableau :
Essayer maintenant !
- #include <stdio.h>
- #include <string.h>
-
- #define N 25
-
- int S[N];
- int t = 0;
-
- int isEmpty() {
- return t = 0;
- }
-
- int top() {
- if(isEmpty()) {
- puts("La pile est vide");
- exit(255);
- }
- return S[t];
- }
-
- void push(int item) {
- if(t == N) {
- puts("Débordement de la pile");
- exit(255);
- }
- S[t] = item;
- t++;
- }
-
- int pop() {
- t--;
- return S[t];
- }
-
- int main(void) {
- push(1);
- push(2);
- push(3);
- printf("Depile A : %i\n",pop());
- printf("Depile B : %i\n",pop());
- printf("Depile C : %i\n",pop());
- }
on obtiendra le résultat suivant :
Depile A : 3Depile B : 2
Depile C : 1
Pile avec une liste chaîné simple
La seconde technique consiste à utiliser une liste chainé simple. Ainsi, chaque nouvelle élément sera ajouté dans la mémoire dynamique. Bien que les performances soit moins rapide, elle est de loin préférable à la première technique car elle offre un nombre illimité d'élément dans le tableau. On utilise cette technique dans les piles intégré aux langages de programmation. Voici son algorithme :
|
MODULE taille RETOURNER t + 1 MODULE estVide RETOURNER t < 0 MODULE haut SI estVide ALORS ERREUR "La pile est vide" FIN SI RETOURNER haut.element MODULE empile(objet) n ← nouveau Noeud n.element ← objet n.prochainNoeud(haut) haut ← n t ← t + 1 MODULE depiler(objet) SI estVide ALORS ERREUR "La pile est vide" FIN SI e ← haut.element haut ← haut.demandeProchain() t ← t - 1 RETOURNER e |