V případě, že se rozhodneme využít jako prostoru pro uložení hodnot v zásobníku datový typ pole, musíme při inicializace stanovit jeho velikost. Konstruktor typu ArrayStack tedy bude mít jako parametr číslo označující maximální počet prvků, které budeme schopni do zásobníku uložit. Konstruktor vytvoří pole objektů _data se zadanou velikostí, všechny prvky tohoto pole budou inicializovány na hodnotu null. V proměnné _top budeme vždy udržovat index prvního volného prvku pole, takže na počátku ji necháme nastavenu na nulu - viz Obr. 3.3.
V operacích push(), pop() a top() si povšimněte toho, jakým způsobem je využito příkazu assert pro kontrolu toho, zda nedošlo k zaplnění celého zásobníku nebo naopak zda není zásobník prázdný. Pokud si potřebujete osvěžit, jak tento příkaz funguje, vraťte se k úvodní kapitole o jazyce Java, odstavci 2.7 o zpracování výjimek.
public class ArrayStack implements Stack
{
public ArrayStack(int size) {
assert size > 0;
_data = new Object[size];
}
public void push(Object obj) {
assert _top < _data.length : "Preteceni zasobniku";
_data[_top++] = obj;
}
public Object pop() {
assert _top > 0 : "Zasobnik je prazdny";
return _data[--_top];
}
public Object top() {
assert _top > 0 : "Zasobnik je prazdny";
return _data[_top-1];
}
public boolean empty() {
return _top == 0;
}
protected Object[] _data;
protected int _top;
}
A jakým způsobem teď můžeme třídu ArrayStack použít? Vytvoříme její instanci pomocí operátoru new a získanou referenci uložíme do proměnné typu Stack. Tím zajistíme, že zbytek programu bude pracovat pouze s operacemi abstraktního datového typu Stack a nebude závislý na konkrétní použité implementaci zásobníku.
class TestZasobniku {
public static void main(String args[]) {
Stack z = new ArrayStack(4);
System.out.println(z.empty());
z.push("a");
z.push("b");
z.push("c");
z.push("d");
// z.push("e");
while( !z.empty() ) {
System.out.print(z.pop()+" ");
}
System.out.println();
}
}
Spuštění testovacího programu bude vypadat následovně:
> java -ea TestZasobniku true d c b a
Pokud bychom do zásobníku vložili ještě jeden prvek navíc (stačí odstranit komentář), dosáhli bychom jeho přetečení a hlášení chyby.
> java -ea TestZasobniku true java.lang.AssertionError: Preteceni zasobniku at ArrayStack.push(ArrayStack.java:8) at TestZasobniku.main(TestZasobniku.java:9) Exception in thread "main"
Chybovou zprávu ovšem dostaneme i tehdy, pokud neumožníme parametrem -ea kontrolu splnění zadaných podmínek; v operaci push() se pak totiž budeme odkazovat na prvek s indexem směřujícím za konec pole _data.
> java -ea TestZasobniku true java.lang.ArrayIndexOutOfBoundsException: 4 at ArrayStack.push(ArrayStack.java:9) at TestZasobniku.main(TestZasobniku.java:9) Exception in thread "main"
V následujícím příkladu si ukážeme použití zásobníku pro výpočty s celočíselnými hodnotami v postfixové notaci. V jazyce Java ovšem narazíme na problém s objektovými a hodnotovými typy. Třída ArrayStack totiž předpokládá, že do zásobníku budeme umisťovat objekty, jejichž společným předkem je v jazyce Java třída Object. Vzhledem k tomu, že ale budeme pracovat s celočíselnými hodnotami, musíme při práci se zásobníkem dbát na správné konverze mezi objektovým typem Integer a hodnotovým typem int.
To je jistě nepříjemné, a proto např. autoři jazyka C# zvolili řešení, kdy je konverze zajištěna zcela transparentně (zde se jedná o typ Int32, který je pak ekvivalentem typu int a oba jsou tedy potomky třídy Object). Rozdělení na hodnotové a objektové datové typy je obvykle vedeno požadavky na efektivitu programů, neboť pracovat s běžnými numerickými typy jako s objekty by vedlo ke značným ztrátám časovým i prostorovým.
 | Příklad 3.4. |
Vytvořte třídu reprezentující celočíselný kalkulátor pracující v postfixové notaci a umožňující sčítání a odčítání čísel. Výpočet v postfixové notaci spočívá v tom, že před provedením aritmetické operace umístíme operandy na zásobník a po vyhodnocení operace je ze zásobníku odstraníme a nahradíme výsledkem. Při vkládání hodnoty na zásobník musíme vždy vytvořit nový objekt typu Integer, při odebírání získáme operací pop() referenci na objekt typu Object, kterou nejprve převedeme na typ Integer a pak voláním metody intValue() získáme hodnotu int. Odebrání hodnoty ze zásobníku a její konverzi zajistíme soukromou metodou popInt().
class PostfixovyKalkulator {
public void cislo(int x) {
zasobnik.push(new Integer(x));
}
public void soucet() {
int y = popInt();
int x = popInt();
zasobnik.push(new Integer(x+y));
}
public void rozdil() {
int y = popInt();
int x = popInt();
zasobnik.push(new Integer(x-y));
}
public int vysledek() {
return popInt();
}
private int popInt() {
Integer intObj = (Integer)zasobnik.pop();
return intObj.intValue();
}
private ArrayStack zasobnik = new ArrayStack(10);
}
|
Pro výpočet hodnoty výrazu 2 + 7 - 4 je pak třeba provést následující operace:
PostfixovyKalkulator kalk = new PostfixovyKalkulator();
kalk.cislo(2);
kalk.cislo(7);
kalk.soucet();
kalk.cislo(4);
kalk.rozdil();
System.out.println("Vysledek je " + kalk.vysledek());
Na podobném principu výpočtu se zásobníkem je založen soubor instrukcí, do kterého se překládají programy v jazycích Java i C#. Tento zásobníkový kód se pak přímo interpretuje nebo se ještě překládá do instrukcí konkrétního procesoru, na němž bude program spuštěn.