La pile

Si on a une variable dynamique qui contient elle-même une ou plusieurs variables pointeurs, on a une définition récursive d'une structure de données. On peut ainsi créer des piles, des listes, des arbres, des graphes, ...

type base  = integer;
     pile = ^element;
     element = record
                 valeur: base;
                 suivant: pile;
               end;

Remarque: c'est le seul cas en Pascal où l'on puisse utiliser un identificateur sans l'avoir préalablement défini. La figure 6.6  représente la structure d'une pile en cours d'exécution.

 
Figure 6.6:  structure de la pile pairs lors d'une exécution

On obtient alors le programme suivant :

program piles2;

type base = integer;
     pile=^element;
     element = record
                valeur : base;
                suivant : pile;
               end;

var pairs, impairs : pile;
    x : integer;

procedure initpile(var p:pile);
   begin
        p:=nil;
   end;

function pilevide(p:pile):boolean;
    begin
         pilevide:=(p=nil);
    end;

procedure empiler(var p:pile; e : base);
    var paux : pile;

    begin
         new(paux);
         paux^.valeur:=e;
         paux^.suivant:=p;
         p:=paux;
    end;

procedure depiler(var p: pile; var e : base);
    var paux : pile;
    begin
         if (pilevide(p)) then writeln('impossible de depiler car pile vide')
         else
             begin
                  e:=p^.valeur;
                  paux:=p^.suivant;
                  dispose(p);
                  p:=paux;
             end;
    end;

begin
    initpile(pairs);
    initpile(impairs);
    writeln('Entrez des nombres entiers, pour arreter entrez 0');
    readln(x);
    while (x<>0) do
      begin
          if (x mod 2 = 0) then empiler(pairs,x)
                           else empiler(impairs,x);
          readln(x);
      end;

    writeln('Les nombres pairs que vous avez entres sont ');
    while not(pilevide(pairs)) do
          begin
                depiler(pairs, x);
                writeln(x);
          end;

    writeln('Les nombres impairs que vous avez entres sont ');
    while not(pilevide(impairs)) do
          begin
                depiler(impairs, x);
                writeln(x);
          end;

end.

Il est intéressant de remarquer que dans les trois définitions successives du type pile (voir les paragraphes 5.3 et 6.3.2), le programme principal de l'application pairs-impairs reste inchangé. Le type pile est ce qu'on appelle un .