Zásobník je známá datová struktura, která se většinou implementuje pomocí pole či spojového seznamu. V tomto článku si povíme, co to zásobník je, jeho základní princip a ukážeme si jak napsat zásobník používající pole v Javě.
Jak jsme si již řekli, tak zásobník je datová struktura - abstraktní datový typ, který se používá pro dočasné ukládání dat pomocí datového způsobu LIFO. LIFO znamená „Last In – First Out“ - neboli poslední přidaný prvek jde první ven. Tento způsob manipulace s daty je snadno pochopitelný. Poslední položka, která se do zásobníku přidá, vychází ze zásobníku jako první.
Je také potřeba myslet na to, že jakmile vloženou hodnotu použijeme, nebude již dostupná.
Snadno se to představí na samotném zásobníku, který je v pistoli. Náboj, který do zásobníku dáte jako poslední (bude nahoře), tak poté vystřelí (bude odebrán) jako první. Samozřejmě už nebude použitelný (dostupný), protože byl již použitý.
Za zmíňku také stojí to, že například Java či PostScript využívají zásobníkovou architekturu.
Implementace zásobníku do Javy:
public class Stack {
private int size;
private int top;
private int[] values;
public Stack(int size) {
this.size = size;
values = new int[size];
top = -1;
}
public void push(int i) {
if(!is_full()) {
top++;
values[top] = i;
} else
throw new UnsupportedOperationException("Stack is full!");
}
public int pop() {
int i = 0;
if(!is_empty()) {
i = values[top];
top--;
}
return i;
}
public boolean is_empty() {
if(top == -1)
return true;
else
return false;
}
public boolean is_full() {
if(top < size - 1)
return false;
else
return true;
}
}
Tak toto je třída, která obstarává zásobník pomocí pole. Samozřejmě by šlo zapsat lepší použitelnější zásobník, ale v tuto chvíli mi jde hlavně o snadnou pochopitelnost. Třída obsahuje 3 privátní proměnné - "size" velikost pole (zásobníku), "top" aktuální vrchol zásobníku a pole "vaules", což je vlastně pomocné pole. Ke konci třídy se nacházejí kontrolní metody, které testují plnost a prázdnost zásobníku. Už zbývají jen metody push a pop. Push a pop jsou typická jména těchto metod v použití zásobníku. Metodě push musíme předat vstupní argument, který uloží tato metoda do zásobníku (pokud není zásobník již plný). Metoda pop nám vypíše aktuální pozici a sníží vrchol (proměnnou top) o pozici dolů.
Malý příklad použití:
public class Main {
public static void main(String[] args) {
Stack zasobnik = new Stack(10);
zasobnik.push(12);
zasobnik.push(12345);
zasobnik.push(124);
for(int i = 0; i < 3;i++) {
System.out.println(zasobnik.pop());
}
}
}
Výpis by vypadal takto:
124
12345
12
Tento výpis je logicky pochopitelný podle manipulace s daty LIFO.
