Invece di usare l'array, possiamo anche usare l'elenco collegato per implementare lo stack. L'elenco collegato alloca la memoria in modo dinamico. Tuttavia, la complessità temporale in entrambi gli scenari è la stessa per tutte le operazioni, ovvero push, pop e peek.

Nell'implementazione dello stack con elenchi collegati, i nodi vengono mantenuti non contigui nella memoria. Ogni nodo contiene un puntatore al nodo successivo immediato nello stack. Si dice che lo stack sia overflow se lo spazio rimasto nell'heap di memoria non è sufficiente per creare un nodo.

Il nodo più in alto nello stack contiene sempre null nel suo campo indirizzo. Parliamo del modo in cui ciascuna operazione viene eseguita nell'implementazione dell'elenco collegato dello stack.

Aggiunta di un nodo allo stack (operazione Push)

L'aggiunta di un nodo allo stack viene definita come spingere operazione. L'inserimento di un elemento in uno stack nell'implementazione di un elenco collegato è diverso da quello di un'implementazione di array. Per inserire un elemento nello stack, sono necessari i seguenti passaggi.

1. Crea prima un nodo e allocagli memoria.
2. Se l'elenco è vuoto, l'elemento deve essere inserito 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à dei nodi nella lista, allora dobbiamo aggiungere il nuovo elemento all'inizio della lista (per non violare la proprietà dello stack). A questo scopo, assegnare l'indirizzo dell'elemento iniziale al campo indirizzo del nuovo nodo e rendere il nuovo nodo il nodo iniziale della lista.

Complessità temporale: o(1)





Implementazione C:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

Eliminazione di un nodo dallo stack (operazione POP)

L'eliminazione di un nodo dalla cima dello stack viene definita come pop operazione. L'eliminazione di un nodo dall'implementazione dell'elenco collegato dello stack è diversa da quella nell'implementazione dell'array. Per estrarre un elemento dallo stack, dobbiamo seguire i seguenti passaggi:

Verificare la condizione di underflow:La condizione di underflow si verifica quando proviamo a estrarre da uno stack già vuoto. Lo stack sarà vuoto se il puntatore head dell'elenco punta a null.Regolare di conseguenza il puntatore della testa:Nello stack gli elementi vengono estratti solo da un'estremità, pertanto il valore memorizzato nel puntatore head deve essere cancellato e il nodo deve essere liberato. Il nodo successivo del nodo testa diventa ora il nodo testa.

Complessità temporale: o(n)

Implementazione in C

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

Visualizzare i nodi (Attraversamento)

Per visualizzare tutti i nodi di uno stack è necessario attraversare tutti i nodi della lista concatenata organizzata sotto forma di stack. A questo scopo, dobbiamo seguire i seguenti passaggi.

1. Copia il puntatore head in un puntatore temporaneo.
2. Sposta il puntatore temporaneo attraverso tutti i nodi della lista e stampa il campo valore allegato ad ogni nodo.

Complessità temporale: o(n)

Implementazione C

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

Programma guidato da menu in C che implementa tutte le operazioni sullo stack utilizzando l'elenco collegato:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }