TechCodeview

Namiesto použitia poľa môžeme na implementáciu zásobníka použiť aj prepojený zoznam. Prepojený zoznam dynamicky prideľuje pamäť. Časová zložitosť v oboch scenároch je však rovnaká pre všetky operácie, t. j. push, pop a peek.

V implementácii prepojeného zoznamu zásobníka sú uzly udržiavané nesúvisle v pamäti. Každý uzol obsahuje smerník na svoj bezprostredný následnícky uzol v zásobníku. O zásobníku sa hovorí, že je preplnený, ak miesto v halde pamäte nestačí na vytvorenie uzla.

čísla pre abecedu

Najvrchnejší uzol v zásobníku vždy obsahuje vo svojom poli adresy hodnotu null. Poďme diskutovať o spôsobe, akým sa každá operácia vykonáva v implementácii prepojeného zoznamu zásobníka.

Pridanie uzla do zásobníka (operácia Push)

Pridanie uzla do zásobníka sa označuje ako TAM prevádzka. Vloženie prvku do zásobníka v implementácii prepojeného zoznamu sa líši od implementácie poľa. Na zatlačenie prvku na stoh sú potrebné nasledujúce kroky.

1. Najprv vytvorte uzol a prideľte mu pamäť.
2. Ak je zoznam prázdny, položka sa má tlačiť ako počiatočný uzol zoznamu. To zahŕňa priradenie hodnoty dátovej časti uzla a priradenie hodnoty null adresovej časti uzla.
3. Ak už sú v zozname nejaké uzly, potom musíme pridať nový prvok na začiatok zoznamu (aby sa neporušila vlastnosť zásobníka). Na tento účel priraďte adresu počiatočného prvku do poľa adresy nového uzla a urobte z nového uzla počiatočný uzol zoznamu.

Časová zložitosť: o(1)

awt java





C implementácia:

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

Odstránenie uzla zo zásobníka (operácia POP)

Odstránenie uzla z vrcholu zásobníka sa označuje ako pop prevádzka. Odstránenie uzla z implementácie prepojeného zoznamu zásobníka sa líši od toho v implementácii poľa. Aby sme vybrali prvok zo zásobníka, musíme postupovať podľa nasledujúcich krokov:

Skontrolujte stav podtečenia:Stav podtečenia nastane, keď sa pokúsime vyskočiť z už prázdneho zásobníka. Ak hlavný ukazovateľ zoznamu ukazuje na hodnotu null, zásobník bude prázdny.Podľa toho nastavte ukazovateľ hlavy:V zásobníku sú prvky vyskakované iba z jedného konca, preto je potrebné vymazať hodnotu uloženú v ukazovateli hlavy a uvoľniť uzol. Ďalší uzol hlavného uzla sa teraz stane hlavným uzlom.

Časová zložitosť: o(n)

C implementácia

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

Zobraziť uzly (prechádzanie)

Na zobrazenie všetkých uzlov zásobníka je potrebné prejsť všetkými uzlami prepojeného zoznamu usporiadaného vo forme zásobníka. Na tento účel musíme postupovať podľa nasledujúcich krokov.

reťazec.podreťazec java

1. Skopírujte ukazovateľ hlavy do dočasného ukazovateľa.
2. Presuňte dočasný ukazovateľ cez všetky uzly zoznamu a vytlačte pole hodnoty pripojené ku každému uzlu.

Časová zložitosť: o(n)

C Implementácia

 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 riadený menu v C implementujúci všetky operácie zásobníka pomocou prepojeného zoznamu:

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