Linked list implementazione di stack

Invece di usare array, possiamo anche usare linked list per implementare stack. L’elenco collegato alloca dinamicamente la memoria. Tuttavia, la complessità temporale in entrambi gli scenari è la stessa per tutte le operazioni, ad esempio push, pop e peek.

Nell’implementazione della lista collegata dello stack, i nodi vengono mantenuti non contigui nella memoria. Ogni nodo contiene un puntatore al suo nodo successore immediato nello stack. Si dice che lo stack sia overflown se lo spazio lasciato nell’heap di memoria non è sufficiente per creare un nodo.

Il nodo più in alto nello stack contiene sempre null nel suo campo indirizzo. Consente di discutere il modo in cui, ogni operazione viene eseguita nell’implementazione elenco collegato di stack.

Aggiunta di un nodo allo stack (operazione Push)

L’aggiunta di un nodo allo stack viene definita operazione push. Spingere un elemento in uno stack nell’implementazione di elenchi collegati è diverso da quello di un’implementazione di array. Per spingere un elemento sullo stack, sono coinvolti i seguenti passaggi.

1. Crea prima un nodo e alloca la memoria ad esso.
2. Se l’elenco è vuoto, l’elemento deve essere spinto come nodo iniziale dell’elenco. Ciò include l’assegnazione di valore alla parte dati del nodo e l’assegnazione di null alla parte indirizzo del nodo.
3. Se ci sono già alcuni nodi nell’elenco, dobbiamo aggiungere il nuovo elemento all’inizio dell’elenco (per non violare la proprietà dello stack). A tale scopo, assegnare l’indirizzo dell’elemento di partenza al campo indirizzo del nuovo nodo e rendere il nuovo nodo, il nodo di partenza dell’elenco.

Complessità temporale: o(1)



C implementazione :

Eliminazione di un nodo dallo stack (operazione POP)

L’eliminazione di un nodo dalla parte superiore dello stack viene definita operazione pop. L’eliminazione di un nodo dall’implementazione dell’elenco collegato di stack è diversa da quella dell’implementazione dell’array. Per far apparire un elemento dallo stack, dobbiamo seguire i seguenti passaggi :

1. Controlla la condizione underflow: la condizione underflow si verifica quando proviamo a fare un pop da uno stack già vuoto. Lo stack sarà vuoto se il puntatore head dell’elenco punta a null.
2. Regola di conseguenza il puntatore head: in stack, gli elementi vengono spuntati solo da un’estremità, pertanto, il valore memorizzato nel puntatore head deve essere eliminato e il nodo deve essere liberato. Il nodo successivo del nodo head ora diventa il nodo head.

Complessità temporale : o (n)

C implementazione

Visualizza i nodi (Attraversamento)

Visualizza tutti i nodi di uno stack che deve attraversare tutti i nodi dell’elenco collegato organizzato sotto forma di stack. A tale scopo, dobbiamo seguire i seguenti passaggi.

1. Copia il puntatore head in un puntatore temporaneo.
2. Sposta il puntatore temporaneo attraverso tutti i nodi dell’elenco e stampa il campo valore collegato a ogni nodo.

Complessità temporale : o (n)

C Implementazione

Programma guidato dal menu in C implementazione di tutte le operazioni dello stack utilizzando l’elenco collegato :