La pile n'est rien d'autre que la structure de données linéaire où l'insertion et la suppression n'ont lieu qu'à une seule extrémité. L'opération d'insertion porte un nom spécial appelé PUSH et l'opération de suppression porte également un nom spécial appelé POP. Le PUSH et le POP sont deux opérations fondamentales qui ne peuvent être effectuées que dans une pile particulière. Il s'agit d'un groupe d'emplacements de mémoire et les emplacements de mémoire sont liés à la mémoire de lecture ou à la mémoire d'écriture. Ceci est utilisé pour stocker des informations binaires pendant l'exécution du programme, lorsque nous exécutons un programme, le contenu de ce programme va être stocké dans la pile. Ça suit Dernier entré, premier sorti (LIFO) et il est utilisé uniquement pour stocker et récupérer les données, mais pas pour stocker les données. La brève explication du pointeur de pile / pile est présentée ci-dessous.
Qu'est-ce que Stack / Stack Pointer?
Définition: La pile est un périphérique de stockage, utilisé pour stocker des informations ou des données à la manière de LIFO (Last In First Out). Chaque fois que nous saisissons les données sous la forme de LIFO, l'élément qui doit être supprimé en premier est le dernier élément d'insertion, donc le dernier élément inséré est retiré en premier. C'est l'unité de mémoire dans un registre d'adresse appelé pointeur de pile (SP). Le pointeur de pile indique toujours l'élément supérieur de la pile, ce qui signifie à quel emplacement les données doivent être insérées.
Types de pile
Il existe deux types de piles: la pile de registres et la pile de mémoire.
Enregistrer la pile
La pile de registres est également un dispositif de mémoire présent dans l'unité de mémoire, mais elle ne gère qu'une petite quantité de données. La profondeur de la pile est toujours limitée dans la pile de registres car la taille de la pile de registres est très petite par rapport à la mémoire.
Opération Push dans la pile de registres
Étape 1: Le pointeur de pile s'incrémente de 1.
SP ← SP + 1
Étape 2: Entrez les données dans la pile.
1000 [SP] ← CT
Où DR est le registre de données
Étape 3: Vérifiez si la pile est pleine ou non
si (sp = 0) alors (plein ← 1)
Étape 4: Marquer comme non vide
vide ← 0
Opération Pop dans la pile de registres
Étape 1: Lisez les données de la pile.
DR ← M [SP]
Étape 2: Décrémenter le point de pile.
SP ← SP-1
Étape 3: Vérifiez si la pile est vide ou non
si sp = 0 alors vide ← 1
L'organisation de la pile de la pile de registres 64 bits est illustrée dans la figure ci-dessous.
Enregistrer l'organisation de la pile
Pile de mémoire
Dans la pile de mémoire, la profondeur de pile est flexible. Il occupe une grande quantité de données mémoire, alors que dans la pile de registres, seul un nombre fini de mots mémoire sera stocké.
Opération Push dans la pile de mémoire
Étape 1: SP ← SP-1
Étape 2: 1000 [SP] ← CT
Opération Pop dans la pile de mémoire
Étape 1: DR ← M [SP]
Étape 2: SP ← SP-1
Comparé à l'unité de registre, l'unité de mémoire stocke une grande quantité de données. La figure de la pile de mémoire est illustrée dans la figure ci-dessous.
Pile de mémoire
L'unité de mémoire totale est divisée en trois parties, la première unité de mémoire contient le programme (rien que des instructions), la deuxième partie est des données (opérandes) et la troisième partie est une pile. Les instructions de programme sont toujours stockées dans le compteur de programmes (PC), les registres de données sont identifiés par le registre d'adresse (AR). L'adresse 3000 à 4001 utilisée pour la pile et le premier élément ou élément est stockée en 4001.
Pointeur de pile / pile dans le microprocesseur 8085
La vue programmeur de 8085 microprocesseur contient des registres à usage général et registres à usage spécial . Les registres à usage général sont A, B, C, D, E, H, L et les registres à usage spécial sont SP (Stack Pointer) et PC (Program Counter). La vue du programmateur du microprocesseur 8085 est illustrée dans la figure ci-dessous.
Vue du programmeur sur 8085
Le pointeur de pile est un registre de 16 bits contenant une adresse mémoire, supposons que le contenu du pointeur de pile (SP) soit FC78H, puis le microprocesseur 8085 l'interprète. Les emplacements de mémoire contiennent des informations utiles de FC78H à FFFH et de FC77H à 0000H, l'emplacement de mémoire ne contient pas d'informations utiles. L'interprétation du pointeur de pile est illustrée dans la figure ci-dessous.
Interprétation du pointeur de pile
Opérations de base du pointeur de pile / pile
Il existe deux opérations de la pile: l'opération PUSH et l'opération POP.
Opération PUSH
Le PUSH signifie pousser ou insérer un élément dans la pile. L'opération PUSH incrémente toujours le pointeur de pile et l'opération POP décrémente toujours le pointeur de pile. Dans le cas d'une opération push, il faut vérifier s'il y a un espace libre disponible ou non. Si de l'espace libre est disponible, nous pouvons passer à l'opération push, si l'espace libre n'est pas disponible, un message d'erreur apparaît, indiquant un dépassement de capacité. Le débordement est à vérifier en cas de fonctionnement par poussée respectivement. Le fonctionnement de base du push and pop est illustré dans la figure ci-dessous.
Fonctionnement de base de PUSH et POP
La figure (a) est la pile. Si vous voulez pousser l'élément qui est une insertion de l'élément dans la pile, vous devez pousser (s, a), où «s» n'est rien d'autre qu'une pile. Dans la pile, nous plaçons l’élément «a» et cette opération est illustrée à la figure (b). Voir la figure (3), supposons que la pile contienne trois éléments a, b, c et que la pile soit remplie d'un élément.
Si vous souhaitez insérer un quatrième élément «d» en utilisant push (s, d), mais qu'il n'y a pas d'espace disponible pour insérer l'élément, cela indique que la pile est en débordement. La terminologie de débordement est utilisée lorsque la pile est pleine et que l'algorithme d'opération push est illustré ci-dessous.
push (pile [], haut, pile max, élément)
si (haut == maxstack-1)
{
imprimer «débordement»
}
autre
{
haut = haut + 1
pile [haut] = élément
}
finir
Opération POP
Le POP signifie la suppression de l'élément en haut de la pile. Dans le cas d'une opération pop, il faut vérifier si la pile est initialement vide ou non. Si la pile est initialement vide, il se produit une situation de sous-débordement. Supposons que la pile soit vide et que vous vouliez afficher les éléments dans la pile mais qu'il n'y a pas d'éléments dans la pile, cela conduit à un sous-débordement de la pile.
Le sous-débordement doit être vérifié en cas d'opération de pop respectivement. En opération pop, quel que soit l'élément supérieur présent dans la pile qui doit être poppé ou supprimé, donc pas besoin de mentionner quel élément sera poppé, par défaut, l'élément le plus haut sera poppé. L'algorithme de l'opération pop est illustré ci-dessous.
pop (pile [], haut, élément)
si (haut == - 1)
{
imprimer «underflow»
}
autre
{
item = pile [haut]
top = top-1
}
Exemple
Les éléments sont insérés dans l'ordre A, B, C, D, E, cela représente la pile de cinq éléments. Dans la figure (a), nous voulons pousser l'élément 'A' sur la pile puis le haut devient zéro (top = 0), de même le top = 1 lorsque l'élément 'B' est poussé, top = 2 lorsque l'élément 'C' est poussé, top = 3 lorsque l'élément 'D' est poussé et top = 4 lorsque l'élément 'E' est poussé.
Donc, quels que soient les éléments que j'ai pris, ils sont placés dans la pile, maintenant la pile est pleine. Si vous voulez pousser un autre élément, il n'y a pas de place dans la pile, cela indique donc le débordement. Maintenant, la pile est pleine si vous voulez faire apparaître l’élément «E», l’élément doit d’abord être supprimé. L'opération de poussée est illustrée dans la figure ci-dessous.
Opération Push
Nous devons utiliser l'opération pop pour supprimer les éléments de la pile. Alors mentionnez simplement pop (), n'écrivez pas d'arguments dans le pop car par défaut, il supprime l'élément supérieur. Le premier élément «E» est supprimé suivant l’élément «D»… .. «A». Lorsque les éléments supérieurs sont supprimés, la valeur supérieure diminue. Lorsque top = -1, la pile indique un dépassement inférieur. L'opération pop est illustrée dans la figure ci-dessous.
Opération POP
Voici donc l'explication de la façon dont les éléments sont insérés et supprimés dans la pile à l'aide des opérations push et pop.
Applications
Les applications du pointeur de pile / pile sont
- Inversion de chaîne
- Parenthèse équilibrée
- UNDO / FINGER
- Pile système pour les enregistrements d'activation
- Infixe, préfixe, suffixe, expression
FAQ
1). Quel est le pointeur de pile dans le bras?
Le registre de pointeur de pile (R13) utilisé comme pointeur vers la pile active dans ARM.
2). Pourquoi le pointeur de pile est-il 16 bits?
Le pointeur de pile (SP) et le compteur de programme (PC) utilisés pour stocker l'emplacement précédent et l'adresse d'emplacement de mémoire est de 16 bits, de sorte que le pointeur de pile (SP) est également de 16 bits.
3). Quel est le rôle du pointeur de pile?
Le rôle du pointeur de pile (SP) est d'indiquer le haut de l'élément dans la pile.
4). Quelle pile est utilisée dans 8085?
La pile utilisée en 8085 est Last In First Out (LIFO).
5). Le pointeur de pile est-il un registre?
Oui, le pointeur de pile (SP) est un registre d'adresse qui indique toujours le haut de l'élément dans la pile.
