stack data structure c with illustration
question et réponse d'entrevue de test de logiciel pour plus
Tout ce que vous devez savoir sur Stack en C ++.
La pile est une structure de données fondamentale utilisée pour stocker des éléments de manière linéaire.
La pile suit LIFO (dernier entré, premier sorti) l'ordre ou l'approche dans lequel les opérations sont effectuées. Cela signifie que l'élément qui a été ajouté en dernier à la pile sera le premier élément à être retiré de la pile.
=> Visitez ici pour voir toute la série de formations C ++ pour tous.
Ce que vous apprendrez:
- Empiler en C ++
Empiler en C ++
Une pile est similaire à une pile réelle ou à une pile de choses que nous empilons les unes sur les autres.
Ci-dessous est une représentation picturale de Stack.
Comme indiqué ci-dessus, il y a une pile d'assiettes empilées les unes sur les autres. Si nous voulons y ajouter un autre élément, nous l'ajoutons en haut de la pile comme indiqué dans la figure ci-dessus (côté gauche). Cette opération d'ajout d'un élément à la pile s'appelle ' Pousser ».
Sur le côté droit, nous avons montré une opération opposée, c'est-à-dire que nous supprimons un élément de la pile. Cela se fait également à partir de la même extrémité, c'est-à-dire le haut de la pile. Cette opération s'appelle ' Pop ».
Comme le montre la figure ci-dessus, nous voyons que le push et le pop sont effectués à partir de la même extrémité. Cela oblige la pile à suivre l'ordre LIFO. La position ou la fin à partir de laquelle les éléments sont insérés ou sortis de / vers la pile est appelée ' Haut de la pile ».
Au départ, lorsqu'il n'y a aucun élément dans la pile, le haut de la pile est défini sur -1. Lorsque nous ajoutons un élément à la pile, le haut de la pile est incrémenté de 1 indiquant que l'élément est ajouté. Contrairement à cela, le haut de la pile est décrémenté de 1 lorsqu'un élément est sorti de la pile.
Ensuite, nous verrons certaines des opérations de base de la structure de données de la pile dont nous aurons besoin lors de l'implémentation de la pile.
Opérations de base
Voici les opérations de base prises en charge par la pile.
- pousser - Ajoute ou pousse un élément dans la pile.
- pop - Supprime ou fait sortir un élément de la pile.
- coup d'oeil - Obtient l'élément supérieur de la pile mais ne le supprime pas.
- est rempli - Teste si la pile est pleine.
- est vide - Teste si la pile est vide.
Illustration
L'illustration ci-dessus montre la séquence des opérations effectuées sur la pile. Au départ, la pile est vide. Pour une pile vide, le haut de la pile est défini sur -1.
Ensuite, nous poussons l'élément 10 dans la pile. On voit que le haut de la pile pointe maintenant vers l'élément 10.
Ensuite, nous effectuons une autre opération de poussée avec l'élément 20, à la suite de laquelle le haut de la pile pointe maintenant vers 20. Cet état est le troisième chiffre.
Maintenant, dans la dernière figure, nous effectuons une opération pop (). À la suite de l'opération pop, l'élément pointé vers le haut de la pile est retiré de la pile. Ainsi, sur la figure, on voit que l'élément 20 est retiré de la pile. Ainsi, le haut de la pile pointe désormais sur 10.
De cette manière, on distingue facilement l'approche LIFO utilisée par stack.
Mise en œuvre
# 1) Utilisation de tableaux
Voici l'implémentation C ++ de stack à l'aide de tableaux:
#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack[MAX]; //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack[++top] = item; cout< Production:
La poussée de la pile
deux
4
6
Le Stack Pop:
6
4
deux
Dans la sortie, nous pouvons voir que les éléments sont poussés dans la pile dans un ordre et sont sortis de la pile dans l'ordre inverse. Cela présente l'approche LIFO (dernier entré, premier sorti) pour la pile.
Pour l'implémentation de tableau ci-dessus de la pile, nous pouvons conclure que c'est très facile à implémenter car il n'y a pas de pointeurs impliqués. Mais en même temps, la taille de la pile est statique et la pile ne peut pas croître ou se réduire dynamiquement.
Ensuite, nous implémenterons la pile à l'aide de tableaux dans le langage de programmation Java.
class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack[] = new int[MAX]; boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack[++top] = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack[top--]; return item; } } } //Main class code class Main { public static void main(String args[]) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }
Production:
Pousser la pile:
1
3
5
Pop de pile:
5
3
1
La logique d'implémentation est la même que dans l'implémentation C ++. La sortie montre la technique LIFO consistant à pousser et à sortir des éléments vers / depuis la pile.
Comme déjà indiqué, la mise en œuvre de la pile à l'aide de tableaux est la mise en œuvre la plus simple, mais elle est de nature statique car nous ne pouvons pas augmenter ou réduire dynamiquement la pile.
# 2) Utilisation d'une liste liée
Ensuite, nous implémentons des opérations de pile à l'aide d'une liste chaînée en C ++ et Java. Tout d'abord, nous allons démontrer l'implémentation C ++.
#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'< Production:
meilleur logiciel espion de téléphone portable pour android
Pousser la pile:
100
200
300
L'élément supérieur est 300
Pop de pile:
300
200
100
L'élément supérieur est -1
Ensuite, nous présentons l'implémentation Java de la pile à l'aide d'une liste chaînée.
class LinkedListStack { 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 new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } 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; } } } class Main{ public static void main(String[] args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } }
Production:
Pousser la pile:
100
200
300
L'élément supérieur est 300
Pop de pile:
300
200
100
La pile est vide
L'élément supérieur est -2147483648
Nous venons de voir les implémentations C ++ et Java pour une pile utilisant des listes chaînées. Nous représentons chaque entrée de pile comme un nœud de la liste chaînée. L'avantage le plus important de cette implémentation est qu'elle est dynamique. Cela signifie que nous pouvons augmenter ou réduire la taille de la pile selon nos besoins.
Ceci est différent du cas de l'implémentation de pile utilisant des tableaux dans lesquels nous devons déclarer la taille au préalable et ne pouvons pas la modifier dynamiquement.
L'inconvénient de cette implémentation est que, comme nous utilisons des pointeurs partout, cela prend un peu trop de place par rapport à l'implémentation de tableau.
Applications de Stack
Laissez-nous discuter de certaines des applications de la structure de données de pile. La structure de données de pile est utilisée dans une gamme d'applications de programmation logicielle principalement en raison de sa simplicité et de sa facilité de mise en œuvre.
Nous décrirons brièvement quelques-unes des applications de la pile ci-dessous:
# 1) Infix aux expressions Postfix
Toute expression arithmétique générale est de la forme opérande 1 OP opérande 2 .
En fonction de la position de l'opérateur OP, nous avons les types d'expressions suivants:
- Infixe - La forme générale de l'expression infixe est ' opérande 1 OP opérande 2 ». C'est la forme de base de l'expression et nous l'utilisons tout le temps en mathématiques.
- Préfixe - Lorsqu'un opérateur est placé avant les opérandes, il s'agit d'une expression de préfixe. La forme générale de l'expression infixe est ' OP opérande1 opérande2 ».
- Postfix - Dans les expressions postfixes, les opérandes sont écrits en premier, suivis de l'opérateur. Il a la forme «opérande1 opérande2 OP».
Considérez l'expression «a + b * c ' . Le compilateur analyse l'expression de gauche à droite ou de droite à gauche. En prenant soin de la priorité des opérateurs et de l'associativité, il analysera d'abord l'expression pour évaluer l'expression b * c. Ensuite, il devra à nouveau parcourir l'expression pour ajouter le résultat de b * c à a.
Au fur et à mesure que les expressions deviennent de plus en plus complexes, ce type d'approche consistant à scanner encore et encore l'expression devient inefficace.
Afin de surmonter cette inefficacité, nous convertissons l'expression en suffixe ou préfixe de sorte qu'ils puissent être facilement évalués à l'aide d'une structure de données de pile.
# 2) Analyse / évaluation des expressions
En utilisant stack, nous pouvons également effectuer une évaluation d'expression réelle. Dans ce cas, l'expression est balayée de gauche à droite et les opérandes sont poussés sur la pile.
Chaque fois qu'un opérateur est rencontré, les opérandes sont sortis et l'opération est effectuée. Le résultat de l'opération est à nouveau poussé dans la pile. De cette façon, l'expression est évaluée à l'aide de pile et le résultat final de l'expression est généralement le haut actuel de la pile.
# 3) Traversées d'arbres
La structure de données arborescente peut être traversée pour visiter chaque nœud de plusieurs manières et en fonction du moment où le nœud racine que nous avons est visité.
- inOrder traversal
- précommande Traversal
- Traversée postOrder
Pour traverser efficacement l'arbre, nous utilisons la structure de données de la pile afin de pousser les nœuds intermédiaires sur la pile afin de maintenir l'ordre de traversée.
# 4) Algorithmes de tri
Les algorithmes de tri comme le tri rapide peuvent être rendus plus efficaces en utilisant les structures de données de la pile.
# 5) Tours de Hanoi
Il s'agit d'un problème classique impliquant n nombre de disques et trois tours et le problème consiste à déplacer les disques d'une tour à une autre avec la troisième tour servant d'intermédiaire.
Ce problème peut être résolu efficacement en utilisant la pile lorsque nous poussons les disques à déplacer vers la pile, car la pile agit essentiellement comme une tour utilisée pour déplacer les disques.
Conclusion
La pile est la structure de données la plus simple et la plus facile à implémenter en tant que programme. Il a utilisé l'approche LIFO (dernier entré, premier sorti), ce qui signifie que l'élément entré en dernier est celui qui est supprimé en premier. En effet, la pile utilise une seule extrémité pour ajouter (pousser) et supprimer (pop) des éléments.
La structure de données de pile a de nombreuses utilisations dans la programmation logicielle. Le plus important d'entre eux est l'évaluation des expressions. L'évaluation des expressions comprend également la conversion de l'expression d'infixe en suffixe ou préfixe. Cela implique également d'évaluer l'expression pour produire le résultat final.
Dans ce tutoriel, nous avons vu l'illustration et l'implémentation de la pile ainsi que ses différentes opérations.
Dans notre prochain didacticiel, nous en apprendrons davantage sur la structure des données de la file d'attente.
=> Visitez ici pour le cours C ++ complet d'experts.
lecture recommandée
- Structure de données de file d'attente en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Structure de données de liste liée en C ++ avec illustration
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- Structure de données de liste doublement liée en C ++ avec illustration
- Introduction aux structures de données en C ++
- Paramétrage des données JMeter à l'aide de variables définies par l'utilisateur
- 10+ meilleurs outils de collecte de données avec des stratégies de collecte de données