Místo použití pole můžeme také použít propojený seznam k implementaci zásobníku. Propojený seznam dynamicky přiděluje paměť. Časová složitost v obou scénářích je však stejná pro všechny operace, tj. push, pop a peek.

V implementaci propojeného seznamu zásobníku jsou uzly udržovány nesouvisle v paměti. Každý uzel obsahuje ukazatel na svůj bezprostřední následník v zásobníku. Říká se, že zásobník je přeplněný, pokud místo zbývající v haldě paměti nestačí k vytvoření uzlu.

Nejvyšší uzel v zásobníku vždy obsahuje ve svém poli adresy hodnotu null. Pojďme diskutovat o způsobu, jakým se každá operace provádí v implementaci propojeného seznamu zásobníku.

Přidání uzlu do zásobníku (operace Push)

Přidání uzlu do zásobníku se nazývá TAM úkon. Vložení prvku do zásobníku v implementaci propojeného seznamu se liší od implementace pole. Aby bylo možné zatlačit prvek na stoh, je třeba provést následující kroky.

jak převést řetězec na int v java

1. Nejprve vytvořte uzel a přidělte mu paměť.
2. Pokud je seznam prázdný, má být položka posunuta jako počáteční uzel seznamu. To zahrnuje přiřazení hodnoty datové části uzlu a přiřazení hodnoty null adresové části uzlu.
3. Pokud již v seznamu nějaké uzly jsou, pak musíme přidat nový prvek na začátek seznamu (aby nedošlo k porušení vlastnosti zásobníku). Za tímto účelem přiřaďte adresu počátečního prvku do pole adresy nového uzlu a udělejte z nového uzlu počáteční uzel seznamu.

Časová složitost: o(1)





C implementace:

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

Odstranění uzlu ze zásobníku (operace POP)

Odstranění uzlu z vrcholu zásobníku se nazývá pop úkon. Odstranění uzlu z implementace propojeného seznamu zásobníku se liší od odstranění v implementaci pole. Abychom mohli vyjmout prvek ze zásobníku, musíme provést následující kroky:

Zkontrolujte stav podtečení:Stav podtečení nastane, když se pokusíme vyskočit z již prázdného zásobníku. Pokud hlavní ukazatel seznamu ukazuje na hodnotu null, zásobník bude prázdný.Podle toho nastavte ukazatel hlavy:V zásobníku jsou prvky vyskakovány pouze z jednoho konce, proto je třeba smazat hodnotu uloženou v ukazateli hlavy a uvolnit uzel. Další uzel hlavního uzlu se nyní stává hlavním uzlem.

Časová složitost: o(n)

C implementace

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

Zobrazit uzly (Traversing)

Zobrazení všech uzlů zásobníku vyžaduje procházení všech uzlů propojeného seznamu organizovaného ve formě zásobníku. Za tímto účelem musíme postupovat podle následujících kroků.

1. Zkopírujte ukazatel hlavy do dočasného ukazatele.
2. Přesuňte dočasný ukazatel přes všechny uzly seznamu a vytiskněte pole hodnoty připojené ke každému uzlu.

Časová složitost: o(n)

C Implementace

 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 řízený menu v C implementující všechny operace se zásobníkem pomocí propojeného seznamu:

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