Structure de données et algorithmes - Pile

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 les opérations à une seule extrémité. Par exemple, nous pouvons placer ou retirer une carte ou une plaque du haut de la pile uniquement. De même, Stack ADT autorise toutes les opérations de données à une seule extrémité. À tout moment, nous ne pouvons accéder qu'à l'élément supérieur d'une pile.

Cette caractéristique en fait une structure de données LIFO. LIFO est l'acronyme de Last-in-first-out. Ici, on accède en premier à l'élément placé (inséré ou ajouté) en dernier. Dans la terminologie de la pile, l'opération d'insertion est appeléePUSH l'opération et l'opération de suppression est appelée POP opération.

Représentation de la pile

Le diagramme suivant illustre une pile et ses opérations -

Une pile peut être implémentée au moyen de Array, Structure, Pointer et Linked List. 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ésinitialisation. 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) à un élément de la pile.

Lorsque les données sont PUSHED sur la pile.

Pour utiliser efficacement une pile, nous devons également vérifier l'état de la pile. Dans le même but, la fonctionnalité suivante est ajoutée aux piles -

  • peek() - récupère l'élément de données supérieur de la pile, sans le supprimer.

  • isFull() - vérifier si la pile est pleine.

  • isEmpty() - vérifier si la pile est vide.

À tout moment, nous maintenons un pointeur vers les dernières données PUSHed de la pile. Comme ce pointeur représente toujours le haut de la pile, donc nommétop. letop pointer fournit la valeur supérieure de la pile sans la supprimer.

Nous devons d'abord en apprendre davantage sur les procédures de prise en charge des fonctions de pile -

coup d'oeil ()

Algorithme de la fonction peek () -

begin procedure peek
   return stack[top]
end procedure

Implémentation de la fonction peek () en langage de programmation C -

Example

int peek() {
   return stack[top];
}

est rempli()

Algorithme de la fonction isfull () -

begin procedure isfull

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

Implémentation de la fonction isfull () en langage de programmation C -

Example

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

est vide()

Algorithme de la fonction isempty () -

begin procedure isempty

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

L'implémentation de la fonction isempty () dans le langage de programmation C est légèrement différente. Nous initialisons top à -1, car l'index du tableau commence à 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 -

Example

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 appelé opération Push. L'opération de poussée implique une série d'étapes -

  • Step 1 - Vérifie si la pile est pleine.

  • Step 2 - Si la pile est pleine, produit une erreur et quitte.

  • Step 3 - Si la pile n'est pas pleine, incrémente top pour pointer le prochain espace vide.

  • Step 4 - Ajoute un élément de données à l'emplacement de la pile, où le haut pointe.

  • Step 5 - Renvoie le succès.

Si la liste liée est utilisée pour implémenter la pile, à l'étape 3, nous devons allouer de l'espace de manière dynamique.

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[top] ← data

end procedure

L'implémentation de cet algorithme en C, est très simple. Voir le code suivant -

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = 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 appelé 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é, à la placetopest décrémenté à une position inférieure dans la pile pour pointer vers la valeur suivante. Mais dans l'implémentation de liste chaînée, pop () supprime réellement l'élément de données et libère l'espace mémoire.

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

  • Step 1 - Vérifie si la pile est vide.

  • Step 2 - Si la pile est vide, produit une erreur et quitte.

  • Step 3 - Si la pile n'est pas vide, accède à l'élément de données auquel top pointe.

  • Step 4 - Diminue la valeur de top de 1.

  • Step 5 - Renvoie le succès.

Algorithme pour l'opération Pop

Un algorithme simple pour l'opération Pop peut être dérivé comme suit -

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

La mise en œuvre de cet algorithme en C, est la suivante -

Example

int pop(int data) {

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

Pour un programme de pile complet en langage de programmation C, veuillez cliquer ici .