Tipos abstratos de dados

Em computação, um tipo abstrato de dado (TAD) é o modelo matemático de um determinado tipo de dado que define seus valores possíveis e as operações sobre ele.

É importante observar que a definição de um TAD não determina a forma de implementá-lo. O TAD separa a especificação do dado (que define como ele funciona) de sua implementação (como ele está codificado). Isso possibilita:

usar um TAD sem precisar conhecer os detalhes internos de sua implementação;
alterar a implementação do TAD sem afetar os programas que a usam.

TADs são geralmente usados para representar estruturas de dados de uso frequente em computação, como filas, pilhas e conjuntos, mas podem ser definidos para qualquer tipo de dado frequentemente manipulado em uma aplicação.

Uma fila armazena uma sequência de valores. Por exemplo:

uma fila de inteiros: 11, 7, 4, 5, 9, -2, 16, 0, 4
uma fila de racionais: 1/4, -3/2, 5/8, 0, 3/7
uma fila de strings: “uva”, “pera”, “abacaxi”, “melão”

A principal característica da fila é que os elementos entram no fim da fila e saem do início dela, da mesma forma que em filas do mundo real. Por isso, filas são também conhecidas como FIFO, do inglês First In, First Out (o primeiro a entrar é o primeiro a sair):

Filas são entidades muito usadas em computação. Por exemplo, filas são usadas para:

Organizar pacotes de rede
Gerenciar processos que querem usar a CPU
Sequenciar pedidos de acesso a dados ou serviços
…

Algumas das operações básicas definidas sobre uma fila são:

cria (fila, capacidade) : cria uma nova fila, informando o número máximo de elementos que ela pode comportar; uma fila pode ser considerada infinita, se não tiver capacidade máxima definida.
destroi (fila) : esvazia/destrói a fila
insere (fila, elemento) : insere um novo elemento no fim da fila
elemento = retira (fila) : retira o primeiro elemento da fila
elemento = primeiro (fila) : informa qual é o primeiro elemento, mas não o retira da fila
vazia (fila) : informa se a fila está vazia
cheia (fila) : informa se a fila está cheia
tamanho (fila) : informa o número atual de elementos na fila

Uma interface possível para o TAD “fila de números inteiros” em C seria:

libfila.h

#ifndef _FILA_H
#define _FILA_H
 
typedef struct {
  ...  // conteúdo depende da implementação em libfila.c
} fila_t;
 
// Cria uma fila vazia com a capacidade informada
// Retorno: ponteiro p/ a fila ou NULL se falhar
fila_t* fila_cria (int capacidade);
 
// Remove todos os elementos da fila, libera espaço
// Retorno: NULL
fila_t* fila_destroi (fila_t* f);
 
// Insere o elemento no final da fila (politica FIFO)
// Retorno: número de elementos na fila após a operação ou -1 se falhar
int enqueue (fila_t* f, int elem);
 
// Retira o elemento do inicio da fila (politica FIFO) e o devolve
// Retorno: número de elementos na fila após a operação ou -1 se falhar
int dequeue (fila_t* f, int* elem);
 
// Devolve o primeiro elemento da fila, sem removê-lo
// Retorno: número de elementos na fila ou -1 se falhar
int fila_primeiro (fila_t* f, int *elem);
 
// Testa se a fila está vazia
// Retorno: 1 se a fila está vazia ou 0 caso contrário
int fila_vazia (fila_t* f);
 
// Testa se a fila está cheia
// Retorno: 1 se a fila está cheia ou 0 caso contrário
int fila_cheia (fila_t* f);
 
// Informa o tamanho da fila (o número de elementos presentes nela)
// Retorno: número de elementos na fila ou -1 se falhar
int fila_tamanho (fila_t* f);
 
// Imprime o conteúdo da fila, do inicio ao fim (opcional, mas útil para testes)
void fila_imprime (fila_t* f);
 
#endif

Filas podem ser implementadas de diversas formas, as mais usuais são:

