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í:
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;
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;