La pila no és res més que l’estructura lineal de dades on la inserció i la supressió només tenen lloc en un extrem. L'operació d'inserció té un nom especial conegut com a PUSH i l'operació de supressió també té un nom especial conegut com a POP. El PUSH i el POP són dues operacions fonamentals que només es podrien dur a terme en una pila concreta. És un grup de ubicacions de memòria i les ubicacions de memòria estan relacionades amb la memòria de lectura o la memòria d’escriptura. S'utilitza per emmagatzemar informació binària durant l'execució del programa, quan estem executant qualsevol programa, el contingut d'aquest programa s'emmagatzemarà a la pila. Segueix Últim en primer lloc (LIFO) i s’utilitza només per emmagatzemar i recuperar les dades, però no s’utilitza per emmagatzemar-les. A continuació es descriu la breu explicació del punter de pila / pila.
Què és el Stack / Stack Pointer?
Definició: La pila és un dispositiu d’emmagatzematge que s’utilitza per emmagatzemar informació o dades en forma de LIFO (Last In First Out). Sempre que introduïm les dades en forma LIFO, l’element que s’ha d’eliminar primer és l’últim element inseridor, de manera que l’últim element inserit es treu primer. És la unitat de memòria d'un registre d'adreces anomenat punter de pila (SP). El punter de la pila sempre indica l'element superior de la pila que significa la ubicació que s'han d'inserir les dades.
Tipus de pila
Hi ha dos tipus de piles: pila de registres i pila de memòria.
Pila de registre
La pila de registres també és un dispositiu de memòria present a la unitat de memòria, però només gestiona una petita quantitat de dades. La profunditat de la pila sempre és limitada a la pila de registres perquè la mida de la pila de registres és molt petita en comparació amb la memòria.
Premeu l'operació a la pila de registre
Pas 1: El punter de la pila augmenta 1.
SP ← SP +1
Pas 2: Introduïu les dades a la pila.
1000 [SP] ← CT
On DR és el registre de dades
Pas 3: Comproveu si la pila està plena o no
if (sp = 0) llavors (complet ← 1)
Pas 4: Marca com a no buit
empty ← 0
Operació Pop a Register Stack
Pas 1: Llegiu les dades de la pila.
DR ← M [SP]
Pas 2: Decrement del punt de pila.
SP ← SP-1
Pas 3: Comproveu si la pila està buida o no
si sp = 0 buida ← 1
L'organització de la pila de registres de 64 bits es mostra a la figura següent.
Registra l'organització de la pila
Pila de memòria
A la pila de memòria, la profunditat de la pila és flexible. Ocupa una gran quantitat de dades de memòria, mentre que a la pila de registres només s'emmagatzemaran un nombre finit de paraules de memòria.
Premeu l'operació a la pila de memòria
Pas 1: SP ← SP-1
Pas 2: 1000 [SP] ← CT
Operació pop a Memory Stack
Pas 1: DR ← M [SP]
Pas 2: SP ← SP-1
En comparació amb la unitat de registre, la unitat de memòria emmagatzema una gran quantitat de dades. La figura de la pila de memòria es mostra a la figura següent.
Pila de memòria
La unitat de memòria total es divideix en tres parts, la primera unitat de memòria té el programa (res més que instruccions), la segona part són dades (operands) i la tercera part és una pila. Les instruccions del programa sempre s’emmagatzemen al comptador de programes (PC), els registres de dades s’identifiquen mitjançant el registre d’adreces (AR). L'adreça 3000 a 4001 que s'utilitza per a la pila i el primer element o element s'emmagatzema a 4001.
Apilador Stack / Stack en microprocessador 8085
La vista del programador del 8085 microprocessador conté registres per a usos generals i registres per a usos especials . Els registres d’ús general són A, B, C, D, E, H, L i els registres d’ús especial són SP (Stack Pointer) i PC (Program Counter). La vista del programador del microprocessador 8085 es mostra a la figura següent.
Vista de programador de 8085
El punter de pila és un registre de 16 bits que conté adreces de memòria, suposem que el contingut del punter de pila (SP) és FC78H, aleshores el microprocessador 8085 ho interpreta. Les ubicacions de memòria tenen informació útil de FC78H a FFFH i de FC77H a 0000H, la ubicació de memòria no té informació útil. La interpretació del punter de la pila es mostra a la figura següent.
Interpretació de Stack Pointer
Operacions bàsiques de Stack / Stack Pointer
Hi ha dues operacions de la pila que són: operació PUSH i operació POP.
Operació PUSH
PUSH significa empènyer o inserir un element a la pila. L'operació PUSH sempre augmenta el punter de la pila i l'operació POP sempre disminueix el punter de la pila. En el cas d’una operació push, hem de comprovar si hi ha un espai lliure disponible o no. Si hi ha espai lliure disponible, podem anar a l’operació push, si no hi ha espai lliure, es produirà un missatge d’error que és un desbordament. El desbordament s'ha de comprovar en cas d'operació push, respectivament. El funcionament bàsic de push i pop es mostra a la figura següent.
Funcionament bàsic de PUSH i POP
La figura (a) és la pila. Si voleu empènyer l’element que és inserir l’element a la pila, heu de prémer (s, a), on ‘s’ no és més que una pila. A la pila, col·loquem l’element ‘a’ i aquesta operació es mostra a la figura (b). Vegeu la figura (3), suposem que la pila conté tres elements a, b, c i que la pila està plena d’un element.
Si voleu inserir un quart element -d utilitzant push (s, d), però no hi ha espai disponible per inserir l'element, indica que la pila està desbordada. La terminologia de desbordament s'utilitza quan la pila està plena i l'algoritme d'operació push es mostra a continuació.
push (stack [], top, stack màxim, element)
if (top == maxstack-1)
{
imprimir 'desbordament'
}
en cas contrari
{
amunt = amunt + 1
stack [top] = element
}
final
Operació POP
El POP significa eliminar l’element situat a la part superior de la pila. En el cas de l’operació pop, hem de comprovar si la pila està inicialment buida o no. Si la pila està inicialment buida, es produeix una situació de desbordament. Suposem que la pila està buida, encara que voleu fer aparèixer els elements de la pila, però no hi ha elements a la pila, donant lloc a un flux inferior de pila.
S'ha de comprovar el flux inferior en cas d'operació pop respectivament. En operació emergent, sigui quin sigui l'element superior que hi hagi a la pila que s'hauria de mostrar o suprimir, de manera que no cal esmentar quin element apareixerà, per defecte apareixerà l'element superior. A continuació es mostra l'algorisme d'operació pop.
pop (stack [], top, item)
if (superior == - 1)
{
imprimir 'submergit'
}
en cas contrari
{
item = stack [dalt]
top = top-1
}
Exemple
Els elements s'insereixen en l'ordre A, B, C, D, E, que representa la pila de cinc elements. A la figura (a), volem prémer l’element 'A' a la pila, llavors la part superior es torna zero (superior = 0), de manera similar la part superior = 1 quan es prem l'element 'B', la part superior = 2 quan l'element 'C' s'empeny, superior = 3 quan es prem l'element 'D' i superior = 4 quan es prem l'element 'E'.
Així doncs, siguin quins siguin els elements que he pres a la pila, ara la pila està plena. Si voleu empènyer un altre element, no hi ha lloc a la pila, de manera que indica el desbordament. Ara la pila està plena si voleu fer aparèixer l'element 'E' que primer s'ha de suprimir. L'operació d'empenta es mostra a la figura següent.
Operació Push
Hem d’utilitzar l’operació pop per eliminar els elements de la pila. Així que només heu d’esmentar pop () no escriviu arguments al pop perquè, per defecte, elimina l’element superior. El primer element 'E' se suprimeix el següent element 'D' ... .. 'A'. Quan els elements superiors s’eliminen, el valor superior disminueix. Quan és superior = -1, la pila indica un desbordament. L'operació emergent es mostra a la figura següent.
Operació POP
Així doncs, aquesta és l’explicació de com s’insereixen i s’eliminen els elements a la pila mitjançant l’operació push i pop.
Aplicacions
Les aplicacions del punter stack / stack són
- Inversió de corda
- Parèntesi equilibrat
- UNDO / DIT
- Pila de sistemes per a registres d'activació
- Infix, prefix, postfix, expressió
Preguntes freqüents
1). Què és el punter de la pila al braç?
El registre de punter de pila (R13) utilitzat com a punter de la pila activa a ARM.
2). Per què el punter de pila és de 16 bits?
El punter de pila (SP) i el comptador de programes (PC) que s’utilitzen per emmagatzemar la ubicació anterior i l’adreça de la ubicació de memòria és de 16 bits, de manera que el punter de pila (SP) també és de 16 bits.
3). Quin és el paper del punter de la pila?
El paper del punter de la pila (SP) és indicar la part superior de l'element de la pila.
4). Quina pila s’utilitza al 8085?
La pila utilitzada al 8085 és Last In First Out (LIFO).
5). El punter de pila és un registre?
Sí, el punter de pila (SP) és un registre d'adreces que sempre indica la part superior de l'element de la pila.
