Advertisements

Une pile est un type de données abstrait (ADT), couramment utilisé dans la plupart des langages de programmation. Il est nommé pile car il se comporte comme une pile du monde réel, par exemple-un jeu de cartes ou une pile d’assiettes, etc.

Une pile du monde réel permet des opérations à une extrémité seulement. Par exemple, nous pouvons placer ou retirer une carte ou une plaque du haut de la pile uniquement., De même, Stack ADT permet toutes les opérations de données à une extrémité seulement. À un moment donné, nous ne pouvons accéder qu’à l’élément supérieur d’une pile.

Cette fonctionnalité en fait une structure de données LIFO. LIFO signifie dernier entré, premier sorti. Ici, l’élément qui est placé (inséré ou ajouté) en dernier est accessible en premier. Dans la terminologie de la pile, l’opération d’insertion est appelée opération PUSH et l’opération de retrait est appelée opération POP.,

représentation de la pile

Le diagramme suivant représente une pile et ses opérations −

Une pile peut être implémentée au moyen d’un tableau, D’une Structure, D’un pointeur et d’une liste chaînée. La pile peut être de taille fixe ou avoir un sens de redimensionnement dynamique. Ici, nous allons implémenter la pile à l’aide de tableaux, ce qui en fait une implémentation de pile de taille fixe.

opérations de base

Les opérations de pile peuvent impliquer l’initialisation de la pile, son utilisation puis sa dé-initialisation., En dehors de ces éléments de base, une pile est utilisée pour les deux opérations principales suivantes-

  • push() − pousser (stocker) un élément sur la pile.

  • pop() − suppression (accès) d’un élément de la pile.

lorsque les données sont poussées sur la pile.

pour utiliser une pile efficacement, nous devons également vérifier l’état de la pile. Dans le même but, la fonctionnalité suivante est ajoutée à stacks −

  • peek() − récupère l’élément de données Supérieur de la pile, sans le supprimer.

  • isFull() − vérifiez si la pile est pleine.,

  • isEmpty() − vérifiez si la pile est vide.

à tout moment, nous maintenons un pointeur vers les dernières données poussées sur la pile. Que ce pointeur représente toujours le haut de la pile, donc nommée haut. Le pointeur supérieur fournit la valeur supérieure de la pile sans les supprimer il., support de la pile des fonctions −

peek()

l’Algorithme de peek() la fonction

begin procedure peek return stackend procedure

la mise en Œuvre de peek() fonction dans le langage de programmation C −

Exemple

int peek() { return stack;}

isfull()

l’Algorithme de isfull() la fonction

begin procedure isfull if top equals to MAXSIZE return true else return false endif end procedure

la mise en Œuvre de isfull() fonction dans le langage de programmation C −

Exemple

bool isfull() { if(top == MAXSIZE) return true; else return false;}

isempty()

l’Algorithme de la fonction d’isempty () −

begin procedure isempty if top less than 1 return true else return false endif end procedure

la mise en Œuvre de la fonction isempty() fonction en langage de programmation C est légèrement différente., Nous initialisons top à -1, car l’index dans le tableau commence à partir de 0. Nous vérifions donc si le haut est en dessous de zéro ou -1 pour déterminer si la pile est vide. Voici le code –

exemple

bool isempty() { if(top == -1) return true; else return false;}

opération Push

le processus de mise en pile d’un nouvel élément de données est connu sous le nom D’opération Push. Opération Push implique une série d’étapes −

  • Etape 1 − Vérifie si la pile est pleine.

  • Étape 2 − Si la pile est pleine, produit une erreur et de sortie.

  • Étape 3 − si la pile n’est pas pleine, incrémente le haut pour pointer l’espace vide suivant.,

  • Étape 4 − ajoute l’élément de données à l’emplacement de la pile, où top pointe.

  • Étape 5 − renvoie le succès.

Si la liste chaînée est utilisée pour implémenter la pile, alors à l’étape 3, nous devons allouer de l’espace dynamiquement.

algorithme pour L’opération PUSH

un algorithme simple pour L’opération Push peut être dérivé comme suit −

begin procedure push: stack, data if stack is full return null endif top ← top + 1 stack ← dataend procedure

L’implémentation de cet algorithme en C est très facile., Voir le code suivant –

exemple

void push(int data) { if(!isFull()) { top = top + 1; stack = data; } else { printf("Could not insert data, Stack is full.\n"); }}

opération Pop

L’accès au contenu tout en le supprimant de la pile, est connu comme une opération Pop. Dans une implémentation de tableau de l’opération pop (), l’élément de données n’est pas réellement supprimé, mais top est décrémenté à une position inférieure dans la pile pour pointer vers la valeur suivante. Mais dans l’implémentation de liste liée, pop () supprime en fait l’élément de données et désalloue l’espace mémoire.

Une opération Pop peut impliquer les étapes suivantes −

  • Étape 1 − vérifie si la pile est vide.,

  • Étape 2 − Si la pile est vide, produit une erreur et de sortie.

  • Étape 3 − si la pile n’est pas vide, accède à l’élément de données sur lequel pointe top.

  • Etape 4 − Diminue la valeur de haut par 1.

  • Étape 5 − renvoie le succès.,

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack if stack is empty return null endif data ← stack top ← top - 1 return dataend procedure

Implementation of this algorithm in C, is as follows −

Example

int pop(int data) { if(!isempty()) { data = stack; top = top - 1; return data; } else { printf("Could not retrieve data, Stack is empty.\n"); }}

For a complete stack program in C programming language, please click here.

Advertisements