In plaats van array te gebruiken, kunnen we ook een gekoppelde lijst gebruiken om stack te implementeren. Gekoppelde lijst wijst het geheugen dynamisch toe. De tijdscomplexiteit in beide scenario's is echter hetzelfde voor alle bewerkingen, d.w.z. push, pop en peek.

Bij een gekoppelde lijstimplementatie van een stapel worden de knooppunten niet-aaneengesloten in het geheugen bewaard. Elk knooppunt bevat een verwijzing naar het onmiddellijke opvolgerknooppunt in de stapel. Er wordt gezegd dat de stapel overstroomt als de resterende ruimte in de geheugenheap niet voldoende is om een ​​knooppunt te creëren.

uitzonderingsafhandeling in Java

Het bovenste knooppunt in de stapel bevat altijd null in zijn adresveld. Laten we de manier bespreken waarop elke bewerking wordt uitgevoerd in de gekoppelde lijstimplementatie van de stapel.

Een knooppunt aan de stapel toevoegen (Push-bewerking)

Het toevoegen van een knooppunt aan de stapel wordt aangeduid als duw operatie. Het pushen van een element naar een stapel in een gekoppelde lijstimplementatie is anders dan bij een array-implementatie. Om een ​​element op de stapel te duwen, zijn de volgende stappen nodig.

1. Maak eerst een knooppunt en wijs er geheugen aan toe.
2. Als de lijst leeg is, moet het item als startknooppunt van de lijst worden gepusht. Dit omvat het toekennen van waarde aan het datagedeelte van het knooppunt en het toekennen van nul aan het adresgedeelte van het knooppunt.
3. Als er al enkele knooppunten in de lijst staan, moeten we het nieuwe element aan het begin van de lijst toevoegen (om de eigenschap van de stapel niet te schenden). Wijs daartoe het adres van het startelement toe aan het adresveld van het nieuwe knooppunt en maak van het nieuwe knooppunt het startknooppunt van de lijst.

Tijdcomplexiteit: o(1)





C-implementatie:

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

Een knooppunt uit de stapel verwijderen (POP-bewerking)

Het verwijderen van een knooppunt van de bovenkant van de stapel wordt aangeduid als knal operatie. Het verwijderen van een knooppunt uit de gekoppelde lijstimplementatie van de stapel verschilt van dat in de array-implementatie. Om een ​​element uit de stapel te halen, moeten we de volgende stappen volgen:

Controleer op de onderstroomconditie:De underflow-toestand doet zich voor wanneer we proberen van een reeds lege stapel te knallen. De stapel is leeg als de hoofdaanwijzer van de lijst naar nul wijst.Pas de hoofdaanwijzer dienovereenkomstig aan:In de stapel worden de elementen slechts vanaf één kant gepopt. Daarom moet de waarde die is opgeslagen in de hoofdaanwijzer worden verwijderd en moet het knooppunt worden vrijgegeven. Het volgende knooppunt van het hoofdknooppunt wordt nu het hoofdknooppunt.

Tijdcomplexiteit: o(n)

C-implementatie

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

De knooppunten weergeven (doorkruisen)

Om alle knooppunten van een stapel weer te geven, moeten alle knooppunten van de gekoppelde lijst worden doorlopen, georganiseerd in de vorm van een stapel. Hiervoor moeten we de volgende stappen volgen.

1. Kopieer de hoofdaanwijzer naar een tijdelijke aanwijzer.
2. Verplaats de tijdelijke aanwijzer door alle knooppunten van de lijst en druk het waardeveld af dat aan elk knooppunt is gekoppeld.

Tijdcomplexiteit: o(n)

C-implementatie

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

Menugestuurd programma in C dat alle stapelbewerkingen implementeert met behulp van een gekoppelde lijst:

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