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.
É comum nos referirmos a essas operações pelos termos em inglês push (empilhar), pop (desempilhar) e top (obter elemento do topo). A Figura 1 apresenta graficamente o comportamento das três funções.
Na computação, o exemplo de utilização de pilha mais comum é a própria pilha de execução de um programa. Neste caso, as variáveis locais das funções são dispostas em uma pilha e uma função só tem acesso às variáveis que estão no topo, ou seja, não é possível aceder a variáveis de outras funções.
Implementando uma Pilha
Há várias maneiras de se implementar uma ED e cada implementação apresenta vantagens e desvantagens particulares. As duas principais maneiras de se implementar uma ED são:
- Utilizando alocação sequencial estática (com vetores); e
- Utilizando alocação não sequencial dinâmica (com ponteiros).
Neste artigo, adotaremos a implementação com vetores (que é o tipo de implementação utilizado pelo ArrayList
do Java). Mais detalhes sobre as vantagens e desvantagens desta estratégia de implementação são apresentados na Seção 5 deste artigo.
A estrutura de pilha implementada neste artigo contém:
- um vetor de inteiros, denominado “itens”, que armazena, em posições contíguas da memória, os elementos da pilha;
- uma variável inteira, denominada “topo”, que armazena a posição onde o próximo elemento da pilha será inserido, ou seja, o topo da pilha; e
- uma constante,
TAM_MAX
, que define a quantidade máxima de elementos suportada pela pilha.
Os passos para implementação desta ED são apresentados abaixo:
Passo 1: definir a estrutura da pilha. A Listagem 1 apresenta o código do arquivo Pilha.h
, responsável pela definição das estruturas fundamentais da pilha, bem como do protótipo de suas funções. A constante TAM_MAX
(linha 3) define a capacidade do vetor de itens, isto é, da quantidade máxima de itens que podem ser adicionados à pilha. A estrutura struct Pilha
(linhas 4 à 7) contém os elementos necessários para armazenamento e manipulação dos dados na pilha.
Passo 2: o segundo passo consiste na definição dos protótipos das funções a serem oferecidas pela pilha. Tais funções são:
- Criar Pilha: aloca e retorna uma pilha vazia para o utilizador.
- Liberar Pilha: libera a memória alocada para a pilha.
- Verificar Pilha Vazia: verifica se a pilha está vazia.
- Verificar Pilha Cheia: verifica se a pilha está cheia.
- Empilhar: insere um novo elemento no topo da pilha.
- Desempilhar: remover e retorna o elemento do topo da pilha.
- Obter Topo: retorna o elemento do topo da pilha, sem removê-lo.
Os protótipos das funções descritas acima devem ser incluídos no arquivo Pilha.h
, conforme apresentado na Listagem 2. É possível perceber também a declaração de mais duas constantes, a saber TRUE
e FALSE
, que serão utilizadas pelas funções estahVazia
e estahCheia
. Como a linguagem C não possui nativamente um tipo específico para dados booleanos, esta é uma forma de representar esse tipo de informação de forma mais legível no código fonte do programa. Alguns trechos de código já apresentados na Listagem 1 foram omitidos na Listagem 2.
A implementação da função criarPilha
deve ser realizada em um arquivo denominado Pilha.c
. A implementação desta função encontra-se na Listagem 3. Conforme pode ser visto, o procedimento para criar uma pilha é: (i) instanciar dinamicamente a pilha (linha 5); (ii) atribuir o valor 0
(zero) à variável topo
, uma vez que a pilha encontra-se vazia no início (linha 6); e (iii) retornar a pilha criada dinamicamente (linha 7).
Ressalta-se ainda a necessidade de se importar dois arquivos de cabeçalho: (i) o stdlib.h
, que permite utilização de funções para gerenciamento dinâmico de memória, como malloc
, free
, entre outros; e (ii) o Pilha.h
, que define as estruturas e funções oferecidas pela pilha.
A implementação das demais funções é apresentada na Listagem 4. Foge ao escopo deste artigo descrever o funcionamento detalhado destas funções; mais informações sobre a estrutura pilha, seu funcionamento e implementação podem ser encontrados em [1].
A Listagem 5 apresenta um código simples para criação e manipulação de uma pilha.
Inicialmente, este programa insere os elementos 1
, 2
e 3
na pilha (linha 7); assim o elemento 3
passa o topo da pilha. Posteriormente, o elemento do topo é removido (linha 8) e o elemento 2
passa a ser o topo. Na linha 9, o elemento 4
é inserido na pilha, passando a ser o topo da mesma e, por fim, a função imprimirPilha
(linha 10) é invocada e o resultado da execução desta função é apresentado na Figura 2.
O que nos chama a atenção nos trechos de código apresentados anteriormente é que esta pilha funciona adequadamente, porém, apenas para números inteiros. Ou seja, não conseguiríamos armazenar, recuperar ou remover outros tipos de dados nesta estrutura, como strings ou tipos complexos, como structs, por exemplo “Aluno”, “Processo”, “Disciplina”, entre outros.
Se quiséssemos atingir tal objetivo, teríamos que modificar alguns trechos de código da implementação da estrutura, como por exemplo, a linha 5 da Listagem 1, que descreve o tipo de elementos do vetor itens ou as funções empilhar e desempilhar, da Listagem 4, uma vez que o tipo de item recebido pela função empilhar e o tipo de retorno da função desempilhar seriam diferentes.
É importante ressaltar que esse código poderia ser melhorado com a adição de um tipo de dados específico para encapsular o item de uma estrutura de dados. Assim, a mudança ficaria concentrada na alteração de um único tipo de estrutura, contudo ainda assim seria necessário modificar o código da estrutura de dados, o que não é uma tarefa trivial e muito menos recomendada, por diversos motivos já comentados no início deste artigo.
Para amenizar estes problemas, uma solução mais elegante é a construção de estruturas genéricas, que permitem ao programador especificar, no momento da criação da estrutura de dados, qual o tipo de elemento que será mantido por ela e partir daí, todo o trabalho realizado pela ED fica transparente para o programador e nenhum código desta estrutura precisará de ser modificado.
Criando uma Pilha Genérica
Um recurso a ser utilizado para confecção da pilha genérica é o tipo void
da linguagem C. Muitos devem saber que void
é uma palavra reservada da linguagem C, utilizada, por exemplo, para especificar que uma função não possui um tipo de retorno. O que nem todos devem saber é que esse recurso também é utilizado para especificar tipos genéricos em C. Por exemplo, uma função que retorna um ponteiro para um tipo void
(void*
), na verdade, retorna um ponteiro que pode ser convertido via casting explícito para qualquer outro tipo existente na linguagem C ou até mesmo para tipos definidos pelo próprio utilizador.
Este recurso é utilizado em algumas funções de bibliotecas da linguagem C, como por exemplo, a função malloc
. Se observarmos a documentação desta função [2], sua assinatura é void* malloc (size_t size)
; essa função aloca um determinado espaço de memória do tamanho especificado pelo utilizador e retorna um ponteiro para o bloco de memória reservado. Esse ponteiro, por sua vez, pode ser convertido em um ponteiro para qualquer outro tipo de dado. Por exemplo, pode-se alocar uma variável inteira dinamicamente por meio do trecho de código da Listagem 6.
A primeira alteração realizada no código fonte da nossa estrutura de dados encontra-se no arquivo de cabeçalho, Pilha.h
, conforme mostrado na Listagem 7.
Neste caso, a struct Pilha
não contém mais um vetor de inteiros, mas sim um vetor de ponteiros para o tipo genérico void
. Em outras palavras, tem-se um vetor capaz de conter elementos de qualquer tipo de dado. Outra mudança é o acréscimo da variável tamItem
na estrutura Pilha
. Ela será utilizada nas funções desempilhar e obterTopo
, nas quais será preciso conhecer o tamanho do item que está sendo manipulado pela pilha para que seja possível realizar uma cópia deste item antes de retorná-lo ao utilizador.
No caso das outras funções da pilha, as modificações realizadas são apresentadas na Listagem 8 (as funções que não sofreram modificações foram omitidas). Como pode ser observado, a única mudança realizada na função criarPilha
encontra-se nas linhas 1 e 4, nas quais o tamanho do item a ser armazenado na pilha é passado como parâmetro para esta função e posteriormente copiado para a variável tamItem
da estrutura pilha, respectivamente.
Quanto às funções desempilhar
e obterTopo
, as principais mudanças estão nas linhas 9 à 10 e 17 à 18, respectivamente. Nestes casos, antes de retornar o elemento do topo da pilha para o utilizador, uma cópia do mesmo é realizada. Para que isso seja possível, utilizou-se a função memcpy
(acrónimo de memory copy), da biblioteca stdlib.h
. Esta função copia os valores da região apontada pelo topo da pilha para uma nova região de memória, apontada por elRemovido
. O ponteiro elRemovido
é genérico e aponta para uma região de memória instanciada dinamicamente por meio da função malloc
. Neste ponto, é possível identificar onde a variável tamItem
é utilizada. Para que uma cópia do elemento do topo da pilha seja feita, antes, é necessário saber o tamanho deste item para que possa ser alocado um espaço de memória compatível para receber a cópia.
Com essas poucas mudanças, nossa estrutura de dados já suporta diferentes tipos de dados. A Listagem 9 apresenta duas formas de uso desta estrutura, uma capaz de armazenar números inteiros na pilha e outra capaz de armazenar strings.
É possível observar que as funções que são específicas para o tipo de item da pilha, como a função que imprime os elementos de uma pilha, possuem duas versões, uma para números inteiros (imprimirPilhaInt
) e outra para strings (imprimirPilhaStr
). Isso é aceitável, uma vez que para imprimir um elemento, deve-se conhecer como esse elemento é formado. Imaginemos por exemplo, que temos uma lista de registros de alunos; a forma de impressão de um registro como esse é bastante específica. Além disso, esse é um método que não faz parte da implementação da pilha, ou seja, é de responsabilidade do programador que está a manipular a estrutura.
As demais funções, que dizem respeito à estrutura da pilha em si, como empilhar, desempilhar, verificar se está vazia ou se está cheia não precisam de ser modificados. Basta invocá-las passando como parâmetro o ponteiro para a lista desejada e o comportamento da função será executado com sucesso, independentemente do tipo de objeto armazenado por ela. Entretanto, uma questão que devemos pensar é: e se quiséssemos adicionar uma função à estrutura da pilha, que fosse capaz de desempilhar todos os elementos até encontrar um determinado elemento desejado. Por exemplo, suponha que a pilha seja composta pelos elementos 1, 2 e 3, sendo 3 o topo da mesma. Se invocássemos esta função passando o item 1 como parâmetro, os elementos 2 e 3 seriam removidos e a pilha ficaria com apenas um elemento.
O impasse aqui é o seguinte: como a função saberá como comparar os itens da pilha, uma vez que ela não conhece o seu tipo, a priori. Mesmo sabendo qual é o tipo de dado, em alguns casos, não seria possível compará-los; por exemplo, quando o tipo de dado é uma estrutura complexa criada pelo próprio desenvolvedor, como uma struct para armazenar os dados de um aluno, entre outros.
Para resolver este problema, precisamos de utilizar outro recurso da linguagem C, conhecido como funções callback. Este tipo de função tira proveito do fato de que a linguagem C trabalha com ponteiros para funções, isto é, podemos passar como parâmetro para uma função, um ponteiro que aponta para o bloco da memória onde está localizada outra função do sistema (ou até mesmo ela mesma). Isto permite que uma determinada função realize chamadas de outra função, sem mesmo saber que função é esta. Mas este será um assunto para um próximo artigo.
Vantagens e Desvantagens do uso de vetores para implementação de estruturas de dados
Ao declararmos um vetor, reservamos um espaço contíguo de memória para armazenar seus elementos. O fato de o vetor ocupar um espaço contíguo na memória permite que acessemos qualquer um de seus elementos a partir do ponteiro para o primeiro elemento.
Por exemplo, quando declaramos int vet[100]
, de fato, a variável vet
representa um ponteiro para o primeiro elemento do vetor. De posse deste ponteiro, podemos aceder a qualquer elemento do vetor através do operador de indexação vet[i]
.
Dizemos que o vetor é uma estrutura que possibilita acesso aleatório (random acess) aos elementos, pois podemos aceder a qualquer elemento aleatoriamente. No entanto, o vetor não é uma estrutura de dados muito flexível. Se o número de elementos que precisamos de armazenar exceder a dimensão do vetor, teremos problemas. Não existe uma maneira simples e barata, computacionalmente falando, para alterarmos a dimensão do vetor em tempo de execução.
Neste mesmo sentido, temos outro problema sério quando lidamos com estruturas como o vetor. Se o número de elementos que precisarmos armazenar no vetor for muito inferior à sua dimensão, estaremos subutilizando o espaço de memória reservado. A solução para esses problemas é utilizarmos estruturas de dados que: (i) cresçam à medida que precisarmos armazenar novos elementos; e (ii) diminuam à medida que precisarmos retirar elementos armazenados anteriormente.
Tais estruturas são chamadas dinâmicas e elas armazenam cada um dos seus elementos usando alocação dinâmica de memória. Mais detalhes sobre este tipo de estrutura podem ser encontrados em [1].
Considerações finais
Este artigo apresentou a implementação de uma pilha genérica, isto é, uma estrutura de dados capaz de lidar com elementos de qualquer tipo de dado, como inteiros, strings, entre outros. Inicialmente, destacou a motivação para construção deste tipo de estrutura; posteriormente, apresentou-se a implementação de uma pilha específica para lidar com números inteiros. Por fim, mostrou-se como evoluir esta estrutura para torná-la genérica.
Uma das limitações da implementação apresentada neste artigo é que a capacidade da pilha é limitada, ou seja, uma vez atingida a capacidade máxima desta estrutura, não se pode mais inserir elementos na mesma. Na prática, isso não é muito comum. O que ocorre, mesmo em estruturas implementadas com vetores, é que um novo vetor com maior capacidade é alocado, caso seja possível, e os elementos do vetor antigo são transferidos para o novo vetor.
Nos próximos artigos, pretende-se apresentar uma alternativa para resolução do problema anterior, bem como apresentar o desenvolvimento de funções para a pilha que dependem do tipo de item manipulado por ela para ser executada. Além disso, pretende-se abordar a implementação de outras estruturas de dados genéricas, como listas, filas, árvores, entre outras.
Referências
- Celes, W.; Rangel, J. L. Apostila de Estruturas de Dados. Disponível em: http://www-usr.inf.ufsm.br/~juvizzotto/elc1067-2013b/estrut-dados-pucrio.pdf. Acedido em: Agosto/2014.
- Documentação da função
malloc
. Disponível em: http://www.cplusplus.com/reference/cstdlib/malloc/. Acedido em: Agosto/2014.