Estruturas de Dados com Delphi - parte II : Pilhas

No meu último post, comecei a falar sobre estruturas de dados e como o Delphi lida com as estruturas mais comuns, como as filas. Neste post, eu mostro o conceito de outra das estruturas padronizadas que o Delphi trata de forma inerente : pilhas.

A diferença central entre filas e pilhas está na ordem em que os elementos são retirados da estrutura. No caso das filas, o primeiro elemento inserido será o primeiro a ser retirado, mecanismo conhecido como FIFO (First In, First Out). Para as pilhas, o último elemento inserido é retirado primeiro; isto é, pilhas implementam o LIFO (Last In, First Out). Para compreender esse conceito, imagine que você guarde os pratos de sua casa empilhados no armário. Sempre que você precisa de um prato, retira o que está no topo da pilha. Quando vai guardá-los, os pratos são postos no topo da pilha novamente, disponíveis para o próximo uso.

Uma situação computacional prática onde o uso de pilhas se adequa é o cálculo do custo de um produto fabricado. Por exemplo, para calcular o custo de fabricação de um computador, temos que calcular o custo da CPU, do monitor e do teclado. No entanto, obter o custo da CPU requer que se calcule antes o custo da placa-mãe, transistores, capacitores, etc. A placa-mãe também é composta por outros itens, e assim sucessivamente.

Nessa estrutura, podemos somar o custo individual de cada componente até encontrar um que também seja composto. O item composto é incluído no topo da pilha enquanto se calcula seu custo. Tal processo deve ser feito recursivamente até que haja apenas itens simples. Nesse momento, o custo do último item adicionado à pilha está determinado e ele pode ser removido da pilha, prosseguindo o cálculo com o item seguinte.

Para implementarmos com as classes nativas do Delphi uma solução para essa situação, considere as classes abaixo:

TWProduto = class
public
Codigo: String;
Custo : Double;
Componentes: TList;

Constructor Create(ACodigo:String;ACusto: Double);
Destructor Destroy;override;
End;

TWContexto=class
public
produto: TWProduto;
indice : integer;
custo : double;

Constructor Create(AProduto: TWProduto);
end;

{ ... }

Constructor TWProduto.Create(ACodigo:String;ACusto: Double);
begin
Codigo := ACodigo;
Custo := ACusto;
Componentes:= TList.Create;
end;

Destructor TWProduto.Destroy;
begin
{ ... }
Componentes.Free;
inherited;
end;

Constructor TWContexto.Create(AProduto: TWProduto);
begin
produto := AProduto;
indice := 0; { iniciar cálculo nesse índice }
custo := 0.0; { custo inicial do produto }
end;

A primeira classe (TWProduto) representa um produto que pode ser composto de outros produtos, incluindo outros produtos compostos. Já a classe TWContexto serve para controlar o cálculo do custo de um único produto composto. Além do próprio produto, ela armazena o índice do último componente considerado pelos cálculos bem como o custo obtido até o momento.

No quadro a seguir, eu simulo manualmente a montagem simplificada de um computador. O resultado é um exemplo de estruturação complexa usando a classe de produto descrita acima e cujo custo poderá ser calculado com uma rotina usando pilha:

function TForm1.MontaComputador : TWProduto;
var computador, compon, subcompon: TWProduto;
begin
computador := TWProduto.Create('Computador', 0.0);

compon := TWProduto.Create('Teclado', 20.0);
computador.Componentes.Add(compon);

compon := TWProduto.Create('Monitor', 235.0);
computador.Componentes.Add(compon);

{ A CPU é um produto composto }
compon := TWProduto.Create('CPU', 0.0);
subcompon := TWProduto.Create('Placa-mãe', 250.0);
compon.Componentes.Add(subcompon);
subcompon := TWProduto.Create('Cooler', 32.0);
compon.Componentes.Add(subcompon);
computador.Componentes.Add(compon);

Result := Computador;
end;

A rotina abaixo usa pilha para controlar o cálculo do custo de um produto - no caso, o computador estruturado no quadro anterior. Em Delphi, a classe TStack implementa as operações necessárias para se trabalhar com uma pilha.

procedure TForm1.btnCalcularCustoClick(Sender: TObject);
var i : integer;
interromper : boolean;
Pilha: TStack;
contexto, ctxAux : TWContexto;
computador : TWProduto;
begin
computador := MontaComputador;
contexto := TWContexto.Create (computador);

{ Inicia a pilha com o produto original no contexto : o computador }
Pilha:= TStack.Create;
Pilha.Push(contexto);

while (pilha.Count > 0) do begin
{ Obtém o contexto no topo, sem removê-lo }
contexto := pilha.Peek;
compon := contexto.produto;
i := contexto.indice;

{ Percorre os componentes desse produto, somando o custo de cada um para obter o custo do total do produto em si }
interromper := false;
while (i < compon.Componentes.Count) And (not interromper) do begin
subcompon := compon.Componentes.Items[i];

{ Esse produto é composto ? }
interromper := (subcompon.Componentes.Count > 0);
if (interromper) then begin
{ Inclui o subcomponente composto no topo da pilha pra calcular seu custo }
ctxAux := TWContexto.Create (subcompon);
Pilha.Push(ctxAux);

{ Quando desempilhar esse produto, inicie no componente seguinte }
contexto.indice := i + 1;
end
else
contexto.custo := contexto.custo + subcompon.Custo;

Inc (i);
end;

{ Conseguiu totalizar o custo do produto; então, remove-o do topo da pilha }
if not interromper then begin
Pilha.Pop;
compon.Custo := contexto.custo;
contexto.Free;

{ Adiciona o custo calculado ao custo do produto do qual esse componente é parte }
if pilha.Count > 0 then begin
contexto := pilha.Peek;
contexto.custo := contexto.custo + compon.Custo;
end;
end;
end;

{ Apresenta o custo obtido }
lblCusto.Caption := FormatFloat ('#,##0.00', computador.Custo);

Pilha.Free;
computador.Free;
end;

Assim como no caso da fila tratado no outro post, o constructor da pilha exige a especificação do tipo de dado com o qual a pilha será capaz de trabalhar. No exemnplo, a classe TWContexto é informada para que possamos controlar os produtos que já foram considerados no cálculo do custo.

As funções mais importantes na pilha são a que acrescenta e a que remove um elemento. Para inserir um novo elemento no topo da pilha, use o método Push e para extraí-lo use Pop, como mostrado no código acima.

É possível ainda obter o elemento que está no topo da pilha sem, no entanto, extraí-lo. Para isso, há o método Peek, também utilizado no exemplo.

Embora não tenha sido necessário aqui, o TStack permite interceptar a adição e remoção de elementos através do evento OnNotify. Ele é frequentemente utilizado para liberar a memória associada aos elementos da pilha.

Mais Informações
Estruturas de Dados com Delphi - parte I : Filas, Estruturas de Dados no Wikipedia, Pilhas