Abstraktní datové typy
Zásobník a fronta
 Vytisknout studijní materiál

Zásobník a fronta

Zásobník a fronta jsou dynamické množiny, pro které je specificky definována operace vybrání prvku z množiny.

Pro zásobník operace vyber ze zásobníku vyjme prvek, který byl operací vlož do zásobníku vložen jako poslední.

Tento postup se označuje termínem

last-in, first-out    LIFO

Pro frontu operace vyber z fronty vyjme prvek, který je ve frontě vložený nejdéle. Jinými slovy, z prvků, které jsou ve frontě vybere ten, který byl do fronty vložen jako první.

Tento postup se označuje termínem

first-in, first-out    FIFO

Obě tyto ADT jsou používány mnoha algoritmy na dalších úrovních abstrakce. Ukážeme si jejich implementaci pomocí pole a spojového seznamu.

Zásobník

S použitím zásobníku jsme se již setkali, když jsme uvedli, že JVM je zásobníkový stroj a ukázali jsme si jeho použití na vyhodnocování výrazů.

Dalším příkladem jeho použití je zpracování řádky textu na obrazovce tak, že

píšeme = přidáváme znak na konec řádky

mažeme - „backspace“ = odebereme poslední napsaný znak

V textu deklarace třídy se používají složené závorky. Kontrolu jejich vyváženého použití můžeme vykonat následujícím algoritmem.

Čti znaky textu a je-li znakem otvírací závorka, vlož ji do zásobníku. Je-li přečtený znak zavírací závorka potom, je-li zásobník prázdný ohlaš chybu „chybějící otvírací závorka“, jinak vyber prvek ze zásobníku. Jsou-li přečteny všechny znaky, potom je-li zásobník prázdný, závorky jsou vyváženy, jinak ohlaš chybu „chybějící zavírací závorka“.

V uvedených příkladem jsme používali zásobník jako ADT, tj. používali jsme operace vlož, vyber a test na zjištění je-li zásobník prázdný. Mlčky jsem předpokládali, že na začátku jeho používání byl zásobník prázdný. Uvedená použití budou správně pracovat pro jakoukoliv implementaci ADT zásobník.

Pro operace vlož a vyber se v anglické terminologii používají slova push a pop, která již téměř zdomácněla i v odborné češtině, podobně jako slova software a hardware.

Pro jednoduchost, bez ujmy na obecnosti, budeme se zabývat implementací zásobníku, do kterého vkládáme a z kterého vybíráme celá čísla. Pro implementaci takového zásobníku v Javě použijeme třídu IntZasobnik. Její rozhraní podle naší konvence je na obr..

Obsahuje tedy metody pro operace vytvoření prázdného zásobníku, test je-li zásobník prázdný, vložení prvku a výběr prvku. Test je-li zásobník prázdný, by jsme měli použít například před operací výběru prvku, nejsme-li si jisti zda nějaký prvek se v zásobníku nachází.

Implementace zásobníku pomocí pole

Imlementace třídy IntZasobnik pomocí pole je na obr..

Prvky zásobníku jsou uchovávány v poli z a proměnná vrchol udržuje hodnotu indexu, kam bude prvek vložen. Konstruktor vytváří pole velikosti maxN a nastaví hodnotu proměnné vrchol na 0, tedy vytvoří prázdný zásobník. Příklad klientské třídy Zasobnik je na obr..

Čas každé z operací nad zásobníkem implementovaným pomocí pole je O(1).

Když vykonáme operaci pop nad prázdným zásobníkem říkáme, že došlo k podtečení, underflow ,zásobníku. Obecně jde o chybový stav. V Javě lze na něj reagovat použitím mechanizmu výjimek.

Když vykonáme operaci push nad plným zásobníkem, tedy když vrchol = maxN říkáme, že došlo k přetečení, overflow, zásobníku. Jde o to, že jsme pro aplikaci dostatečně neodhadli potřebnou velikost zásobníku, na co lze opět reagovat pomocí mechanizmu výjimky. Alternativně může být velikost vytvářeného zásobníku parametrem konstruktoru. Velikost pole uchovávajícího prvky zásobníku lze podle potřeby měnit technikou dynamického rozšiřování pole, obr..

Myšlenka je založena na tom, že původní pole a bude referencováno také proměnnou x a na proměnné a vytvoříme větší pole, v našem případu dvakrát tak velké jako bylo pole původní. Hodnota žádného prvku pole a nyní není definována. Původní hodnoty skopírujeme z pole x. Pro ilustraci jsme přiřadili hodnoty ostatním prvkům pole a a vytiskli je. Nyní ovšem nebude každá operace vložení prvku O(1).

