Structure des données de la pile est un structure de données linéaire ce qui suit Principe LIFO (dernier entré, premier sorti) , donc le dernier élément inséré est le premier à être retiré. Dans cet article, nous couvrirons toutes les bases de Stack, les opérations sur Stack, sa mise en œuvre, ses avantages, ses inconvénients qui vous aideront à résoudre tous les problèmes basés sur Stack.

Table des matières

• Qu'est-ce que la structure des données de la pile ?
• Opérations de base sur la structure des données de la pile
• Opération isEmpty dans la structure de données de la pile
• Implémentation de la structure de données de pile à l'aide d'une liste chaînée
• Analyse de la complexité des opérations sur la structure de données de la pile
• Avantages de la structure de données de pile
• Inconvénients de la structure de données de la pile
• Applications de la structure de données de pile

Qu'est-ce que la structure des données de la pile ?

Empiler est un structure de données linéaire basé sur Principe LIFO (Last In First Out) dans lequel l'insertion d'un nouvel élément et la suppression d'un élément existant ont lieu à la même extrémité représentée que le haut de la pile.

Pour implémenter la pile, il est nécessaire de maintenir le pointeur vers le haut de la pile , qui est le dernier élément à insérer car nous ne pouvons accéder aux éléments qu'en haut de la pile.

Représentation de la structure des données de la pile :

Stack suit le principe LIFO (Last In First Out), de sorte que l'élément poussé en dernier est affiché en premier.

Pile de taille fixe : Comme son nom l'indique, une pile de taille fixe a une taille fixe et ne peut pas croître ou diminuer de manière dynamique. Si la pile est pleine et que l'on tente d'y ajouter un élément, une erreur de débordement se produit. Si la pile est vide et qu'une tentative est faite pour en supprimer un élément, une erreur de dépassement inférieur se produit.

Pile de taille dynamique : Une pile de taille dynamique peut croître ou diminuer dynamiquement. Lorsque la pile est pleine, elle augmente automatiquement sa taille pour accueillir le nouvel élément, et lorsque la pile est vide, elle diminue sa taille. Ce type de pile est implémenté à l'aide d'une liste chaînée, car elle permet un redimensionnement facile de la pile.

Opérations de base sur la pile Structure de données :

Afin d'effectuer des manipulations dans une pile, certaines opérations nous sont proposées.

synchronisation des threads

• pousser() pour insérer un élément dans la pile
• populaire() pour supprimer un élément de la pile
• haut() Renvoie l'élément supérieur de la pile.
• est vide() renvoie vrai si la pile est vide sinon faux.
• est rempli() renvoie vrai si la pile est pleine sinon faux.

Condition de débordement.

Algorithme pour l'opération Push :

• Avant de pousser l'élément vers la pile, nous vérifions si la pile est complet .
• Si la pile est pleine (en haut == capacité-1) , alors Débordements de pile et nous ne pouvons pas insérer l'élément dans la pile.
• Sinon, on incrémente la valeur de top de 1 (haut = haut + 1) et la nouvelle valeur est insérée à première position .
• Les éléments peuvent être poussés dans la pile jusqu'à ce que nous atteignions le capacité de la pile.

Condition de sous-versement.

Algorithme pour l'opération Pop :

• Avant de retirer l'élément de la pile, nous vérifions si la pile est vide .
• Si la pile est vide (top == -1), alors Débits inférieurs à la pile et nous ne pouvons supprimer aucun élément de la pile.
• Sinon, on stocke la valeur en haut, on décrémente la valeur de top de 1 (haut = haut – 1) et renvoie la valeur supérieure stockée.

Algorithme pour le fonctionnement supérieur :

• Avant de renvoyer l'élément supérieur de la pile, nous vérifions si la pile est vide.
• Si la pile est vide (top == -1), nous affichons simplement La pile est vide.
• Sinon, nous renvoyons l'élément stocké dans indice = haut .

Algorithme pour l'opération isEmpty :

• Vérifiez la valeur de haut en pile.
• Si (en haut == -1) , alors la pile est vide alors reviens vrai .
• Sinon, la pile n'est pas vide donc retournez FAUX .

Algorithme pour l’opération isFull :

• Vérifiez la valeur de haut en pile.
• Si (en haut == capacité-1), alors la pile est complet alors reviens vrai .
• Sinon, la pile n'est pas pleine alors retournez FAUX .

Implémentation de la pile Structure de données :

Les opérations de base pouvant être effectuées sur une pile incluent le push, le pop et le peek. Il existe deux manières d'implémenter une pile :

