Linked list implementace stack

místo použití array, můžeme také použít linked list implementovat stack. Propojený seznam přiděluje paměť dynamicky. Časová složitost v obou scénářích je však stejná pro všechny operace, tj.

v linked list implementaci zásobníku jsou uzly udržovány nesouvislě v paměti. Každý uzel obsahuje ukazatel na svůj okamžitý nástupnický uzel v zásobníku. Zásobník se říká, že je přetečen, pokud prostor v haldě paměti nestačí k vytvoření uzlu.

nejvyšší uzel v zásobníku vždy obsahuje null ve svém adresním poli. Pojďme diskutovat o způsobu, jakým je každá operace prováděna v propojeném seznamu implementace zásobníku.

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

přidání uzlu do zásobníku se označuje jako operace push. Posunutí prvku do zásobníku v implementaci propojeného seznamu se liší od implementace pole. Za účelem zatlačení prvku na stoh se jedná o následující kroky.

1. nejprve vytvořte uzel a přidělte mu paměť.
2. pokud je seznam prázdný, má být položka tlačena jako počáteční uzel seznamu. To zahrnuje přiřazení hodnoty datové části uzlu a přiřazení null adresové části uzlu.
3. Pokud tam jsou některé uzly v seznamu už, pak musíme přidat nový prvek na začátek seznamu (není porušit vlastnost zásobníku). Za tímto účelem přiřaďte adresu počátečního prvku do adresního pole nového uzlu a vytvořte nový uzel, počáteční uzel seznamu.

časová Složitost : o(1)



C provedení :

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

Odstranění uzel z vrcholu zásobníku je označován jako pop provoz. Odstranění uzlu z implementace propojeného seznamu zásobníku se liší od implementace pole. Aby se pop prvek ze zásobníku, musíme postupovat podle následujících kroků :

1. Zkontrolujte, zda pro podkročení stavu: podkročení stavu dochází, když se snažíme pop z prázdného zásobníku. Zásobník bude prázdný, pokud ukazatel hlavy seznamu ukazuje na null.
2. Upravit hlavu ukazatel způsobem: V zásobníku, prvky jsou odebrány pouze z jednoho konce, tedy hodnoty uložené v hlavě ukazatel musí být odstraněny a uzel musí být osvobozen. Další uzel uzlu hlavy se nyní stává uzlem hlavy.

Časová Složitost : o(n)

C provádění

Zobrazit uzly (Křížení)

Zobrazení všech uzlů ze zásobníku potřebuje křížení všech uzlů spojového seznamu organizovány 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)

implementace C

program řízený Menu v C implementuje všechny operace zásobníku pomocí propojeného seznamu :