TechCodeview

I stedet for at bruge array, kan vi også bruge linked list til at implementere stack. Sammenkædet liste allokerer hukommelsen dynamisk. Imidlertid er tidskompleksiteten i begge scenarier den samme for alle operationer, dvs. push, pop og kig.

I linked list-implementering af stak opretholdes noderne ikke-sammenhængende i hukommelsen. Hver knude indeholder en pointer til dens umiddelbare efterfølgerknude i stakken. Det siges, at stakken flyder over, hvis pladsen tilbage i hukommelsesbunken ikke er nok til at skabe en node.

Den øverste node i stakken indeholder altid null i sit adressefelt. Lad os diskutere den måde, hvorpå hver operation udføres i en linket listeimplementering af stak.

Tilføjelse af en node til stakken (Push-operation)

Tilføjelse af en node til stakken kaldes skubbe operation. At skubbe et element til en stak i en linket listeimplementering er forskellig fra en arrayimplementering. For at skubbe et element ind på stakken er følgende trin involveret.

1. Opret først en node og allokér hukommelse til den.
2. Hvis listen er tom, skal elementet skubbes som startknudepunktet på listen. Dette inkluderer tildeling af værdi til datadelen af ​​noden og tildeling af nul til adressedelen af ​​noden.
3. Hvis der allerede er nogle noder på listen, så er vi nødt til at tilføje det nye element i begyndelsen af ​​listen (for ikke at krænke stakkens egenskaber). Til dette formål skal du tildele startelementets adresse til adressefeltet på den nye node og gøre den nye node til listens startknude.

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

Sletning af en node fra stakken (POP-operation)

Sletning af en node fra toppen af ​​stakken kaldes pop operation. Sletning af en node fra den linkede listeimplementering af stak er forskellig fra den i arrayimplementeringen. For at få et element ud af stakken, skal vi følge følgende trin:

Tjek for underløbstilstanden:Underløbstilstanden opstår, når vi forsøger at springe fra en allerede tom stak. Stakken vil være tom, hvis hovedmarkøren på listen peger på null.Juster hovedmarkøren i overensstemmelse hermed:I stakken bliver elementerne kun poppet fra den ene ende, derfor skal værdien gemt i hovedmarkøren slettes, og noden skal frigøres. Den næste knude i hovedknuden bliver nu hovedknuden.

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

Vis noderne (Traversing)

Visning af alle noderne i en stak skal gennemløbe alle noderne på den sammenkædede liste organiseret i form af stak. Til dette formål skal vi følge følgende trin.

1. Kopier hovedmarkøren til en midlertidig markør.
2. Flyt den midlertidige markør gennem alle noderne på listen, og udskriv værdifeltet, der er knyttet til hver node.

Tidskompleksitet: o(n)

C Implementering

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

Menudrevet program i C, der implementerer alle stak-operationer ved hjælp af linket liste:

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