Estruturas de Dados Genéricas

Introdução

Quando cursamos disciplinas de Algoritmos e Estruturas de Dados nos cursos de computação e áreas afins, em geral, aprendemos a criar Estruturas de Dados (EDs) básicas, como listas, pilhas, filas, capazes de trabalharem apenas com números inteiros. Isto não é essencialmente um problema, uma vez que o intuito destas disciplinas é apresentar os principais tipos de EDs, as operações relacionadas a elas, bem como as formas de uso (aplicação) das mesmas; o que não depende do tipo de dados armazenado pela estrutura.

Contudo, quando vamos para a prática do desenvolvimento e utilização destas EDs, seja num trabalho prático da disciplina ou em outro tipo de aplicação, o nosso desejo é trabalhar com EDs capazes de armazenar qualquer tipo de elemento e não apenas de números inteiros. Por exemplo, nosso interesse pode ser criar uma lista de alunos ou uma fila de processos a serem atendidos por um determinado sistema operacional, entre outros. Obviamente, alunos e processos são entidades complexas (por exemplo, o registro de um aluno pode conter nome, matrícula, data de nascimento, entre outros dados), uma vez que são compostas por outros tipos de dados mais simples, e não pertencem aos tipos primitivos de qualquer linguagem de programação de propósito geral.

Neste sentido, como podemos trabalhar com estruturas de dados para esses tipos complexos? Uma forma seria implementar uma versão da estrutura de dados específica para cada tipo de dados que desejamos armazenar, isto é, uma implementação de lista específica para trabalhar com alunos, outra para processos, outra para inteiros e assim sucessivamente. Contudo, podemos perceber que esta não é uma abordagem muito interessante, uma vez que: (i) aumenta o volume de trabalho do programador, que deverá reimplementar as estruturas para cada tipo de dado de interesse; (ii) aumenta a quantidade de código duplicado, uma vez que o código fonte de funções comuns a um mesmo tipo de estrutura, como por exemplo, inserir no final de uma lista deveria ser duplicado para cada novo tipo de dado; (iii) aumentaria muito a probabilidade de o programador cometer erros, comprometendo a qualidade do software como um todo; entre outros.

Enfim, são muitas as razões para não adotarmos a estratégia apresentada anteriormente. Outra opção seria implementarmos “estruturas genéricas”, isto é, estruturas de dados que trabalham de forma transparente para o usuário final (programador), independentemente do tipo de dado que está sendo manipulado por ela. Sendo assim, o correto seria criarmos uma ED denominada Lista, por exemplo, que encapsula o código necessário para manipulação dos itens de uma lista, não importando que tipo de item seja este. Em outras palavras, teríamos uma única implementação do tipo Lista, que pode armazenar e tratar desde números inteiros, strings, até estruturas complexas como alunos, processos, produtos, entre outros.

Esta é a estratégia utilizada pela maioria das bibliotecas de estruturas de dados das linguagens de programação modernas, como Java, C++, entre outros. Por exemplo, em Java existe a implementação ArrayList, que representa uma lista implementada por meio de vetores. Ao criarmos um objeto do tipo ArrayList, podemos informar que tipo de dados iremos armazenar na ED, por exemplo ArrayList, e ela estará preparada para lidar com itens deste tipo, sem precisarmos conhecer, muito menos alterar, o código fonte desta estrutura de dados.

Uma linguagem de programação bastante utilizada em disciplinas iniciais de programação e estruturas de dados é a linguagem C. Apesar de muitos livros já abordarem o ensino de ED com linguagens orientadas a objetos, como C++ e Java, ainda há livros que tratam do assunto utilizando esta linguagem procedimental.

Quanto às linguagens de programação Java e C++, muitos livros exploram a construção de estruturas de dados genéricas, tendo em conta que o paradigma de Orientação a Objetos facilita bastante este trabalho, por meio dos robustos mecanismos de generalização existentes nativamente nestas linguagens, como herança e polimorfismo. Quanto à linguagem C, no entanto, é difícil encontrar material didático sobre o desenvolvimento de estruturas genéricas para tal linguagem. Isto tem feito com que muitos alunos encontrem dificuldades ao aplicarem os conhecimentos teóricos obtidos nas disciplinas que abordam o tema estruturas de dados em situações práticas. Neste sentido, este artigo tem como objetivo apresentar o desenvolvimento de uma estrutura de dados conhecida como pilha de forma genérica, isto é, de forma que ela seja capaz de armazenar qualquer tipo de elemento especificado pelo utilizador, sem exigir que seu código seja modificado.

A Pilha

Antes de iniciarmos a implementação de nossa estrutura de dados genérica, é importante explicarmos sucintamente do que se trata a ED conhecida como pilha. 

Uma das EDs mais simples, mas não menos importantes do que as demais, é a pilha. Possivelmente por essa razão, é uma das EDs mais utilizada em programação, sendo inclusive implementada diretamente pelo hardware da maioria das máquinas modernas.

A ideia fundamental da pilha é que todo o acesso aos seus elementos é feito por meio do seu topo. Assim, quando um elemento novo é introduzido na pilha, ele passa a ser o elemento do topo e o único elemento que pode ser removido ou acessado da pilha é o do topo. Isto faz com que os elementos da pilha sejam retirados na ordem inversa à ordem em que foram introduzidos: o primeiro elemento a sair da pilha é o último que entrou.

A sigla LIFO – Last in, First out (O último a entrar é o primeiro a sair) – é usada para descrever esta estratégia.

Para entendermos o funcionamento de uma pilha, podemos fazer uma analogia com uma pilha de pratos. Se quisermos adicionar um prato na pilha, o colocaremos no topo. Se quisermos retirar um prato da pilha, retiraremos o prato do topo. Assim, para termos acesso ao segundo prato da pilha, precisaremos retirar o prato do topo.

A ED pilha funciona de maneira análoga. Existem três operações básicas que devem ser implementadas em uma pilha:

  • a operação para empilhar um novo elemento, inserindo-o no topo;
  • a operação para desempilhar um elemento, removendo-o do topo; e
  • a operação para consultar o elemento do topo, sem removê-lo.

Publicado na edição 47 (PDF) da Revista PROGRAMAR.