Algoritmy.net > Datové struktury > Zásobník
Zásobník
Zásobník
Zásobník (stack) je jednou ze základních datových struktur, která se využívá především pro dočasné ukládání dat v průběhu výpočtu. Zásobník data ukládá způsobem, kterému se říká LIFO - last in, first out - čili poslední vložený prvek jde na výstup jako první, předposlední jako druhý a tak dále. Opačným způsobem funguje datový typ fronta - FIFO - first in, first out.
Základní operace
Abstraktní datový typ zásobník specifikuje tyto operace:
- push - vloží prvek na vrch zásobníku
- pop - odstraní vrchol zásobníku
- top - dotaz na vrchol zásobníku
- isEmpty - dotaz na prázdnost zásobníku (size - dotaz na velikost zásobníku)
Využití
Zásobník se v informatice používá zejména pro ukládání stavu algoritmů a programů. Je použit v Tarjanově algoritmu, v prohledávání do hloubky a implicitně ve všech rekurzivních algoritmech. Na zásobníkové architektuře jsou postaveny virtuální stroje pro jazyky Java a Lisp.
Kód
/**
* Zasobnik
* Implementovan jako spojovy seznam
*/
public class Stack {
private Node first;
private int size;
public Stack() {
this.size = 0;
}
/**
* Ulozi prvek na vrch zasobniku
* Slozitost - O(1)
* @param i prvek k ulozeni
*/
public void push(int i) {
Node n = new Node(i);
Node currFirst = first;
first = n;
n.next = currFirst;
size++;
}
/**
* Odstrani vrchni prvek ze zasobniku
* Slozitost - O(1)
* @return hodnota vrchniho prvku
*/
public int pop() {
if (size == 0) {
throw new IllegalStateException("Zasobnik je prazdny, nelze odebrat prvek");
}
int value = first.value;
first = first.next;
size--;
return value;
}
/**
* Vrati vrchol zasobniku
* Slozitost - O(1)
* @return hodnota vrchniho prvku
*/
public int top() {
if (size == 0) {
throw new IllegalStateException("Zasobnik je prazdny, nelze vratit");
}
return first.value;
}
/**
* Vrati velikost zasobniku
* @return velikost zasobniku
*/
public int getSize() {
return this.size;
}
/**
* Klasicka toString metoda, vraci textovou reprezentaci objektu
* @return textova reprezentace objektu
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node curr = first;
for (int i = 0; i < this.size; i++) {
builder.append(curr.value).append(" ");
curr = curr.next;
}
return builder.toString();
}
/**
* Vnitrni trida reprezentujici uzel spojoveho seznamu
*/
private class Node {
private int value;
private Node next;
private Node(int value) {
this.value = value;
}
}
}
díky :-)