1. Dettaglio dell'operazione Push (Inserimento)
L'operazione Push consente di aggiungere un elemento in cima alla struttura (Top). Sia che lo stack sia implementato tramite un array statico o tramite una lista dinamica concatenata, l'inserimento avviene sempre a costo computazionale costante.
- Controllo Overflow: Nel caso di un array a dimensione fissa, prima di procedere bisogna verificare che lo stack non abbia raggiunto la capacità massima ($\text{top} == \text{MAX\_SIZE} - 1$). Nelle liste dinamiche, il limite è vincolato unicamente dalla memoria RAM disponibile.
- Aggiornamento del puntatore: L'indice o il puntatore di cima viene incrementato o fatto puntare al nuovo nodo inserito.
void push(int *stack, int *top, int valore, int maxSize) {
if (*top >= maxSize - 1) {
printf("Errore: Stack Overflow!\n");
return;
}
(*top)++;
stack[*top] = valore;
}
2. Dettaglio dell'operazione Pop (Rimozione)
L'operazione Pop preleva e rimuove l'elemento situato in cima alla pila.
- Controllo Underflow: È fondamentale verificare preventivamente che la pila non sia vuota ($\text{top} == -1$), poiché tentare di rimuovere elementi da uno stack vuoto genera un errore critico di esecuzione.
- Restituzione del dato: Il valore prelevato dalla posizione corrente di
topviene restituito al chiamante, e l'indice viene decrementato per riflettere il nuovo stato della cima.
int pop(int *stack, int *top) {
if (*top < 0) {
printf("Errore: Stack Underflow!\n");
return -1;
}
int rimosso = stack[*top];
(*top)--;
return rimosso;
}
Complessità Computazionale:
Sia l'operazione Push che l'operazione Pop operano in tempo costante nel caso peggiore:
$$\mathcal{O}(1)$$
Poiché l'accesso avviene sempre e solo in cima, non è necessario scorrere alcun elemento della struttura.