Pokud by vkládané hodnoty nebyly některého ze základních typů, ale objekty třídy, potom pole implementující zásobník bude deklarováno jako pole objektů, například jako pole sourozenci v článku 2.1.

Implementace zásobníku pomocí spojového seznamu

Jiný způsob jak překonat omezení dané pevnou velikostí pole, je použití spojového seznamu, který vytváří iluzi neomezené kapacity zásobníku. Třída IntZasobnik imlementující zásobník pomocí spojového seznamu je na obr. .

Prvky typu int jsou ukládány v objektech privátní třídy Prvek, která kromě členské proměnné klic pro klíč obsahuje členskou proměnnou dalsi pro spojování prvků. Zásobník reprezentuje proměnná vrchol, která obsahuje ukazatel na poslední vložený prvek, pokud tento existuje. Klientský program je stejný jako pro třídu IntZasobnik imlementující zásobník pomocí pole, obr..

Čas každé z operací nad zásobníkem implementovaným pomocí spojového seznamu je O(1).

Na implementaci zásobníku znaků nebo jiného typu prvků musíme změnit ve třídě IntZasobnik typ klice. Uvedený program můžeme použít také pro zásobník objektů nějaké třídy, kdy v objektech třídy Prvek nebude hodnota ukládaná do zásobníku, nýbrž reference na ukládaný objekt.Na obr. jsou do zásobníku ukládány prvky s referencí na objekty třídy Sourozenec.

Příklad klientského programu je na obr..

Méně vhodné řešení je rozšířit ukládaný objekt o členskou proměnnou dalsi, protože vyžaduje zásah do deklarace třídy ukládaných objektů.

Poznamenejme, že jazyk Java obsahuje obecnou implementaci zásobníku objektů - třídu Stack, jakož i některých dalších ADT. Použití třídy Stack si ukážeme v kapitole 10.

Zdůrazněme, že obě implementace ADT IntZasobnik můžeme vzájemně zaměnit bez jakékoliv změny klientského programu. Liší se vlastnostmi.

Implementace pomocí pole vyžaduje po celou dobu výpočtu paměť pro předpokládaný maximální počet prvků (pokud neuvažujeme dynamicky rozšiřované pole).

Implementace pomocí spojového seznamu vyžaduje paměťový prostor úměrný počtu uložených prvků. Navíc však potřebuje paměť pro uchovávání ukazatelů a čas na přidělení paměti při každé operaci push a nakonec čas na uvolnění paměti po každé operaci pop.

Fronta

Fronta je modelem každodenních situacích v bance, jídelně, šatně ap. Navíc je často využívána v operačních systémech, kde například požadavky na tisk jsou v serveru udržovány ve frontě.

Rozhraní fronty je až na jména metod stejné jako u zásobníku, obr..

Implementace fronty pomocí pole

Implementace fronty pomocí pole je na obr..

Z důvodu efektivnosti neposouváme ukládané prvky v poli, co by odpovídalo běžné zkušenosti, ale budeme udržovat dvě hodnoty indexů

zacatek - index odkud vybereme prvek

konec -index kam uložíme prvek

a frontu tvoří prvky mezi těmito indexy. Když hodnota indexu dosáhne konce pole může se vrátit na jeho začátek.

V případě, že fronta je prázdná nebo plná jsou si tyto indexy rovny. Kvůli jednoduchosti, vytvoříme pole pro implementaci fronty o 1 větší než maximální počet prvků fronty a rovnost indexů bude znamenat prázdné pole. Příklad klientského programu je na obr. .

Čas každé z operací nad frontou implementovanou pomocí pole je O(1).

Alternativně můžeme použít proměnnou pro počet prvků ve frontě, která se inkrementuje v operaci vloz a dekrementuje v operaci vyber a podle její hodnoty určit, je-li fronta prázdná nebo plná.

Implementace fronty pomocí spojového seznamu

Implementace fronty pomocí spojového seznamu je na obr..

Na rozdíl od zásobníku použijeme ukazatel konec na konec seznamu, kam prvky vkládáme a ukazatel zacatek na začátek seznamu, odkud prvky vybíráme. Klientský program je opět stejný jako pro implementaci pomocí pole, obr..

Čas každé z operací nad frontou implementovanou pomocí spojového seznamu je O(1).

Pro porovnání obou implementací fronty platí totéž co pro zásobník.