vetor linear simples
vetor linear otimizado (só move elementos se o fim do vetor for atingido)
vetor circular
lista encadeada simples
lista encadeada dupla
lista encadeada circular simples
lista encadeada circular dupla

Observe que, embora o conteúdo do struct fila_t dependa da forma de implementação da fila, os protótipos das funções não dependem desse conteúdo. Isso torna o uso da fila independente de sua implementação.

Uma pilha também armazena uma sequência de valores, mas estes são “empilhados” como em uma pilha de pratos ou de caixas. Uma pilha tem uma base e um topo:

A base contém o primeiro elemento que entrou na pilha (e que será o último a sair dela);
O topo contém o último elemento que entrou na pilha (e que será o primeiro a sair dela).

Da mesma forma que a fila, podemos ter pilhas de inteiros, de racionais, de strings, etc. A principal característica da pilha é que os elementos entram e saem sempre no topo da pilha. Por isso, pilhas são também conhecidas como LIFO, do inglês Last In, First Out (o último a entrar é o primeiro a sair).

Algumas das operações básicas definidas sobre uma pilha são:

cria (pilha, capacidade) : cria uma nova pilha, informando o número máximo de elementos que ela pode comportar
destroi (pilha) : esvazia/destrói a pilha
insere (pilha, elemento) : insere um novo elemento no topo da pilha
elemento = retira (pilha) : retira o elemento do topo da pilha
elemento = topo (pilha) : devolve o elemento do topo da pilha sem removê-lo
vazia (pilha) : informa se a pilha está vazia
cheia (pilha) : informa se a pilha está cheia
tamanho (pilha) : informa o número atual de elementos na pilha

Uma interface possível para o TAD “pilha de números inteiros” em C seria:

libpilha.h

#ifndef _PILHA_H
#define _PILHA_H
 
typedef struct {
  ...  // conteúdo depende da implementação em libpilha.c
} pilha_t;
 
// Cria uma pilha vazia com a capacidade informada
// Retorno: ponteiro p/ a pilha ou NULL se falhar
pilha_t* pilha_cria (int capacidade);
 
// Remove todos os elementos da pilha, libera espaço
// Retorno: NULL
pilha_t* pilha_destroi (pilha_t* pilha);
 
// Insere o elemento no topo da pilha (politica LIFO)
// Retorno: número de elementos na pilha após a operação ou -1 se falhar
int push (pilha_t* pilha, int elem);
 
// Retira o elemento do topo da pilha (politica LIFO) e o devolve
// Retorno: número de elementos na pilha após a operação ou -1 se falhar
int pop (pilha_t* pilha, int *elem);
 
// devolve o elemento no topo da pilha, sem removê-lo
// Retorno: número de elementos na pilha após a operação ou -1 se falhar
int pilha_topo (pilha_t* pilha, int *elem);
 
// Testa se a pilha está vazia
// Retorno: 1 se a pilha está vazia ou 0 caso contrário
int pilha_vazia (pilha_t* pilha);
 
// Testa se a pilha está cheia
// Retorno: 1 se a pilha está cheia ou 0 caso contrário
int pilha_cheia (pilha_t* pilha);
 
// Informa o tamanho da pilha (o número de elementos presentes nela)
// Retorno: número de elementos na pilha ou -1 se falhar
int pilha_tamanho (pilha_t* pilha);
 
// Imprime o conteúdo da pilha, do topo à base (opcional, mas útil para testes)
void pilha_imprime (pilha_t* pilha);
 
#endif

Pilhas são usualmente implementadas com vetores ou listas encadeadas simples.

Um deque (double-ended queue) é similar a uma fila, mas permite operações (inserir, retirar, consultar) em ambas as pontas (início e fim). O deque pode ser visto como uma generalização dos TADs fila e pilha, porque pode funcionar como qualquer uma dessas estruturas.

Algumas das operações básicas definidas sobre um deque são:

