Domů » Informatika » Datová struktura » Zásobník

Zásobník

Zásovník je datová struktura, která uchovává prvky v opačném pořadí, než v jakém byly do zásobníku vloženy (srovnej s frontou). První prvek v pořadí je tedy prvek, který byl do zásobníku vložen jako poslední. Toto chování se označuje anglickým akronymem LIFO (last in first out) – kdo přijde poslední, je obsloužen jako první.

Zásobník se v řadičích často objevuje jako hardwarový prvek podporující skoky do podprogramů a zpětné návraty (přístup „call-and-return“). Zásobníkovou architekturu využívají i některé interpretované programovací jazyky.

Implementace

Zásobník pomocí spojového seznamu (Java)

kód v jazyce Java - Zobrazit

  1. package demo;
  2.  
  3. /**
  4.  * Dynamický zásobník realizovaný pomocí seznamu.
  5.  * @author Vojtěch Hordějčuk
  6.  */
  7. public class LinkedStack<E>
  8. {
  9.   /**
  10.    * hlavička zásobníku
  11.    */
  12.   private Node<E> top;
  13.  
  14.   /**
  15.    * Vytvoří novou frontu.
  16.    */
  17.   public LinkedStack()
  18.   {
  19.     top = null;
  20.   }
  21.  
  22.   /**
  23.    * Ověří, zda je zásobník prázdný.
  24.    * @return TRUE právě když je zásobník prázdný
  25.    */
  26.   public boolean isEmpty()
  27.   {
  28.     return top == null;
  29.   }
  30.  
  31.   /**
  32.    * Vloží prvek na vrchol zásobníku.
  33.    * @param item vkládaný prvek
  34.    */
  35.   public void push(E item)
  36.   {
  37.     Node<E> newTop = new Node<E>(item);
  38.     newTop.append(top);
  39.     top = newTop;
  40.   }
  41.  
  42.   /**
  43.    * Odebere a vrátí vrchol zásobníku.
  44.    * @return bývalý vrchol zásobníků
  45.    */
  46.   public E pop()
  47.   {
  48.     if (isEmpty())
  49.     {
  50.       throw new RuntimeException();
  51.     }
  52.  
  53.     E headValue = top.getValue();
  54.     top = top.getNext();
  55.     return headValue;
  56.   }
  57.  
  58.   /**
  59.    * Prvek spojového seznamu.
  60.    * @param <E> třída hodnoty
  61.    */
  62.   private static class Node<E>
  63.   {
  64.     private E value;
  65.     private Node<E> next;
  66.  
  67.     protected Node(E value0)
  68.     {
  69.       value = value0;
  70.       next = null;
  71.     }
  72.  
  73.     protected E getValue()
  74.     {
  75.       return value;
  76.     }
  77.  
  78.     protected Node<E> getNext()
  79.     {
  80.       return next;
  81.     }
  82.  
  83.     protected void append(Node<E> next0)
  84.     {
  85.       next = next0;
  86.     }
  87.   }
  88. }

Reference