3.2. Zásobník

Obsah

3.2.1. Reprezentace zásobníku pomocí statického pole
3.2.2. Reprezentace zásobníku pomocí dynamického pole
3.2.3. Reprezentace zásobníku pomocí vázaného seznamu
3.2.4. Aplikace datového typu zásobník
3.2.5. Úlohy k řešení

Zásobník (stack) je dynamická datová struktura, která umožňuje postupné vkládání prvků a jejich odstraňování, ovšem v takovém pořadí, že naposledy vložený prvek můžeme odstranit jako první (last in - first out, LIFO). Nad zásobníkem můžeme provádět následující operace:

V případě, že se pokoušíme provést operaci pop nad prázdným zásobníkem, dojde k podtečení zásobníku. Naopak pokud budeme chtít do zaplněného zásobníku vložit operací push() další prvek, dojde k přetečení zásobníku.

Nyní se pokusme vytvořit specifikaci rozhraní zásobníku v jazyce Java. Vzhledem k tomu, že Java vyžaduje specifikaci datových typů všech proměnných, parametrů a návratových hodnot funkcí, narazíme ihned na problém. Jakého typu mohou být hodnoty uložené v zásobníku?

Zřejmě bychom rádi tento typ nadefinovali co nejobecněji tak, aby se vytvořený datový typ dal použít ve všech situacích. V jazyce Java nám to umožní předdefinovaný datový typ Object, představující bázový typ všech standardních i uživatelem definovaných tříd.

public interface Stack { 
	void    push(Object obj); 
	Object  pop(); 
	Object  top(); 
	boolean empty(); 
}

Máme-li k dispozici abstraktní rozhraní, můžeme k němu vytvořit jednu nebo více implementací. To znamená, že se nejprve musíme zamyslet nad tím, jak budeme zásobník realizovat. Můžeme se například rozhodnout pro ukládání hodnot do pole vhodné velikosti, nebo pro vytvoření dynamické datové struktury tvořené vzájemně propojenými objekty nesoucími konkrétní uloženou hodnotu.