cria (deque, capacidade) : cria um novo deque, informando o número máximo de elementos que ele pode comportar
destroi (deque) : esvazia/destrói o deque
insere_inicio (deque, elemento) : insere um novo elemento no início
insere_final (deque, elemento) : insere um novo elemento no fim
elemento = retira_inicio (deque) : retira o primeiro elemento
elemento = retira_final (deque) : retira o último elemento
elemento = primeiro (deque) : informa qual é o primeiro elemento, mas não o retira
elemento = ultimo (deque) : informa qual é o último elemento, mas não o retira
vazio (deque) : informa se o deque está vazio
cheio (deque) : informa se o deque está cheio
tamanho (deque) : informa o número atual de elementos no deque

Uma interface possível para o TAD “deque de números inteiros” em C seria:

libdeque.h

#ifndef _DEQUE_H
#define _DEQUE_H
 
typedef struct {
  ...  // conteúdo depende da implementação em libdeque.c
} deque_t;
 
// Cria um deque vazio com a capacidade informada
// Retorno: ponteiro p/ o deque ou NULL se falhar
deque_t* deque_cria (int capacidade);
 
// Remove todos os elementos do deque, libera espaço
// Retorno: NULL
deque_t* deque_destroi (deque_t* f);
 
// Insere o elemento no início do deque
// Retorno: número de elementos no deque após a operação ou -1 se falhar
int insere_inicio (deque_t* f, int elem);
 
// Insere o elemento no final do deque
// Retorno: número de elementos no deque após a operação ou -1 se falhar
int insere_final (deque_t* f, int elem);
 
// Retira o elemento do inicio do deque e o devolve
// Retorno: número de elementos no deque após a operação ou -1 se falhar
int retira_inicio (deque_t* f, int* elem);
 
// Retira o elemento do final do deque e o devolve
// Retorno: número de elementos no deque após a operação ou -1 se falhar
int retira_final (deque_t* f, int* elem);
 
// Devolve o primeiro elemento do deque, sem removê-lo
// Retorno: número de elementos no deque ou -1 se falhar
int deque_primeiro (deque_t* f, int *elem);
 
// Devolve o último elemento do deque, sem removê-lo
// Retorno: número de elementos no deque ou -1 se falhar
int deque_ultimo (deque_t* f, int *elem);
 
// Testa se o deque está vazio
// Retorno: 1 se o deque está vazio ou 0 caso contrário
int deque_vazio (deque_t* f);
 
// Testa se o deque está cheio
// Retorno: 1 se o deque está cheio ou 0 caso contrário
int deque_cheio (deque_t* f);
 
// Informa o tamanho do deque (o número de elementos presentes nele)
// Retorno: número de elementos no deque ou -1 se falhar
int deque_tamanho (deque_t* f);
 
// Imprime o conteúdo do deque, do inicio ao fim (opcional, mas útil para testes)
void deque_imprime (deque_t* f);
 
#endif

Uma lista é similar a uma fila (FIFO), mas permite operações (inserir, retirar, consultar) sobre qualquer um de seus elementos. A lista pode ser vista como uma generalização dos TADs fila, pilha e deque, porque pode funcionar como qualquer uma dessas estruturas.

Algumas das operações básicas definidas sobre uma lista são:

cria (lista, capacidade) : cria uma nova lista, informando o número máximo de elementos que ela pode comportar
destroi (lista) : esvazia/destrói a lista
insere_inicio (lista, elemento) : insere um novo elemento no início
insere_fim (lista, elemento) : insere um novo elemento no fim
elemento = retira_inicio (lista) : retira o elemento do início
elemento = retira_fim (lista) : retira o elemento do fim
retira_elemento (lista, elemento) : retira o elemento informado da lista
insere_ordenado (lista, elemento) : insere o elemento na lista garantindo ordenação crescente
pertence (lista, elemento) : informa se o elemento aparece na lista
vazia (lista) : informa se a lista está vazia
cheia (lista) : informa se a lista está cheia
tamanho (lista) : informa o número atual de elementos na lista

Um TAD conjunto é uma coleção de itens similar aos conjuntos matemáticos.

Algumas das operações básicas definidas sobre um conjunto são:

