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