• Utiliser un tableau
• Utiliser la liste chaînée

Dans une implémentation basée sur un tableau, l'opération push est implémentée en incrémentant l'index de l'élément supérieur et en stockant le nouvel élément à cet index. L'opération pop est implémentée en renvoyant la valeur stockée à l'index supérieur, puis en décrémentant l'index de l'élément supérieur.

Dans une implémentation basée sur une liste chaînée, l'opération push est implémentée en créant un nouveau nœud avec le nouvel élément et en définissant le pointeur suivant du nœud supérieur actuel sur le nouveau nœud. L'opération pop est implémentée en définissant le pointeur suivant du nœud supérieur actuel sur le nœud suivant et en renvoyant la valeur du nœud supérieur actuel.

/* Programme C++ pour implémenter la pile de base opérations */ #inclure #inclure en utilisant espace de noms norme; #définir MAX 1000 classe Empiler { int haut; publique: int un[MAXIMUM]; // Taille maximale de la pile Empiler() { haut = -1; } bouffon pousser(int X); int populaire(); int coup d'oeil(); bouffon est vide(); } ; bouffon Pile :: pousser(int X) { si (haut >= (MAXIMUM - 1)) { cout << 'stack=''débordement'<='' span=''>; retour FAUX; } autre { un[++haut] = X; cout << X << ' poussé dans la pile '; retour vrai; } } int Pile ::pop() { si (haut < 0) { cout << « Sous-débit de pile »; retour 0; } autre { int X = un[haut--]; retour X; } } int Pile ::coup d'oeil() { si (haut < 0) { cout << 'La pile est vide'; retour 0; } autre { int X = un[haut]; retour X; } } bouffon Stack ::isEmpty() { retour (haut < 0); } // Programme pilote pour tester les fonctions ci-dessus int principal() { classe Empiler s; s.pousser(dix); s.pousser(vingt); s.pousser(30); cout << s.populaire() << ' Sorti de la pile '; //imprimer l'élément supérieur de la pile après l'avoir éclaté cout << 'L'élément supérieur est : ' << s.coup d'oeil() << fin; //imprimer tous les éléments de la pile : cout <<'Éléments présents dans la pile : '; alors que(!s.est vide()) { // affiche l'élément supérieur de la pile cout << s.coup d'oeil() <<' '; // supprime l'élément supérieur de la pile s.populaire(); } retour 0; } //Le code est modifié par Vinay PandeyC

// C program for array implementation of stack #include  #include  #include  // A structure to represent a stack struct Stack {  int top;  unsigned capacity;  int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) {  struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));  stack->capacité = capacité ;  pile->top = -1 ;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  pile de retour ; } // La pile est pleine lorsque top est égal au dernier index int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // La pile est vide lorsque top est égal à -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Fonction pour ajouter un élément à empiler. Il augmente le haut de 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  pile->array[++stack->top] = élément;  printf('%d poussé vers la pile
', item); } // Fonction pour supprimer un élément de la pile. Il diminue le haut de 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Fonction pour renvoyer le haut de la pile sans le supprimer int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Programme pilote pour tester les fonctions ci-dessus int main() { struct Stack* stack = createStack(100);  pousser (pile, 10);  pousser (pile, 20);  pousser (pile, 30);  printf('%d sorti de la pile
', pop(pile));  renvoie 0 ; }>

Java

