Estruturas de Dados com Delphi - parte I : Filas

Em maior ou menor grau, o trabalho de um programador de computadores envolve lidar com meios de organizar os dados internos de seus programas. Uma organização bem planejada é imprescindível para a implementação de algorítmos eficientes, o que afeta tanto a performance da aplicação quanto sua facilidade de manutenção. As formas de se organizar os dados em um programa são chamadas de Estruturas de Dados.

Pela sua importância, a maioria das linguagens de programação oferecem bibliotecas com implementações genéricas pré fabricadas para as formas tradicionais de organização de dados, tais como listas, pilhas e filas. No caso do Delphi, esses e outros mecanismos estão disponíveis na unit System.Generics.Collections. Neste post, começo a mostrar as principais estruturas existentes nessa biblioteca, complementando a explicação com exemplos práticos em Delphi.

Em primeiro lugar, precisamos compreender como funciona cada uma das estruturas para podermos decidir qual a mais apropriada para cada situação.

Por exemplo, as filas são desenhadas para o cenário onde precisamos tratar uma sequência de valores exatamente na mesma ordem em que esses valores vão surgindo. É o conceito da fila do caixa em uma loja: cada cliente é atendido sequencialmente de acordo com sua posição na fila; novos clientes entram no final da fila para serem atendidos. Em programação, esse conceito pode ser aplicado ao tratamento de requisições enviadas para execução num sistema. O quadro abaixo traz a declaração básica de uma classe Delphi representando uma requisição executável:

TWRequis = class
public
procedure Execute;virtual;abstract;
function Terminou : Boolean;virtual;abstract;
End;

As Collecions definidas pelo Delphi são estruturas de dados genéricas, mais ou menos como as STL do C++. Isso significa que, quando declaramos uma instância dessas estruturas, devemos informar o tipo de dado que essa Collection em particular vai tratar. Para deixar mais claro, veja a declaração da classe que controlará a execução de requisições em nosso exemplo de fila:

TWVerifRequis = class
{ ... }
public
Fila: TQueue<TWRequis>;
procedure DoOnNotify (Sender: TObject; const Item: TWRequis; Action: TCollectionNotification);

constructor Create;
destructor Destroy;override;
procedure InsereRequis(ATipo: integer);
procedure Start;
end;

No exemplo, declarei a fila associada à classe de requisição. Se for necessário, também é permitido associar a tipos atômicos (como integer e string) ou a estruturas (record). Agora, vamos dar uma olhada no construtor da classe:

constructor TWVerifRequis.Create;
begin
Fila := TQueue<TWRequis>.Create();
Fila.OnNotify := DoOnNotify;
end;

Veja que também ao criar uma instância da fila (o TQueue) devemos especificar o tipo de dado com o qual ela está apta a trabalhar. Um outro detalhe é o evento OnNotify; interceptá-lo nos permite reagir a alterações na fila, tais como saber que um novo registro foi incluído ou acabou de ser removido. Em ambos os casos, podemos atualizar o status da fila para o usuário, avisando-o quantos registros restam e qual requisição está sendo processada. Repare ainda que a assinatura do evento reflete o tipo de dado que nossa fila trata, restringindo a resposta do OnNotify a este tipo específico:

procedure TWVerifRequis.DoOnNotify (Sender: TObject;const Item: TWRequis; Action: TCollectionNotification);
begin
{ A requisição que está no início da fila foi removida; então, ela deve ser executada }
if Action = cnRemoved then begin
{ Atualiza o status, notificando o usuário sobre que requisição está em processamento }
NotificaRequisAtual(Item);
Item.Execute;
Item.Free;
end;

{ Atualiza o status, notificando o usuário sobre quantas requisições restam na fila p/ executar }
NotificaQtd (Fila.Count);
end;

As funções mais importantes para essa estrutura de dado são a que acrescenta e a que remove um elemento da fila. Para incluir um novo item ao fim da fila, use o método Enqueue e para remover o elemento que está no início da fila, use Dequeue, como mostra o exemplo a seguir:

procedure TWVerifRequis.InsereRequis(ATipo: integer);
var lRequis : TWRequis;
begin
{ Invoca a factory para criar a requisição correta de acordo com o tipo informado }
lRequis := CriaNovaRequisicao(ATipo);

{ Acrescenta ao fim da lista a nova requsição criada }
Fila.Enqueue(lRequis);
end;

procedure TWVerifRequis.Start;
var lRequis : TWRequis;
begin
{ Enquanto não foi solicitado o término da execução, continua monitorando a fila }
while Not Terminou() do begin
{ Se há elemento na lista, remove-o aqui. Isso dispara o evento OnNotify, permitindo a execução dessa requisição }
if (Fila.Count > 0) then
lRequis := Fila.Dequeue
else
Sleep(1000);
end;
end;

A requisição poderia ter sido executada imediatamente após a chamada ao Dequeue, ao invés de dentro do evento OnNotify. Ambas são soluções aceitáveis e, portanto, optar por uma ou outra abordagem é uma questão de gosto.

Uma última consideração: se, por alguma razão, for preciso descobrir quem é o próximo item da fila sem, no entanto, removê-lo, use o método Extract. Uma aplicação disso é mostrar no status informações sobre a requisição que está aguardando para ser executada.

Esse exemplo foi construído com o Delphi XE2; não encontrei informação a respeito da presença da biblioteca Collection em versões anteriores ou em qual versão ela foi introduzida. No próximo post, falo sobre pilhas (ou stacks) e suas aplicações.

Mais Informações
Estruturas de Dados no Wikipedia, Tipos de Estruturas de Dados, Documentação do System.Generics.Collections