În loc să folosim matrice, putem folosi și lista legată pentru a implementa stiva. Lista legată alocă memoria în mod dinamic. Cu toate acestea, complexitatea timpului în ambele scenarii este aceeași pentru toate operațiunile, adică push, pop și peek.

În implementarea listelor legate de stive, nodurile sunt menținute necontiguu în memorie. Fiecare nod conține un pointer către nodul său imediat succesor din stivă. Se spune că stiva este depășită dacă spațiul rămas în heap-ul de memorie nu este suficient pentru a crea un nod.

comentariu multilinie Powershell

Cel mai mare nod din stivă conține întotdeauna null în câmpul său de adresă. Să discutăm despre modul în care, fiecare operație este efectuată în implementarea listelor conectate a stivei.

Adăugarea unui nod la stivă (operație Push)

Adăugarea unui nod la stivă se numește Apăsaţi Operațiune. Împingerea unui element într-o stivă în implementarea listelor legate este diferită de cea a implementării unui tablou. Pentru a împinge un element pe stivă, sunt implicați următorii pași.

1. Creați mai întâi un nod și alocați-i memorie.
2. Dacă lista este goală, atunci articolul trebuie să fie împins ca nod de pornire al listei. Aceasta include atribuirea valorii părții de date a nodului și atribuirea null părții de adresă a nodului.
3. Dacă există deja câteva noduri în listă, atunci trebuie să adăugăm noul element la începutul listei (pentru a nu încălca proprietatea stivei). În acest scop, atribuiți adresa elementului de pornire câmpului de adresă al noului nod și faceți noul nod, nodul de pornire al listei.

Complexitatea timpului: o(1)

conversia unui șir în întreg în java





Implementarea 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'); } } 

Ștergerea unui nod din stivă (operație POP)

Ștergerea unui nod din partea de sus a stivei este denumită pop Operațiune. Ștergerea unui nod din implementarea listei conectate a stivei este diferită de cea din implementarea matricei. Pentru a scoate un element din stivă, trebuie să urmăm următorii pași:

Verificați starea de debit:Condiția de underflow apare atunci când încercăm să ieșim dintr-o stivă deja goală. Stiva va fi goală dacă indicatorul de cap al listei indică nul.Reglați indicatorul de cap în consecință:În stivă, elementele sunt popped doar de la un capăt, prin urmare, valoarea stocată în indicatorul de cap trebuie ștearsă și nodul trebuie eliberat. Următorul nod al nodului principal devine acum nodul principal.

Complexitatea timpului: o(n)

Implementarea 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'); } } 

Afișează nodurile (Traversing)

Afișarea tuturor nodurilor unei stive necesită parcurgerea tuturor nodurilor listei legate organizată sub formă de stivă. În acest scop, trebuie să parcurgem următorii pași.

sfoară prea lungă

1. Copiați indicatorul de cap într-un indicator temporar.
2. Mutați indicatorul temporar prin toate nodurile listei și imprimați câmpul de valoare atașat fiecărui nod.

Complexitatea timpului: o(n)

C Implementarea

 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; } } } 

Program condus de meniu în C care implementează toate operațiunile stivei folosind lista legată:

 #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; } } }