Zásobník

Zásobník (stack) je najdôležitejšia dátová štruktúra s obmedzeným prístupom. Pre zásobník je charakteristický spôsob narábania s údajmi – posledné uložené údaje budú čítané ako prvé. Preto sa používa taktiež výraz LIFO z anglického „Last In, First Out“. Vyžadujeme, aby implementácia zásobníka podporovala dve základné operácie: push (vlož prvok do zásobníka) a pop (vyber prvok zo zásobníka) Pre manipuláciu s uloženými dátovými položkami sa udržuje ukazovateľ zásobníka, ktorý udáva relatívnu adresu poslednej pridanej položky - vrchol zásobníka.

Zásobníky hrajú dôležitú úlohu pri syntaktickej analýze a konštrukcii prekladačov. Prvoradý význam majú pri realizovaní rekurzií, kde slúžia na zapamätávanie návratovej adresy. V praxi sa zásobníky realizujú ako jednorozmerné polia alebo lineárne spájané zoznamy.

^ TOP

Vizualizácia

^ TOP

Implementácia

  var stack:array[1.Max] of integer;
      head:integer;
  
  procedure push(v:integer); // pridaj
  begin
    stack[head]:=v; inc(head);
  end;
  
  function pop:integer;  // vyber
  begin
    dec(head); pop:=stack[head];
  end;
  
  procedure stack_init;  //vyprázdni
  begin
    head:=1;
  end;
  
  function stack_empty:boolean;  //či je prázdny
  begin
    stack_empty:=head=1;
  end; 
      

^ TOP