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

Java

/**
 * 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;
        }
    }
}

Základní operace

Využití

Kód

Doporučujeme