program Pilha;

type
  TipoChave     = integer;
  TipoApontador = ^TipoCelula;
  TipoItem      = record 
                    Chave: TipoChave;
                    { outros componentes }
                  end;
  TipoCelula    = record 
                    Item: TipoItem;
                    Prox: TipoApontador;
                  end;
  TipoPilha     = record
                    Fundo  : TipoApontador;
                    Topo   : TipoApontador;
                    Tamanho: integer;
                  end;

procedure FPVazia (var Pilha: TipoPilha);
begin
  new (Pilha.Topo);
  Pilha.Fundo := Pilha.Topo;
  Pilha.Topo^.Prox := nil;
  Pilha.Tamanho := 0;
end; { FPVazia }

function Vazia (Pilha: TipoPilha): boolean;
begin
  Vazia := Pilha.Topo = Pilha.Fundo;
end; { Vazia }

procedure Empilha (x: TipoItem; var Pilha: TipoPilha);
var Aux: TipoApontador;
begin
  new (Aux);
  Pilha.Topo^.Item := x;
  Aux^.Prox := Pilha.Topo;
  Pilha.Topo := Aux;
  Pilha.Tamanho := Pilha.Tamanho + 1;
end; { Empilha }

procedure Desempilha (var Pilha: TipoPilha; var Item: TipoItem);
var q: TipoApontador;
begin
  if Vazia (Pilha)
  then writeln ('Erro: lista vazia')
  else begin
       q := Pilha.Topo;
       Pilha.Topo := q^.Prox;
       Item := q^.Prox^.Item;
       dispose (q);
       Pilha.Tamanho := Pilha.Tamanho - 1;
       end;
end; { Desempilha }

function Tamanho (Pilha: TipoPilha): integer;
begin
  Tamanho := Pilha.Tamanho;
end; { Tamanho }

const MAX = 10;

var
  pilha: TipoPilha;
  item : TipoItem;
  vetor: array [1..MAX] of integer;
  p    : TipoApontador;
  i, j, k, n: integer;

begin
  FPVazia (pilha);
  
  { Gera uma permutação aleatoria de chaves entre 1 e MAX }
  randomize;
  for i := 1 to MAX do vetor[i] := i;
  for i := 1 to MAX do
    begin
    k := 1 + random (MAX);
    j := 1 + random (MAX);
    n := vetor[k];
    vetor[k] := vetor[j];
    vetor[j] := n;
    end;
  
  { Empilha cada chave }
  for i := 1 to MAX do
    begin
    item.Chave := vetor[i];
    Empilha (item, pilha);
    writeln ('Empilhou: ', item.Chave);
    end;
  
  writeln ('Tamanho da pilha: ', Tamanho (Pilha));
  
  { Desempilha cada chave }
  for i := 1 to MAX do
    begin
    Desempilha (pilha, item);
    writeln ('Desempilhou: ', item.Chave);
    end;
  
  writeln ('Tamanho da pilha: ', Tamanho (Pilha));
end. { Pilha }