Lineární datové struktury
Zásobník
 Tisk

Zásobník


Abstraktní představa zásobníku je na obr. .

Sémantický význam

Dynamická lineární homogenní datová struktura, představovaná posloupností jednotlivých prvků. Prvky se do zásobníku ukládají v pořadí, jak přicházejí. Prvek, který byl do zásobníku uložen jako poslední, tvoří tzv. vrchol zásobníku (Top of Stack) a pouze ten je přístupný, případně je možno jej ze zásobníku vyjmout. Slovně lze zásobník charakterizovat výrokem „Poslední dovnitř, první ven“, anglicky „Last In First Out“, zkráceně LIFO, lidově pravidlo šíleného mlynáře ("Poslední přišel, první mlel"). Zásobník se použije tehdy, chceme-li dočasně uložit data tak, aby při jejich výběru byly zpracovány jako první ty, které přišly jako poslední.


Povolené operace:



Někdy bývají operace zpřístupnění a odstranění sloučeny do jedné (POP)


Implementace zásobníku se provádí:


Implementace zásobníku polem

Použije se tehdy, když víme, že velikost zásobníku bude menší než určitá hodnota nebo dokonce známe maximální velikost přesně.


Const

    Max = ... ; { Celé číslo, udávající max. počet prvků zásobníku}

Type

    TP = ... ; { Typ prvků, ukládaných do zásobníku }

    TZ = record

       POLE: array[1..Max] of TP; { Pole uložených prvků }

       VRCHOL:0..Max     { Index prvku na vrcholu zásobníku }

    end;


// Inicializace zásobníku.

Procedure INICIALIZUJ(var Z :TZ);

Begin

    Z.VRCHOL := 0

end;


// Přidání prvku do zásobníku.

Procedure INICIALIZUJ(var Z :TZ; P : TP);

Begin     with Z do

   if VRCHOL = MAX then write ('Přeplnění zásobníku')

   else begin

      VRCHOL := Succ(VRCHOL);

      POLE[VRCHOL] := P

   end

end;


// Test, je-li zásobník prázdný.

Function PRAZDNY(var Z : TZ) : Boolean;

Begin

    PRAZDNY := Z.VRCHOL = 0

end;


// Odstranění prvku ze zásobníku.

Procedure UBER(var Z : TZ);

Begin

    with Z do

     if PRAZDNY(Z) then write(' Zásobník je prázdný')

     else VRCHOL := pred(VRCHOL)

end;


// Zpřístupnění prvku na vrcholu zásobníku.

Procedure PRISTUP(var Z : TZ; var P : TP);

Begin

    with Z do

     if PRAZDNY(Z) then write(' Zásobník je prázdný')

     else P := POLE(VRCHOL)

end;


II) Implementace zásobníku zřetězenými dynamicky alokovanými proměnnými


Použije se tehdy, neznáme-li předem počet prvků, které se mohou do zásobníku uložit. Protože se pracuje jen s vrcholem zásobníku, potřebujeme jen jeden ukazatel. prvky však musí být rozšířeny o zpětný ukazatel na minulý prvek.


Type

    TP       = ... ; { Typ prvku. Může to být třeba záznam }

    UKAZ = ^Prvek;

    Prvek = record

       Hodnota : TP;

       Spoj      : UKAZ

    end;


// Inicializace zásobníku.

Procedure INICIALIZUJ(var Z : UKAZ);

Begin

    Z := nil;

end;


// Přidání prvku do zásobníku.

Procedure PRIDEJ(var Z : UKAZ; P : TP); { Z ukazuje na vrchol zásobníku }

Var

     Pom : UKAZ;

Begin

    New(Pom);     { Místo pro nový prvek }

    Pom^.Hodnota     := P; { Uložení hodnoty }

    Pom^.Spoj        := Z; { Spojka na předcházející prvek }

    Z                := Pom { Nový prvek je

end;


// Test, je-li zásobník prázdný.

Function PRAZDNY(var Z : TZ) : Boolean;

Begin

    PRAZDNY := Z = nil

end;


// Odstranění prvku z vrcholu zásobníku

Procedure UBER(var Z : UKAZ; var P : TP); { Z ukazuje na vrchol zásobníku }

Var

    Pom : UKAZ;

Begin

    if PRAZDNY(Z) then write(' Prázdný zásobník');

    else begin

        P      := Z^.Hodnota;

        Pom     := Z;

        Z     := Z^.Spoj;     { Posunutí vrcholu zásobníku }

        Dispose(Pom)     { Zrušení paměti s původním vrcholem }

    end

end;


// Zpřístupnění prvku na vrcholu zásobníku.

Procedure PRISTUP(var Z : UKAZ; var P : TP);

Begin

    if PRAZDNY(Z) then write(' Prázdný zásobník');

    else P := Z^.Hodnota

end;