Rijen en stapels - Wiskunst

Twee veel voorkomende zaken betreffende pointers zijn de rijen (queue’s) en stapels (stack’s).

Een rij kun je vergelijken met bijvoorbeeld een rij bij het postkantoor. Achteraan aansluiten en wachten tot je de voorste bent, en dus hopelijk aan de beurt. Een rij werkt volgens het zogenaamde FIFO-systeem; First In First Out. De meeste pre-emptive besturingssystemen werken met een rij (van uit te voeren opdrachten).

Een stapel kun je vergelijken met een bonnen-pin op een toonbank van een winkel. De laatste bon komt bovenaan de pin. Na sluitingstijd zal de winkeleigenaar de pin van bovenaf weer leeghalen. Een stapel werkt volgens het zogenaamde LIFO-systeem; Last In First Out. De stapel wordt onder meer gebruikt bij recursieve procedures en functies.

De pointer-structuur in Pascal leent zich uitstekend om de rij en de stapel te implementeren.

De rij.

Als eerste gaan we naar de rij kijken. We definieren een kop en een staart en een koppeling van links naar rechts, en een aantal bewerkingen.
De rij kun je je schematisch als volgt voorstellen:

kop staart
1^e element→2^e element→ 3^e element→4^e element→ …

De bewerkingen die we willen hebben zijn:

een item aan de rij toevoegen
een item van de rij afhalen
(alle elementen zien)

Ad 1: een item toevoegen.

Om een item aan de rij toe te voegen doorlopen we de volgende stappen:

Maak en vul een nieuw item (huidige), waarbij het veld volgende nil moet zijn
Als de kop nil is, maak de kop gelijk aan huidige (is nu de eerste)
Als de staart niet nil is, maak dan staart^.volgende gelijk aan huidige (staart is nl. nog het laatste element!)
Maak staart gelijk aan huidige (want huidige moet laatste element zijn.

Ad 2: een item afhalen.

Om een item uit de rij te halen (volgens FIFO) doorlopen we de volgende stappen:

Maak huidige gelijk aan de kop
Als huidige niet nil is dan
verwerk de waarde(s) van huidige
maak huidige gelijk aan huidige^.volgende
verwijder de kop (Dispose(kop))
maak kop gelijk aan de huidige.

Voorbeeldje

Om bovenstaande te illustreren volgt nu een voorbeeldje:

program drij;

type
pRij = ^tRij;
tRij = record
waarde: integer;
volgende: pRij;
end;

var
kop, staart: pRij;

procedure VoegToe(w: integer);
var
huidige: pRij;
begin
new(huidige); {1a}
huidige^.waarde := w; {1a}
huidige^.volgende := nil; {1a}
if kop = nil then {1b}
kop := huidige;
if staart <> nil then {1c}
staart^.volgende := huidige;
staart := huidige; {1d}
end;

procedure LaatZien;
var
huidige: pRij;
begin
write(‘Rij = ‘);
huidige := kop;
while huidige <> nil do
begin
write(huidige^.waarde:8);
huidige := huidige^.volgende;
end;
writeln;
end;

function HaalAf: integer;
var
huidige: pRij;
begin
huidige := kop; {2a}
if huidige <> nil then {2b}
begin
HaalAf := huidige^.waarde; {2c}
huidige := huidige^.volgende; {2d}
dispose(kop); {2e}
kop := huidige; {2f}
end
else
HaalAf := -MaxInt; {slechts om aan te geven dat de rij leeg is}
end;

begin
kop := nil;
staart := nil;
VoegToe(1);
LaatZien;
VoegToe(2);
LaatZien;
VoegToe(3);
LaatZien;
writeln;
writeln(HaalAf);
LaatZien;
writeln(HaalAf);
LaatZien;
writeln(HaalAf);
LaatZien;
writeln(HaalAf);
end.

De stapel.

De stapel lijkt op de rij. Alleen draaien we als het ware de kop en de staart om. Ook de verwijzing loopt precies de andere kant op.
Schematisch stellen we ons de stapel als volgt voor:

staart kop
1^e element←2^e element← 3^e element←4^e element← …

De bewerkingen zijn natuurlijk hetzelfde als bij de rij, alleen hebben ze nu speciale namen.
Iets op de stapel zetten heet ‘Push’ en iets van de stapel halen heet ‘Pop’.

1: Push

Om een item aan de stapel toe te voegen doorlopen we de volgende stappen:

Maak en vul een nieuw item (huidige)
Als de staart nil is, maak dan de staart gelijk aan de huidige
Als de kop nil is, maak dan het veld huidige^.vorige gelijk aan nil
maak anders (kop <> nil) het veld huidige^.vorige gelijk aan de kop
Maak kop gelijk aan huidige

2: Pop

Om een item van de stapel af te halen doorlopen we de volgende stappen:

Maak huidige gelijk aan kop
Als huidige niet nil is dan
verwerk de waarde(s) van huidige
maak huidige gelijk aan huidige^.vorige
verwijder de kop (Dispose(kop))
maak kop gelijk aan de huidige

Voorbeeldje

Om de stapel te illustreren volgt hier een voorbeeldje (analoog aan het vorige):

program dstapel;

type
pStapel = ^tStapel;
tStapel = record
waarde: integer;
vorige: dStapel;
end;

var
kop, staart: pStapel;

procedure Push(w: integer);
var
huidige: pStapel;
begin
new(huidige); {1a}
huidige^.waarde := w; {1a}
if staart = nil then {1b}
staart := huidige;
if kop = nil then {1c}
huidige^.vorige := nil
else {1d}
huidige^.vorige := kop;
kop := huidige; {1e}
end;

procedure LaatZien;
var
huidige : pStapel;
begin
huidige := kop;
write(‘Stapel = ‘);
while huidige <> nil do
begin
write(huidige^.waarde:8);
huidige := huidige^.vorige;
end;
writeln;
end;

function Pop: integer;
var
huidige: pStapel;
begin
huidige := kop; {2a}
if huidige <> nil then {2b}
begin
Pop := huidige^.waarde; {2c}
huidige := huidige^.vorige; {2d}
dispose(kop); {2e}
kop := huidige; {2f}
end
else
Pop := -MaxInt; {slechts om aan te geven dat de stapel leeg is}
end;

begin
kop := nil;
staart := nil;
Push(1);
LaatZien;
Push(2);
LaatZien;
Push(3);
LaatZien;
writeln;
writeln(Pop);
LaatZien;
writeln(Pop);
LaatZien;
writeln(Pop);
LaatZien;
writeln(Pop);
end.

Oefeningen.

14.1
Implementeer een simulatie m.b.v. een stack van de recursieve functie Fac(waarde: byte): integer.
Gebruik de juiste type-definitie’s alsmede een procedure Push en een functie Pop.
Denk er even over na hoe je bepaalt of de stapel leeg is, en verzin hiervoor dus een oplossing.
Test met Fac(5) (moet 120 als uitkomst hebben).

[Antwoord]

[Pointers] <–