cria (conjunto, capacidade) : cria um novo conjunto, informando o número máximo de elementos que ele pode comportar.
destroi (conjunto) : esvazia/destrói o conjunto
insere (conjunto, elemento) : insere o elemento no conjunto
retira (conjunto, elemento) : retira o elemento do conjunto
pertence (conjunto, elemento) : informa se o elemento pertence ao conjunto
vazio (conjunto) : informa se o conjunto está vazio
tamanho (conjunto) : informa o número atual de elementos no conjunto (cardinalidade)
c3 = uniao (c1, c2) : calcula a união de dois conjuntos
c3 = intersecao (c1, c2) : calcula a interseção de dois conjuntos
c3 = diferenca (c1, c2) : calcula a diferença de dois conjuntos
igual (c1, c2) : informa se os conjuntos c1 e c2 são iguais
contem (c1, c2) : informa se c1 contém c2 (c2 é subconjunto de c1)
…

Um TAD fila de prioridade é uma fila na qual cada elemento é associado a uma chave (prioridade) e a fila é mantida ordenada segundo os valores das chaves. Por exemplo, considerando uma fila de prioridades fp inicialmente vazia:

operação (valor, chave)	conteúdo da fila
insere (5, 3)	[ (5, 3) ]
insere (0, 6)	[ (5, 3) (0, 6) ]
insere (1, 1)	[ (1, 1) (5, 3) (0, 6) ]
insere (-2, 2)	[ (1, 1) (-2, 2) (5, 3) (0, 6) ]
insere (8, 2)¹⁾	[ (1, 1) (-2, 2) (8, 2) (5, 3) (0, 6) ]
insere (9, 4)	[ (1, 1) (-2, 2) (8, 2) (5, 3) (9, 4) (0, 6) ]
retira min	[ (-2, 2) (8, 2) (5, 3) (9, 4) (0, 6) ]
retira min	[ (8, 2) (5, 3) (9, 4) (0, 6) ]
retira max	[ (8, 2) (5, 3) (9, 4) ]

Algumas das operações básicas definidas sobre uma fila de prioridades são:

cria (fila, capacidade) : cria uma nova fila, informando o número máximo de elementos que ela pode comportar; uma fila pode ser considerada infinita, se não tiver capacidade máxima definida.
destroi (fila) : esvazia/destrói a fila
insere (fila, elemento, chave) : insere um novo elemento na fila, posicionado de acordo com o valor da chave informada (prioridade)
elemento = retira_min (fila) : retira o elemento da fila que tem a menor chave/prioridade
elemento = retira_max (fila) : retira o elemento da fila que tem a maior chave/prioridade
valor_min (fila) : informa o valor do elemento que tem a menor prioridade, sem alterar a fila
valor_max (fila) : informa o valor do elemento que tem a maior prioridade, sem alterar a fila
chave_min (fila) : informa o valor da menor prioridade, sem alterar a fila
chave_max (fila) : informa o valor da maior prioridade, sem alterar a fila
vazia (fila) : informa se a fila está vazia
cheia (fila) : informa se a fila está cheia
tamanho (fila) : informa o número atual de elementos na fila
…

Filas de prioridades têm muitos usos em computação, como na implementação de simuladores, no processamento de pacotes de rede, em algoritmos de compressão de dados e no cálculo de rotas em mapas.

Implemente o TAD “fila de inteiros” usando um vetor alocado dinamicamente para armazenar os inteiros.
Idem, usando uma lista de structs alocadas dinamicamente e ligadas por ponteiros (lista encadeada).
Compare as duas implementações sob os seguintes aspectos:
1. simplicidade da implementação;
2. rapidez das operações para inserir e remover elementos;
3. uso total de memória;
4. flexibilidade no uso da memória.
Repita os itens acima para os TADs pilha, lista e conjunto.

¹⁾

Se dois valores têm a mesma chave, devem ser inseridos e retirados em ordem FIFO.

Tipos abstratos de dados

Fila

Pilha

Deque

Lista

Conjunto

Fila de prioridade

Exercícios