Istället för att använda array kan vi också använda länkad lista för att implementera stack. Länkad lista allokerar minnet dynamiskt. Tidskomplexiteten i båda scenarierna är dock densamma för alla operationer, dvs push, pop och peek.

I länkad listimplementering av stack, bibehålls noderna icke-angränsande i minnet. Varje nod innehåller en pekare till dess omedelbara efterföljande nod i stacken. Stack sägs vara över om det utrymme som finns kvar i minneshögen inte räcker för att skapa en nod.

Den översta noden i stacken innehåller alltid null i adressfältet. Låt oss diskutera det sätt på vilket varje operation utförs i länkad listimplementering av stack.

Lägga till en nod till stacken (Push-operation)

Att lägga till en nod till stacken kallas skjuta på drift. Att skjuta ett element till en stack i en länkad listimplementering skiljer sig från det för en arrayimplementering. För att skjuta upp ett element på stapeln är följande steg involverade.

Skådespelerskan Rubina Dilaik

1. Skapa först en nod och allokera minne till den.
2. Om listan är tom ska objektet tryckas som startnod för listan. Detta inkluderar att tilldela värde till datadelen av noden och tilldela noll till adressdelen av noden.
3. Om det redan finns några noder i listan måste vi lägga till det nya elementet i början av listan (för att inte bryta mot stackens egenskap). För detta ändamål, tilldela startelementets adress till den nya nodens adressfält och gör den nya noden till listans startnod.

Tidskomplexitet: o(1)





C implementering:

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

Ta bort en nod från stacken (POP-operation)

Att ta bort en nod från toppen av stacken kallas pop drift. Att ta bort en nod från den länkade listimplementeringen av stack skiljer sig från den i arrayimplementeringen. För att poppa ett element från stacken måste vi följa följande steg:

Kontrollera underflödet:Underflödestillståndet uppstår när vi försöker hoppa från en redan tom stack. Stacken kommer att vara tom om huvudpekaren på listan pekar på null.Justera huvudpekaren därefter:I stack poppas elementen endast från ena änden, därför måste värdet som lagrats i huvudpekaren tas bort och noden måste frigöras. Nästa nod i huvudnoden blir nu huvudnoden.

Tidskomplexitet: o(n)

C implementering

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

Visa noderna (traversering)

Att visa alla noder i en stack måste genomkorsa alla noder i den länkade listan organiserade i form av stack. För detta ändamål måste vi följa följande steg.

1. Kopiera huvudpekaren till en tillfällig pekare.
2. Flytta den tillfälliga pekaren genom alla noder i listan och skriv ut värdefältet som är kopplat till varje nod.

Tidskomplexitet: o(n)

C Genomförande

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

Menydrivet program i C som implementerar alla stackoperationer med hjälp av länkad lista:

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