Umjesto korištenja niza, također možemo koristiti povezani popis za implementaciju stoga. Povezani popis dinamički dodjeljuje memoriju. Međutim, vremenska složenost u oba scenarija ista je za sve operacije, tj. push, pop i peek.

U implementaciji stoga povezanog popisa, čvorovi se održavaju u memoriji bez kontinuiteta. Svaki čvor sadrži pokazivač na njegov neposredni nasljedni čvor u stogu. Za stog se kaže da je preplavljen ako preostalo mjesto u memorijskoj gomili nije dovoljno za stvaranje čvora.

cijepanje niza u c++

Najviši čvor u stogu uvijek sadrži null u svom adresnom polju. Raspravljajmo o načinu na koji se svaka operacija izvodi u implementaciji stoga povezane liste.

Dodavanje čvora u stog (Push operacija)

Dodavanje čvora u stog se naziva gurnuti operacija. Guranje elementa na stog u implementaciji povezanog popisa razlikuje se od implementacije polja. Da biste gurnuli element na stog, uključeni su sljedeći koraci.

1. Prvo stvorite čvor i dodijelite mu memoriju.
2. Ako je popis prazan, stavku treba gurnuti kao početni čvor popisa. Ovo uključuje dodjeljivanje vrijednosti podatkovnom dijelu čvora i dodjeljivanje nule adresnom dijelu čvora.
3. Ako već postoje neki čvorovi na popisu, tada moramo dodati novi element na početak popisa (kako ne bismo narušili svojstvo steka). U tu svrhu dodijelite adresu početnog elementa adresnom polju novog čvora i učinite novi čvor početnim čvorom liste.

Vremenska složenost: o(1)





C implementacija:

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

Brisanje čvora sa stoga (POP operacija)

Brisanje čvora s vrha stoga naziva se pop operacija. Brisanje čvora iz implementacije povezanog popisa stoga razlikuje se od onoga u implementaciji polja. Kako bismo izbacili element iz stoga, moramo slijediti sljedeće korake:

Provjerite stanje donjeg protoka:Underflow stanje se događa kada pokušamo iskočiti iz već praznog snopa. Stog će biti prazan ako glavni pokazivač liste pokazuje na nulu.U skladu s tim prilagodite pokazivač glave:U stogu se elementi izbacuju samo s jednog kraja, stoga se vrijednost pohranjena u pokazivaču glave mora izbrisati i čvor se mora osloboditi. Sljedeći čvor glavnog čvora sada postaje glavni čvor.

Vremenska složenost: o(n)

besplatni protiv besplatnih

C implementacija

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

Prikaz čvorova (Traversing)

Prikaz svih čvorova hrpe zahtijeva prolazak kroz sve čvorove povezane liste organizirane u obliku hrpe. U tu svrhu moramo slijediti sljedeće korake.

1. Kopirajte pokazivač glave u privremeni pokazivač.
2. Pomaknite privremeni pokazivač kroz sve čvorove popisa i ispišite polje vrijednosti pridruženo svakom čvoru.

Vremenska složenost: o(n)

C Implementacija

 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 vođen izbornicima u C-u koji implementira sve operacije stoga pomoću povezanog popisa:

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