/* Java program to implement basic stack operations */ class Stack {  static final int MAX = 1000;  int top;  int a[] = new int[MAX]; // Maximum size of Stack  boolean isEmpty()  {  return (top < 0);  }  Stack()  {  top = -1;  }  boolean push(int x)  {  if (top>= (MAX - 1)) { System.out.println('Débordement de pile');  retourner faux ;  } autre { a[++top] = x;  System.out.println(x + ' poussé dans la pile');  renvoie vrai ;  } } int pop() { if (haut< 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top--];  return x;  }  }  int peek()  {  if (top < 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top];  return x;  }  }    void print(){  for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]);  } } } // Classe de code du pilote Main { public static void main(String args[]) { Stack s = new Stack();  s.push(10);  s.push(20);  s.push(30);  System.out.println(s.pop() + 'Supprimé de la pile');  System.out.println('L'élément supérieur est :' + s.peek());  System.out.print('Éléments présents dans la pile :');  sprint();  } } //Ce code est modifié par Vinay Pandey>

Python

# Python program for implementation of stack # import maxsize from sys module  # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions  stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>

C#

// C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack {  private int[] ele;  private int top;  private int max;  public Stack(int size)  {  ele = new int[size]; // Maximum size of Stack  top = -1;  max = size;  }  public void push(int item)  {  if (top == max - 1) {  Console.WriteLine('Stack Overflow');  return;  }  else {  ele[++top] = item;  }  }  public int pop()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top--];  }  }  public int peek()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top];  }  }  public void printStack()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return;  }  else {  for (int i = 0; i <= top; i++) {  Console.WriteLine('{0} pushed into stack',  ele[i]);  }  }  } } // Driver program to test above functions class Program {  static void Main()  {  Stack p = new Stack(5);  p.push(10);  p.push(20);  p.push(30);  p.printStack();  p.pop();  } } }>

Javascript

/* javascript program to implement basic stack operations  */  var t = -1;  var MAX = 1000;  var a = Array(MAX).fill(0); // Maximum size of Stack  function isEmpty() {  return (t < 0);  }  function push(x) {  if (t>= (MAX - 1)) { console.log('Débordement de pile');  retourner faux ;  } autre { t+=1;  une[t] = x;    console.log(x + ' poussé dans la pile ');  renvoie vrai ;  } } fonction pop() { si (t< 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  t-=1;  return x;  }  }  function peek() {  if (t < 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  return x;  }  }  function print() {  for (i = t; i>-1; i--) { console.log(' ' + a[i]);  } } pousser(10);  pousser(20);  pousser(30);  console.log(pop() + 'Supprimé de la pile');  console.log(' L'élément supérieur est :' + peek());  console.log(' Éléments présents dans la pile : ');  imprimer(); // Ce code est contribué par Rajput-Ji>

Sortir

10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10>

Avantages de la mise en œuvre de tableaux :

• Facile à mettre en œuvre.
• La mémoire est enregistrée car les pointeurs ne sont pas impliqués.

Inconvénients de la mise en œuvre d'un tableau :

• Il n’est pas dynamique, c’est-à-dire qu’il n’augmente pas et ne diminue pas en fonction des besoins au moment de l’exécution. [Mais dans le cas de tableaux de taille dynamique comme le vecteur en C++, la liste en Python, ArrayList en Java, les piles peuvent également augmenter et diminuer avec l'implémentation du tableau].
• La taille totale de la pile doit être définie au préalable.

// Programme C++ pour l'implémentation de liste chaînée de la pile #inclure en utilisant espace de noms norme; // Une structure pour représenter une pile classe Nœud de pile { publique: int données; Nœud de pile* suivant; } ; Nœud de pile* nouveau nœud(int données) { Nœud de pile* stackNode = nouveau Nœud de pile(); stackNode->données = données; stackNode->suivant = NUL; retour stackNode; } int est vide(Nœud de pile* racine) { retour !racine; } vide pousser(Nœud de pile** racine, int données) { Nœud de pile* stackNode = nouveau nœud(données); stackNode->suivant = *racine; *racine = stackNode; cout << données << ' poussé='' vers='' pile<='' span=''> '; } int populaire(Nœud de pile** racine) { si (est vide(*racine)) retour INT_MIN; Nœud de pile* temp. = *racine; *racine = (*racine)->suivant; int sauté = temp.->données; gratuit(temp.); retour sauté; } int coup d'oeil(Nœud de pile* racine) { si (est vide(racine)) retour INT_MIN; retour racine->données; } //Code du pilote int principal() { Nœud de pile* racine = NUL; pousser(&racine, dix); pousser(&racine, vingt); pousser(&racine, 30); cout << populaire(&racine) << ' est sorti de la pile '; cout << 'L'élément supérieur est' << coup d'oeil(racine) << fin; cout <<'Éléments présents dans la pile : '; //imprimer tous les éléments de la pile : alors que(!est vide(racine)) { // affiche l'élément supérieur de la pile cout << coup d'oeil(racine) <<' '; // supprime l'élément supérieur de la pile populaire(&racine); } retour 0; } // Ce code est fourni par rathbhupendraC

// C program for linked list implementation of stack #include  #include  #include  // A structure to represent a stack struct StackNode {  int data;  struct StackNode* next; }; struct StackNode* newNode(int data) {  struct StackNode* stackNode =   (struct StackNode*)  malloc(sizeof(struct StackNode));  stackNode->données = données ;  stackNode->suivant = NULL ;  retourner stackNode ; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** racine, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *racine = stackNode ;  printf('%d poussé vers la pile
', data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *root = (*root) -> suivant;  int sauté = temp->data;  libre (température);  retour sauté ; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  retourner racine->données ; } int main() { struct StackNode* root = NULL;  pousser(&root, 10);  pousser(&root, 20);  pousser(&root, 30);  printf('%d sorti de la pile
', pop(&root));  printf('L'élément supérieur est %d
', peek(root));  renvoie 0 ; }>

Java

// Java Code for Linked List Implementation public class StackAsLinkedList {  StackNode root;  static class StackNode {  int data;  StackNode next;  StackNode(int data) { this.data = data; }  }  public boolean isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  System.out.println(data + ' pushed to stack');  }  public int pop()  {  int popped = Integer.MIN_VALUE;  if (root == null) {  System.out.println('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  System.out.println('Stack is empty');  return Integer.MIN_VALUE;  }  else {  return root.data;  }  }  // Driver code  public static void main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());    sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());  } }>

Python

# Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

C#

// C# Code for Linked List Implementation using System; public class StackAsLinkedList {  StackNode root;  public class StackNode {  public int data;  public StackNode next;  public StackNode(int data) { this.data = data; }  }  public bool isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  Console.WriteLine(data + ' pushed to stack');  }  public int pop()  {  int popped = int.MinValue;  if (root == null) {  Console.WriteLine('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  Console.WriteLine('Stack is empty');  return int.MinValue;  }  else {  return root.data;  }  }  // Driver code  public static void Main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  Console.WriteLine(sll.pop() + ' popped from stack');  Console.WriteLine('Top element is ' + sll.peek());  } } /* This code contributed by PrinciRaj1992 */>

Javascript

>

Sortir

10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10>

Avantages de la mise en œuvre de listes chaînées :

• L'implémentation de liste chaînée d'une pile peut croître et diminuer en fonction des besoins au moment de l'exécution.
• Il est utilisé dans de nombreuses machines virtuelles comme JVM.

Inconvénients de la mise en œuvre de la liste chaînée :

• Nécessite de la mémoire supplémentaire en raison de l'implication de pointeurs.
• L'accès aléatoire n'est pas possible dans la pile.

Analyse de la complexité des opérations sur la structure de données de la pile :

Avantages de la pile Structure de données :

• Simplicité: Les piles constituent une structure de données simple et facile à comprendre, ce qui les rend adaptées à un large éventail d'applications.
• Efficacité: Les opérations push et pop sur une pile peuvent être effectuées en temps constant (O(1)) , offrant un accès efficace aux données.
• Dernier entré, premier sorti (LIFO) : Les piles suivent le principe LIFO, garantissant que le dernier élément ajouté à la pile est le premier supprimé. Ce comportement est utile dans de nombreux scénarios, tels que les appels de fonction et l'évaluation d'expressions.
• Utilisation de la mémoire limitée : Les piles n'ont besoin de stocker que les éléments qui y ont été placés, ce qui les rend efficaces en termes de mémoire par rapport à d'autres structures de données.

Inconvénients de la pile Structure de données :

• Accès limité: Les éléments d'une pile ne sont accessibles que par le haut, ce qui rend difficile la récupération ou la modification des éléments au milieu de la pile.
• Potentiel de débordement : Si plus d'éléments sont placés sur une pile qu'elle ne peut en contenir, une erreur de débordement se produira, entraînant une perte de données.
• Ne convient pas à l'accès aléatoire : Empiler Les s ne permettent pas un accès aléatoire aux éléments, ce qui les rend inadaptés aux applications où les éléments doivent être accessibles dans un ordre spécifique.
• Capacité limitée: Les piles ont une capacité fixe, ce qui peut constituer une limitation si le nombre d'éléments à stocker est inconnu ou très variable.

Applications de la structure de données de pile :

• Infixe à Postfix /Conversion de préfixe
• Fonctions de restauration et d'annulation à de nombreux endroits comme les éditeurs, Photoshop.
• Fonctionnalités avant et arrière dans les navigateurs Web
• Dans la gestion de la mémoire, tout ordinateur moderne utilise une pile comme gestion principale à des fins d'exécution. Chaque programme exécuté sur un système informatique dispose de ses propres allocations de mémoire.
• Stack aide également à implémenter l’appel de fonction dans les ordinateurs. La dernière fonction appelée est toujours terminée en premier.

Articles Liés:

• Implémenter une pile en utilisant une liste à chaînage unique
• Opérations de base dans la structure de données de pile avec implémentations
• Top 50 des problèmes liés à la structure des données de la pile posés lors des entretiens SDE
• Applications, avantages et inconvénients de Stack
  
• Pile pour une programmation compétitive