Fronta LIFO (Zásobník)

Z CHWiki

http://tutchek.igroup.cz/wiki/stack-ico.gif (angl. Stack)

Obsah 1 Popis 2 Příklad použití 3 Složitost 4 Algoritmy 4.1 Push 4.2 Pop 5 Implementace

[editovat] Popis

Zásobník je impelementací fronty typu LIFO (last in - first out). Nové prvky se přidávají vždy na vrchol. Ze zásobníku se odebírá vždy z vrcholu.

[editovat] Příklad použití

Úloha: Rozhodněte, zda je posloupnost závorek "({{{{((([[]])))}}}})" správně uzávorkovaná nebo ne. Řešení:

1. Vezmeme první znak řetězce.
2. Pokud je to otevírací závorka "([{", umístíme ji do zásobníku.
3. Pokud je to zavírací závorka "}])", podíváme se do zásobníku, zda je na vrcholu odpovídající otevírací závorka. Pokud ano odebereme ze zásobníku otevírací závorku a pokračujeme. Pokud ne končíme s chybou "špatně uzávorkováno".
4. Pokud nejsme na konci, vezmeme další znak řetězce a pokračujeme krokem 2.
5. Pokud je zásobník není prázdný, končíme s chybou "špatně uzávorkováno".
6. Řetězec je správně uzávorkovaný

[editovat] Složitost

• Push - vložení do zásobníku - O(1)
• Pop - vyjmutí ze zásobníku - O(1)

[editovat] Algoritmy

Zásobník je v poli P, index pro nově přidávaný prvek je v proměnné V. (P je indexováno od 0, výchozí hodnota V = 0)

[editovat] Push

Vkládáme prvek X

1. P(V) = X
2. V = V + 1

[editovat] Pop

Odebíráme vrchol

1. Pokud V = 0, chyba "zásobník prázdný", skonči.
2. Vrať P(V - 1)
3. V = V - 1

[editovat] Implementace

Zásobník se dá s úspěchem implementovat v poli. Potřebujeme tedy pole P a proměnnou int vrchol, která označuje index pro přidání dalšího prvku.