Estruturas de Dados: Listas, Pilhas e Filas

Prévia do material em texto

Estruturas de Dados: Listas, 
Pilhas e Filas
Este material apresenta uma introdução abrangente às estruturas de dados 
fundamentais em ciência da computação, com foco em listas, pilhas e filas 
implementadas em linguagem C. Compreender estas estruturas é essencial 
para desenvolver algoritmos eficientes e solucionar problemas complexos 
de programação.
Por Bruno Mateus Barbosa Santos | Engenharia de Software 3 Estácio
Agenda do Curso
Módulo 1
Conceitos fundamentais da manipulação de dados na memória
Módulo 2
Contraste entre manipulação por encadeamento e estruturas sequenciais
Módulo 3
Algoritmos e características peculiares de pilhas
Módulo 4
Algoritmos e características peculiares de filas
Propósito
Compreender as estruturas de dados como as listas e seus casos particulares, pilhas e filas, desenvolve a capacidade de 
abstração e melhora a compreensão da interligação entre os diversos elementos envolvidos na execução de um programa de 
computador, facilitando a abordagem de conceitos mais complexos, como árvores e grafos, dando ao profissional ferramentas 
que ampliam o portfólio de soluções, facilitando o entendimento e a resolução de problemas.
Preparação Recomendada
Para melhor absorção do conhecimento, recomenda-se o uso de:
Computador com compilador de linguagem C instalado
IDE (Integrated Development Environment) configurada
Material de apoio para consulta durante os exercícios práticos
Caderno para anotações dos conceitos principais
Introdução
Neste tema, abordaremos os conceitos básicos relacionados às estruturas 
de dados, que são organizações coerentes de dados e respectivas 
operações, permitindo manipulação eficiente. São elementos fundamentais 
no aprendizado do profissional de TI.
Apresentaremos o assunto com o emprego da linguagem de programação 
C, concretizando a aplicação dos conceitos aprendidos e evitando uma 
visão apenas teórica. É importante entender que as estruturas de dados são 
conceitos teóricos implementáveis em qualquer linguagem de 
programação.
A sequência de apresentação inicia-se com conceitos genéricos de 
manipulação de memória, seguidos pela estrutura de dados genérica 
chamada lista. As pilhas e filas, apresentadas posteriormente, são casos 
particulares que, por sua relevância, são estudados em maior profundidade.
Módulo 1: Manipulação de 
Dados na Memória
Alocação Sequencial
A alocação sequencial é o armazenamento de dados de forma sequencial 
na memória do computador, com posições de memória contíguas. Em uma 
situação real, a memória do computador é ocupada por diversos dados, 
deixando espaços de tamanhos diversos desocupados.
Para realizar a alocação sequencial, o programa precisa informar 
previamente todo o tamanho de memória necessário, seja em tempo de 
compilação ou de execução.
Alocação Sequencial em C
Em linguagens de alto nível como C, a alocação sequencial é representada 
pelos arrays (vetores). Um vetor indica ao compilador que deve reservar 
posições de memória suficientes para todos os elementos, especificando o 
tipo de dado.
1: [...]
2: int vetor[10];
3: int a = 50;
4: vetor[3] = a;
5: [...]
Na linha 2, instruímos o compilador a reservar posições para 10 elementos 
do tipo inteiro. O número de posições necessárias depende do tamanho do 
tipo de dado e da palavra da memória.
Por exemplo, com inteiros de 16 bits e memória com palavras de 8 bits, cada 
inteiro ocupa 2 posições. Para 10 elementos, seriam necessárias 20 
posições de memória.
Acesso aos Elementos no 
Vetor
Os elementos de um vetor são acessados diretamente através do índice, 
que corresponde ao deslocamento (offset) a partir do endereço do primeiro 
elemento.
No exemplo anterior, a linha vetor[3] = a está atribuindo o valor de "a" ao 
quarto elemento do vetor (em C, o vetor inicia com índice zero). Isso 
representa um salto de 6 posições na memória:
3 (índice) × 2 (posições por elemento) = 6 posições
Esta é uma das principais vantagens da alocação sequencial: o acesso 
direto aos elementos através de cálculos simples de endereçamento.
Vantagens e Desvantagens da Alocação 
Sequencial
Vantagens
Acesso direto e rápido a qualquer elemento através do 
índice
Simplicidade de implementação
Economia de memória (não precisa armazenar ponteiros 
adicionais)
Melhor aproveitamento da localidade espacial na cache do 
processador
Desvantagens
Tamanho fixo definido na criação
Operações de inserção e remoção são ineficientes, pois 
requerem deslocamento de elementos
Desperdício de memória quando não é totalmente utilizada
Difícil redimensionamento em tempo de execução
Operação de Remoção em 
Alocação Sequencial
Em uma lista com alocação sequencial, a remoção de elementos é uma 
operação custosa, pois não é possível desalocar o espaço de memória sem 
comprometer a sequencialidade das posições.
Quando um elemento é removido, todos os elementos posteriores devem 
ser movidos uma posição para frente, para manter a continuidade da 
sequência. Isso tem complexidade O(n) no pior caso, quando o primeiro 
elemento é removido.
Este tipo de operação é mais bem suportado pela alocação dinâmica, que 
veremos posteriormente.
Listas Lineares - Conceitos Básicos
Listas lineares são estruturas de dados não primitivas usadas para reunir um conjunto de elementos relacionados entre si.
Formalmente, uma lista linear é um conjunto de n g 0 nós, cujas propriedades estruturais decorrem unicamente da posição 
relativa dos nós dentro da sequência linear.
Se n = 0, a lista é vazia
Se n > 0, então qualquer nó L[k] (para 1 0
3: para i = 1 até i 0
3: int i = busca(chave)
4: se io tamanho da memória 
em tempo de execução.
[...]
1: int *vetor;
2: vetor = (int *) malloc(tamanho_vetor * sizeof(int));
[...]
A função malloc solicita ao sistema operacional que reserve uma área contígua de memória de tamanho tamanho_vetor * 
sizeof(int).
A variável tamanho_vetor pode ser determinada durante a execução do programa, proporcionando maior flexibilidade.
Em C, o nome do vetor é um ponteiro para o endereço base, e os índices são deslocamentos a partir desse endereço.
Busca Binária em Listas Ordenadas
Em listas ordenadas, podemos aproveitar a ordenação para realizar buscas mais eficientes, 
como a busca binária.
Considere a lista ordenada: [1, 3, 6, 7, 9, 12, 15, 22, 90]
Verificação do Elemento Central
Consultamos o elemento central (9) e verificamos que é maior que o elemento buscado 
(5). Descartamos todos os elementos do meio até o fim.
Redução do Espaço de Busca
Repetimos o procedimento considerando apenas a primeira metade [1, 3, 6, 7, 9]. O 
elemento central (6) ainda é maior que 5.
Conclusão da Busca
Repetimos para o primeiro quarto [1, 3]. Após verificar [3], concluímos que o 
elemento 5 não está na lista.
Este método tem complexidade O(log n), muito mais eficiente que a busca linear.
Implementação da Busca 
Binária em C
int busca_binaria(int lista[], int elemento, int inicio, int fim) {
 int meio = floor((fim + inicio) / 2);
 
 if ((inicio == fim) && (lista[meio] != elemento))
 return -1;
 else if (lista[meio] == elemento)
 return meio;
 else if (elemento aux_dir
Para inserção, o processo é inverso: decrementamos aux_esq para inserir à esquerda ou incrementamos aux_dir para inserir à 
direita.
Listas Circulares
Um problema com deques é que se removermos elementos do início e tentarmos inserir no final quando o vetor estiver cheio, 
haverá desperdício de memória nas posições iniciais que foram liberadas.
Uma solução elegante é utilizar uma lista circular, onde as extremidades direita e esquerda estão ligadas:
Ao ultrapassar o limite superior direito, voltamos à extremidade esquerda
Ao ultrapassar o limite inferior esquerdo, voltamos à extremidade direita
Na prática, isso é implementado através de operações de módulo na aritmética dos índices
Esta abordagem permite um uso mais eficiente da memória alocada.
Aplicações de Listas Sequenciais
As listas sequenciais são amplamente utilizadas em diversas aplicações:
Armazenamento de coleções de dados homogêneos
Implementação de pilhas e filas
Armazenamento de tabelas e matrizes
Implementação de buffers
Algoritmos de ordenação como QuickSort e MergeSort
Processamento de imagens (matrizes de pixels)
A escolha entre alocação sequencial e encadeada depende das operações que serão mais frequentes e das restrições de 
memória.
Módulo 2: Listas Lineares Dinamicamente 
Encadeadas
Problemas da Fragmentação de Memória
A fragmentação de memória ocorre quando, ao longo do tempo, alocações e desalocações deixam espaços de tamanhos distintos 
disponíveis, tornando difícil alocar posições contíguas na heap.
O impacto mais claro da fragmentação é no desempenho, pois o sistema operacional precisa:
Varrer a tabela de alocação buscando espaço suficiente
Verificar se existe um espaço de tamanho idêntico ao necessário
Gerenciar áreas de memória fragmentadas
A alocação encadeada é uma forma de contornar este problema, reduzindo a sobrecarga com o gerenciamento de memória.
Entendendo a Alocação Encadeada
Na alocação encadeada, a relação entre os elementos não é definida pela posição física na memória, mas por referências 
explícitas de um elemento para outro.
Os princípios fundamentais são:
Alocar espaço suficiente para cada elemento individualmente
Manter a relação entre elementos através de ponteiros
Cada elemento (nó) pode estar em qualquer posição da memória
Para acessar os elementos, cada nó contém um campo ponteiro que guarda o endereço do elemento seguinte, formando uma 
"cadeia" de referências.
Tipos de Listas Encadeadas
Lista Simplesmente Encadeada
Cada nó contém apenas um ponteiro que aponta para o 
próximo nó. O movimento só é possível em uma direção.
Lista Duplamente Encadeada
Cada nó contém dois ponteiros: um para o próximo nó e outro 
para o nó anterior. Permite movimento em ambas as direções.
A escolha entre estes tipos depende das operações que serão realizadas e das restrições de memória, já que a lista duplamente 
encadeada utiliza mais memória.
Implementação de Nós em C
Em C, usamos a estrutura struct para definir os nós de uma lista encadeada:
Lista Simplesmente Encadeada
struct No {
 int chave;
 Elemento elemento;
 No *prox;
}
Lista Duplamente Encadeada
struct No {
 int chave;
 Elemento elemento;
 No *prox;
 No *ant;
}
A estrutura No contém campos para armazenar dados (chave e elemento) e ponteiros para outros nós. Em C, a instrução struct 
define um tipo de dado não primário cujos elementos são alocados sequencialmente.
Operações em Listas Encadeadas - Inserção
Para inserir um elemento em uma lista encadeada não ordenada:
Alocar espaço para o novo elemento1.
Fazer o novo elemento apontar para o mesmo nó que o nó cabeça aponta2.
Fazer o nó cabeça apontar para o novo elemento3.
Esta operação insere o novo elemento entre o nó cabeça e os nós existentes, com complexidade O(1).
Busca em Lista Encadeada 
Ordenada
No *buscar(No *no_cabeca, No **aux, int chave) {
 No *atual = no_cabeca->prox;
 *aux = no_cabeca;
 
 while (atual != NULL) {
 if (atual->chave prox;
 }
 else if (atual->chave == chave) {
 return atual; //elemento encontrado
 }
 else
 return NULL; //elemento não encontrado
 }
 return NULL; //lista vazia
}
Esta função aproveita a busca para retornar o endereço do elemento 
imediatamente anterior ao buscado, caso este não esteja na lista. Isso torna 
a função útil para a inserção.
Em uma lista não ordenada, a busca precisa prosseguir até encontrar o 
elemento ou o fim da lista.
Implementação da Inserção 
em Lista Encadeada
int inserir(No *no_ant, Elemento novo_elemento, int chave) {
 No *aux, *anterior = no_cabeca;
 No *novo_no = (No *) calloc(1, sizeof(No));
 
 aux = buscar(no_cabeca, &anterior, chave);
 
 if ((novo_no == NULL) || (aux != NULL))
 return 0; //falha na inserção
 else {
 novo_no->elemento = novo_elemento;
 novo_no->chave = chave;
 novo_no->prox = anterior->prox;
 anterior->prox = novo_no;
 return 1; //inserção bem sucedida
 }
}
A função aloca memóriapara o novo nó, verifica se a alocação foi bem-
sucedida e se o elemento já existe, e então realiza a inserção conectando o 
novo nó na posição correta.
Passos da Inserção em Lista 
Encadeada
Alocação de Memória
Criamos um novo nó com calloc e preenchemos com os novos valores.
Atualização de Ponteiros
Fazemos o campo prox do novo nó apontar para o mesmo nó que o anterior aponta.
Conexão com a Lista
Fazemos o campo prox do nó anterior apontar para o novo nó, concluindo a 
inserção.
Este procedimento funciona tanto para listas ordenadas quanto não ordenadas, com a 
diferença de que na lista ordenada a posição é determinada pela ordem das chaves.
Remoção em Lista 
Encadeada
remover(No *no_cabeca, int chave) {
 No *aux, *anterior = no_cabeca;
 
 aux = buscar(no_cabeca, &anterior, chave);
 
 if (aux != NULL) {
 anterior->prox = aux->prox;
 free(aux);
 return 1; //remoção bem sucedida
 } else
 return 0; //falha remoção
}
A remoção em lista encadeada é simples e eficiente:
Fazer o nó anterior ao removido apontar para o nó posterior1.
Desalocar o nó removido com a função free2.
Esta é uma grande vantagem da alocação encadeada: os elementos podem 
ser efetivamente desalocados da memória sem afetar a estrutura da lista.
Listas Circulares 
Encadeadas
Assim como na alocação sequencial, podemos transformar uma lista 
encadeada em circular:
Em lista simplesmente encadeada: o último nó aponta para o nó cabeça
Em lista duplamente encadeada: o último nó aponta para o nó cabeça, e 
o nó cabeça aponta para o último nó
Em uma lista simplesmente encadeada circular, o percurso ainda é 
unidirecional, mas pode continuar indefinidamente. Em uma lista 
duplamente encadeada circular, o percurso pode ser feito em ambos os 
sentidos e também pode continuar indefinidamente.
Aplicações de Listas Encadeadas
As listas encadeadas são amplamente utilizadas em diversas aplicações:
Implementação de pilhas e filas dinâmicas
Gerenciamento de memória em sistemas operacionais
Representação de grafos (listas de adjacência)
Implementação de tabelas hash com encadeamento
Editores de texto (para inserção e remoção eficientes)
Histórico de navegação em browsers
Listas de reprodução em players de mídia
Comparação: Alocação Sequencial vs. Encadeada
A escolha entre estas abordagens depende das operações mais frequentes e dos requisitos da aplicação.
Acesso
Sequencial: O(1) - acesso direto por 
índice
Encadeada: O(n) - precisa percorrer a 
lista
Inserção
Sequencial: O(n) - necessita deslocar 
elementos
Encadeada: O(1) - apenas atualiza 
ponteiros
Remoção
Sequencial: O(n) - necessita deslocar 
elementos
Encadeada: O(1) - apenas atualiza 
ponteiros
Memória
Sequencial: Menos espaço, mas pode 
haver desperdício
Encadeada: Mais espaço (ponteiros), 
mas sem desperdício
Módulo 3: Pilhas
Conceito e Características
Uma pilha é um tipo particular de lista na qual as operações de inserção, 
remoção e acesso ocorrem sempre numa mesma extremidade, chamada de 
topo.
Uma pilha segue a regra "O último a chegar é o primeiro a sair", também 
conhecida pela sigla LIFO (Last In, First Out). A remoção ocorre na ordem 
inversa da inserção.
Devido a essa característica, pilhas têm a propriedade de inverter 
sequências, o que é útil em diversas aplicações.
Operações Básicas em Pilhas
Empilhamento (Push)
Adiciona um elemento no topo da pilha:
Recebe o elemento a ser inserido1.
Verifica se há espaço disponível2.
Insere o elemento no topo3.
Atualiza o ponteiro/índice do topo4.
Desempilhamento (Pop)
Remove o elemento do topo da pilha:
Verifica se a pilha não está vazia1.
Recupera o valor do elemento do topo2.
Atualiza o ponteiro/índice do topo3.
Retorna o valor recuperado4.
Estas operações são executadas em tempo constante O(1), tornando as pilhas muito eficientes para operações LIFO.
Exemplo de Operações em Pilha
Considere os elementos a, b, c, d, e a serem inseridos em uma pilha (da esquerda para a direita).
Empilhamento (Push)
Pilha Operação Sequência de 
Entrada
{ } push(a) a, b, c, d, e
{ a } push(b) b, c, d, e
{ a, b } push(c) c, d, e
{ a, b, c } push(d) d, e
{ a, b, c, d } push(e) e
{ a, b, c, d, e}
Desempilhamento (Pop)
Pilha Operação Sequência de 
Saída
{ a, b, c, d, e} pop()
{ a, b, c, d } pop() e
{ a, b, c } pop() e, d
{ a, b } pop() e, d, c
{ a } pop() e, d, c, b
{ } e, d, c, b, a
Observe que a sequência de saída está invertida em relação à sequência de entrada, demonstrando a propriedade LIFO.
Aplicações de Pilhas
Desfazer Ações
Cada ação realizada em um programa é 
inserida na pilha. Ao acionar a função de 
desfazer, as ações são desfeitas na ordem 
inversa em que ocorreram (da mais recente 
para a mais antiga).
Execução de Programas
Durante a execução de programas, pilhas são 
usadas para controlar chamadas de função. 
O endereço de retorno é empilhado quando 
uma função é chamada e desempilhado 
quando a função termina.
Avaliação de Expressões
Pilhas são usadas para converter e avaliar 
expressões matemáticas, especialmente na 
conversão entre notações infixa, prefixa 
(polonesa) e pós-fixa (polonesa reversa).
Estas aplicações aproveitam a propriedade LIFO das pilhas para resolver problemas de forma 
elegante e eficiente.
Pilhas em Alocação Sequencial
Na implementação sequencial, a pilha é representada por um vetor e uma variável topo que indica o índice do elemento no topo.
Considerações importantes:
Pilhas com alocação sequencial têm tamanho limitado pelo vetor
É necessário verificar underflow (desempilhar de pilha vazia) e overflow (empilhar em pilha cheia)
Uma pilha vazia é indicada pelo valor de topo = -1 em C
Empilhar significa incrementar o topo e atribuir o valor; desempilhar significa decrementar o topo
Implementação de Pilhas em Alocação 
Sequencial
int push(Elemento elemento) {
 if (topo = 0) {
 valor_recuperado = pilha[topo];
 topo--;
 return valor_recuperado;
 } else
 return NULL; //falha
}
Função Pop (Desempilhar)
Estas implementações simples garantem operações eficientes O(1) e prevenção de erros de overflow e underflow.