TechCodeview

Namesto uporabe niza lahko za implementacijo sklada uporabimo tudi povezani seznam. Povezani seznam dinamično dodeli pomnilnik. Vendar pa je časovna zapletenost v obeh scenarijih enaka za vse operacije, tj. potiskanje, pokanje in pokukanje.

Pri implementaciji sklada s povezanim seznamom se vozlišča v pomnilniku vzdržujejo neprekinjeno. Vsako vozlišče vsebuje kazalec na vozlišče svojega neposrednega naslednika v skladu. Sklad naj bi bil prelit, če v kopici pomnilnika ni dovolj prostora za ustvarjanje vozlišča.

Najvišje vozlišče v skladu vedno vsebuje nič v naslovnem polju. Razpravljajmo o tem, kako se izvaja vsaka operacija v implementaciji sklada povezanega seznama.

instanceof

Dodajanje vozlišča v sklad (potisna operacija)

Dodajanje vozlišča v sklad se imenuje potiskati delovanje. Potiskanje elementa v sklad v izvedbi povezanega seznama se razlikuje od izvajanja matrike. Da potisnete element na sklad, so vključeni naslednji koraki.

1. Najprej ustvarite vozlišče in mu dodelite pomnilnik.
2. Če je seznam prazen, je treba element potisniti kot začetno vozlišče seznama. To vključuje dodeljevanje vrednosti podatkovnemu delu vozlišča in dodelitev ničle naslovnemu delu vozlišča.
3. Če je na seznamu že nekaj vozlišč, moramo dodati nov element na začetek seznama (da ne kršimo lastnosti sklada). V ta namen dodelite naslov začetnega elementa naslovnemu polju novega vozlišča in naredite novo vozlišče začetno vozlišče seznama.

Časovna zahtevnost: o(1)





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

Brisanje vozlišča iz sklada (operacija POP)

Brisanje vozlišča z vrha sklada se imenuje pop delovanje. Brisanje vozlišča iz implementacije sklada povezanega seznama se razlikuje od tistega v implementaciji matrike. Če želimo element odstraniti iz sklada, moramo slediti naslednjim korakom:

Preverite stanje pretoka:Pogoj underflow se pojavi, ko poskušamo poskočiti iz že praznega sklada. Sklad bo prazen, če kazalec glave seznama kaže na nič.Ustrezno prilagodite kazalec glave:V skladu se elementi izločijo samo z enega konca, zato je treba vrednost, shranjeno v kazalcu glave, izbrisati in vozlišče osvoboditi. Naslednje vozlišče glavnega vozlišča zdaj postane glavno vozlišče.

Časovna zahtevnost: o(n)

C izvedba

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

Prikažite vozlišča (Traversing)

Za prikaz vseh vozlišč sklada je treba prečkati vsa vozlišča povezanega seznama, organiziranega v obliki sklada. V ta namen moramo slediti naslednjim korakom.

dobiti povezavo

1. Kopirajte kazalec glave v začasni kazalec.
2. Premaknite začasni kazalec skozi vsa vozlišča seznama in natisnite polje vrednosti, ki je priloženo vsakemu vozlišču.

Časovna zahtevnost: o(n)

C Izvedba

 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 v jeziku C, ki ga poganja meni, izvaja vse operacije sklada z uporabo povezanega seznama:

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