Lo stack non è altro che la struttura dati lineare in cui l'inserimento e la cancellazione avvengono solo a un'estremità. L'operazione di inserimento ha un nome speciale noto come PUSH e anche l'operazione di eliminazione ha un nome speciale noto come POP. Il PUSH e il POP sono due operazioni fondamentali che potrebbero essere svolte solo in un particolare stack. È un gruppo di posizioni di memoria e le posizioni di memoria sono correlate alla memoria di lettura o alla memoria di scrittura. Questo viene utilizzato per memorizzare informazioni binarie durante l'esecuzione del programma, quando eseguiamo qualsiasi programma, il contenuto di quel programma verrà memorizzato nello stack. Segue Ultimo ad entrare, primo ad uscire (LIFO) e viene utilizzato solo per archiviare e recuperare i dati ma non per archiviare i dati. La breve spiegazione del puntatore stack / stack è discussa di seguito.
Cos'è Stack / Stack Pointer?
Definizione: Lo stack è un dispositivo di archiviazione, utilizzato per memorizzare informazioni o dati in un modo LIFO (Last In First Out). Ogni volta che si inseriscono i dati in modo LIFO, l'elemento che deve essere cancellato per primo è l'ultimo elemento di inserimento, quindi l'ultimo elemento inserito viene rimosso per primo. È l'unità di memoria all'interno di un registro di indirizzi chiamato stack pointer (SP). Il puntatore dello stack indica sempre l'elemento in cima allo stack, il che significa in quale posizione devono essere inseriti i dati.
Tipi di stack
Esistono due tipi di stack: lo stack di registri e lo stack di memoria.
Stack di registro
Lo stack di registri è anche un dispositivo di memoria presente nell'unità di memoria, ma gestisce solo una piccola quantità di dati. La profondità dello stack è sempre limitata nello stack di registri perché la dimensione dello stack di registri è molto piccola rispetto alla memoria.
Operazione di push nello stack di registro
Passo 1: Il puntatore dello stack aumenta di 1.
SP ← SP + 1
Passo 2: Immettere i dati nello stack.
1000 [SP] ← CT
Dove DR è il registro dei dati
Step3: Controlla se la pila è piena o meno
if (sp = 0) then (full ← 1)
Step4: Segna non vuoto
vuoto ← 0
Operazione Pop in Stack di registro
Passo 1: Leggi i dati dallo stack.
DR ← M [SP]
Passo 2: Diminuisci lo stack point.
SP ← SP-1
Step3: Controlla se la pila è vuota o meno
se sp = 0 allora vuoto ← 1
L'organizzazione dello stack dello stack del registro a 64 bit è mostrata nella figura seguente.
Registra organizzazione stack
Stack di memoria
Nello stack di memoria, la profondità dello stack è flessibile. Occupa una grande quantità di dati di memoria, mentre nello stack di registri verrà memorizzato solo un numero finito di parole di memoria.
Operazione di push nello stack di memoria
Passo 1: SP ← SP-1
Passo 2: 1000 [SP] ← CT
Operazione Pop in Memory Stack
Passo 1: DR ← M [SP]
Passo 2: SP ← SP-1
Rispetto all'unità di registro, l'unità di memoria memorizza una grande quantità di dati. La figura dello stack di memoria è mostrata nella figura seguente.
Stack di memoria
L'unità di memoria totale è divisa in tre parti, la prima unità di memoria ha il programma (nient'altro che istruzioni), la seconda parte sono i dati (operandi) e la terza parte è lo stack. Le istruzioni del programma vengono sempre memorizzate nel program counter (PC), i registri dei dati sono identificati dal registro degli indirizzi (AR). L'indirizzo da 3000 a 4001 utilizzato per lo stack e il primo elemento o elemento è memorizzato in 4001.
Stack / Stack Pointer nel microprocessore 8085
La vista del programmatore dell'8085 microprocessore contiene registri di uso generale e registri speciali . I registri per scopi generici sono A, B, C, D, E, H, L ei registri per scopi speciali sono SP (Stack Pointer) e PC (Program Counter). La vista del programmatore del microprocessore 8085 è mostrata nella figura seguente.
Vista programmatore dell'8085
Lo stack pointer è un registro a 16 bit che contiene un indirizzo di memoria, supponiamo che il contenuto dello stack pointer (SP) sia FC78H, quindi il microprocessore 8085 lo interpreta. Le posizioni di memoria hanno informazioni utili da FC78H a FFFH e da FC77H a 0000H le posizioni di memoria non hanno informazioni utili. L'interpretazione del puntatore allo stack è mostrata nella figura seguente.
Interpretazione dello Stack Pointer
Operazioni di base di Stack / Stack Pointer
Ci sono due operazioni dello stack che sono: operazione PUSH e operazione POP.
Operazione PUSH
Il PUSH significa spingere o inserire un elemento nella pila. L'operazione PUSH incrementa sempre il puntatore dello stack e l'operazione POP sempre decrementa il puntatore dello stack. Nel caso di un'operazione push, dobbiamo verificare se c'è uno spazio libero disponibile o meno. Se è disponibile spazio libero, è possibile passare all'operazione push, se lo spazio libero non è disponibile, viene visualizzato un messaggio di errore che è in overflow. Il troppo pieno deve essere controllato rispettivamente in caso di funzionamento a spinta. L'operazione di base di push and pop è mostrata nella figura sottostante.
Operazioni di base di PUSH e POP
La figura (a) è la pila. Se vuoi spingere l'elemento che sta inserendo l'elemento nello stack, devi spingere (s, a), dove 's' non è altro che uno stack. Nello stack, stiamo posizionando l'elemento 'a' e questa operazione è mostrata nella figura (b). Vedere la figura (3), supponiamo che lo stack contenga tre elementi a, b, c, e lo stack sia riempito con un elemento.
Se desideri inserire un quarto elemento, 'd', utilizzando push (s, d), ma non c'è spazio disponibile per inserire l'elemento, significa che lo stack è in overflow. La terminologia di overflow viene utilizzata quando lo stack è pieno e l'algoritmo dell'operazione push è mostrato di seguito.
push (stack [], top, max stack, item)
if (top == maxstack-1)
{
stampa 'overflow'
}
altro
{
top = top + 1
stack [top] = elemento
}
fine
Operazione POP
Il POP significa eliminare l'elemento in cima allo stack. Nel caso dell'operazione pop, dobbiamo controllare se lo stack è inizialmente vuoto o meno. Se lo stack è inizialmente vuoto, si verifica una situazione di underflow. Supponiamo che lo stack sia vuoto, ma vuoi inserire gli elementi nello stack ma non ci sono elementi nello stack, quindi si verifica l'underflow dello stack.
L'underflow deve essere verificato rispettivamente in caso di operazione pop. Nell'operazione pop qualunque sia l'elemento in cima allo stack che dovrebbe essere estratto o cancellato, quindi non c'è bisogno di menzionare quale elemento verrà estratto, per impostazione predefinita verrà estratto l'elemento più in alto. L'algoritmo dell'operazione pop è mostrato di seguito.
pop (stack [], top, item)
if (top == - 1)
{
stampa 'underflow'
}
altro
{
elemento = pila [in alto]
top = top-1
}
Esempio
Gli elementi sono inseriti nell'ordine A, B, C, D, E, rappresenta la pila di cinque elementi. Nella figura (a), vogliamo spingere l'elemento 'A' sullo stack, quindi il top diventa zero (top = 0), allo stesso modo top = 1 quando viene premuto l'elemento 'B', top = 2 quando l'elemento 'C' viene spinto, in alto = 3 quando l'elemento 'D' viene spinto e in alto = 4 quando viene spinto l'elemento 'E'.
Quindi qualunque sia l'elemento che ho preso è stato posizionato nella pila, ora la pila è piena. Se vuoi spingere un altro elemento non c'è posto nello stack, quindi indica l'overflow. Ora lo stack è pieno se si desidera visualizzare l'elemento 'E', l'elemento deve essere prima eliminato. L'operazione di spinta è mostrata nella figura seguente.
Operazione push
Dobbiamo usare l'operazione pop per eliminare gli elementi nello stack. Quindi menziona solo pop (), non scrivere argomenti nel pop perché per impostazione predefinita elimina l'elemento in alto. Il primo elemento 'E' viene eliminato successivo elemento 'D' ... .. 'A'. Quando gli elementi superiori vengono eliminati, il valore superiore diminuisce. Quando top = -1 lo stack indica underflow. L'operazione di pop è mostrata nella figura seguente.
Operazione POP
Quindi questa è la spiegazione di come gli elementi vengono inseriti ed eliminati nello stack utilizzando l'operazione push and pop.
Applicazioni
Le applicazioni del puntatore stack / stack sono
- Inversione di stringa
- Parentesi equilibrata
- UNDO / FINGER
- Stack di sistema per i record di attivazione
- Infisso, prefisso, suffisso, espressione
Domande frequenti
1). Qual è lo stack pointer nel braccio?
Lo stack pointer register (R13) utilizzato come puntatore allo stack attivo in ARM.
2). Perché lo stack pointer è a 16 bit?
Lo stack pointer (SP) e il program counter (PC) utilizzati per memorizzare la posizione precedente e l'indirizzo della posizione di memoria sono 16 bit, quindi anche lo stack pointer (SP) è di 16 bit.
3). Qual è il ruolo dello stack pointer?
Il ruolo del puntatore allo stack (SP) è indicare la parte superiore dell'elemento nello stack.
4). Quale stack viene utilizzato in 8085?
Lo stack utilizzato in 8085 è Last In First Out (LIFO).
5). Lo stack pointer è un registro?
Sì, lo stack pointer (SP) è un registro di indirizzi che indica sempre la parte superiore dell'elemento nello stack.
