Frontazas

1. Fronta -

Fronta (kolejka)
odebírá se ze začátku fronty,
přidává se na konec fronty.
Datová struktura typu FIFO
a) Implementace s využitím statických
struktur (pole)
b) Implementace s využitím dynamických
struktur (spojového seznamu)

2. a) s využitím statických struktur

Definice a deklarace:
type COSI = string[10];
{popř. COSI=real apod.}
PP = 10;
FRONTA = array[1..PP] of COSI;
Var F1 : FRONTA;
ZAC, KON : byte;
PRVEK : COSI;
Přidej prvek do fronty:
begin KON:=KON+1;
KON:=0;
F1[KON]:= PRVEK
ZAC:=1
end
Odeber prvek z fronty:
begin PRVEK:=F1[1];
for I:=2 to KON do F1[I-1]:=F1[I]
end

3. Snímek 3

Uvedené řešení je spíše manuální
záležitost, jediná starost je o stav, kdy
fronta je plná (KON=PP - nedá se přidat)
popř. prázdná (KON=0 - nedá se odebrat)
Efekt přináší použití fronty v podobě kruhu,
kdy kromě výše uvedených proměnných
deklarujeme ještě proměnnou
var POC: byte
udržující informaci o počtu zákazníků ve
frontě (POC <= PP).

4. Snímek 4

Pak přídání prvku do fronty řeší algoritmus
begin KON:=(KON+1) mod 10;
F1[KON]:=PRVEK;
POC:=POC+1
end
a odebrání prvku z fronty řeší algoritmus
begin PRVEK:=F1[ZAC];
ZAC:=(ZAC+1) mod 10;
POC:=POC-1
end
Výchozí nastavení KON:=0; ZAC:=1; POC:=0 a starost,
aby hodnota POC byla v intervalu 1..PP (ovšem nabývat
hodnot může z intervalu 0..PP+1.

5. b) s využitím dynamických struktur

type FRONTA = record
F1
ZAC
ZAC:WSKAZ;
KON
KON:WSKAZ
end
nil
ZAC - START
KON - ILOSC
Type
var
COSI = string[10];
WSKAZ = ^STRU;
STRU = record IM
WSK
end;
F1 : FRONTA;
: COSI;
: WSKAZ

6. Snímek 6

Úvodní inicializaci fronty řeší algoritmus
Procedure INIT;
begin new(F1.ZAC);
F1.ZAC^.WSK:=nil;
F1.KON:=F1.ZAC
end
F1
ZAC
nil
KON

7. Snímek 7

Přidání prvku do fronty řeší algoritmus
Procedure PRIDEJ(R:COSI);
begin F1.KON^.IM:=R;
new(F1.KON^.WSK);
F1.KON:=F1.KON^.WSK;
F1.KON^.WSK:=nil
end

8. Snímek 8

Odebrání prvku z fronty řeší algoritmus
Procedure ODEBER(var R:COSI);
var POM : WSKAZ;
begin
if F1.ZAC<>F1.KON then
begin R:=F1.ZAC^.IM;
POM:=F1.ZAC ;
F1.ZAC:=F1.ZAC^.WSK;
dispose(POM)
end

9. Snímek 9

Schematicky lze přidání prvku do fronty znázornit:
F1
ZAC
KON
(3)
(3)
(2)
nil
nil
(1)
R
(4)
Schematicky lze odebrání prvku z fronty znázornit:
F1
KON
(3)
(3)
nil
(2)
POM
ZAC
(4)
R
(1)

10. Zásobník (stos) -

přidává se i odebírá vždy
TOP
nil
z vrcholu zásobníku.
Datová struktura typu
LIFO
a) Implementace s
využitím statických
struktur (pole)
b) Implementace s
využitím
dynamických
struktur (spojového
seznamu)

11. a) s využitím statických struktur

Definice a deklarace:
type COSI = string[10];
{popř. COSI=real apod.}
FRONTA = array[1..PP] of COSI;
var Z1
: FRONTA;
VRCH : byte;
PRVEK : COSI;
Přidej prvek do zásobníku: begin VRCH:=VRCH+1;
VRCH:=0;
Z1[VRCH]:= PRVEK
end
Odeber prvek z fronty:
begin PRVEK:=Z1[VRCH];
VRCH :=VRCH-1
end

12. b) s využitím dynamických struktur

Z1
nil
Type
var
COSI = string[10];
WSKAZ = ^STRU;
STRU = record IM
WSK
end;
Z1 : WSKAZ;
: COSI;
: WSKAZ

13. Snímek 13

Úvodní inicializaci zásobníku řeší algoritmus
Procedure INIT;
begin Z1:= nil;
end
Přidání prvku do zásobníku řeší algoritmus
Procedure VLOZ(R:COSI);
var POM : WSKAZ;
begin new(POM);
POM^.IM :=R;
POM^.WSK:=Z1;
Z1
:=POM
end

14. Snímek 14

Odebrání prvku ze zásobníku řeší
Procedure ODEBER(var R:COSI);
var POM : WSKAZ;
begin R :=Z1^.IM;
POM:=Z1;
Z1 := Z1^.WSK;
dispose(POM)
end

15. Snímek 15

Jak u fronty, tak u zásobníku, je třeba hlídat,
zda není prázdný. U zásobníku je
algoritmus ve tvaru
Function JePrazdny : Boolean;
begin if Z1=nil
then JePrazdny := true
else JePrazdny := false
end