Durante a aula de hoje, exploramos as estruturas de dados lineares fundamentais para a ciência da computação. Essas estruturas são a base para a organização e manipulação de dados em memória. Vamos revisar os conceitos de Pilhas, Filas e Listas Encadeadas, suas propriedades, implementações e aplicações práticas. Confira outras anotações na página de Posts.
Pilhas (Stacks)
A pilha é uma estrutura LIFO (Last In, First Out). Isso significa que o último elemento inserido é o primeiro a ser removido. É como uma pilha de pratos: o último prato colocado é o primeiro a ser retirado.
Operações básicas
push(item): Insere um item no topo da pilha.pop(): Remove e retorna o item do topo.top()/peek(): Retorna o item do topo sem removê-lo.
Aplicações
- Gerenciamento de chamadas de funções (call stack).
- Algoritmos de desfazer/refazer (undo/redo).
- Parsing de expressões matemáticas (infixa para posfixa).
- Algoritmos de backtracking, como o utilizado no problema das N-Rainhas (visto em aulas futuras).
Filas (Queues)
A fila é uma estrutura FIFO (First In, First Out). O primeiro elemento inserido é o primeiro a ser removido. É como uma fila de banco: quem chega primeiro é atendido primeiro.
Operações básicas
enqueue(item): Insere um item no final da fila.dequeue(): Remove e retorna o item do início da fila.front(): Retorna o item do início sem removê-lo.
Aplicações
- Escalonamento de processos em sistemas operacionais (FCFS - First-Come, First-Served).
- Buffers de dados, como em streams de vídeo ou áudio.
- Algoritmos de busca em largura (BFS - Breadth-First Search) em grafos.
- Gerenciamento de filas de impressão.
Uma variação importante é a Fila Circular, que otimiza o uso de memória em implementações baseadas em array, reaproveitando as posições que já foram removidas.
Listas Encadeadas (Linked Lists)
Diferente das pilhas e filas, que geralmente são construídas sobre arrays ou listas encadeadas, a lista encadeada é uma estrutura dinâmica composta por nós (nodes). Cada nó contém um valor e uma referência (ponteiro) para o próximo nó.
Tipos principais
- Lista Simplesmente Encadeada: Cada nó aponta apenas para o próximo. A navegação é unidirecional.
- Lista Duplamente Encadeada: Cada nó aponta tanto para o próximo quanto para o anterior. Isso permite navegação bidirecional, facilitando operações como remoção de um nó específico.
Operações básicas
- Inserção no início, meio ou fim (O(1) no início, O(n) no pior caso para o fim se não houver ponteiro para o último).
- Remoção de um nó.
- Busca por um valor (O(n) no pior caso).
Vantagens sobre Arrays
- Inserção e remoção no início são O(1), enquanto em arrays (dinâmicos) pode ser O(n) devido ao deslocamento de elementos.
- Tamanho dinamicamente ajustável sem custo de realocação.
- Ideal quando a quantidade de elementos é imprevisível.
Desvantagens
- Acesso a um elemento por índice é O(n), enquanto em arrays é O(1).
- Maior consumo de memória devido ao armazenamento dos ponteiros.
Análise Comparativa de Complexidade
| Operação | Pilha (Array/LD) | Fila (Array/LD) | Lista Encadeada (Simples) |
|---|---|---|---|
| Inserção (início) | O(1) | O(1) (se fila vazia) / O(n) | O(1) |
| Inserção (fim) | O(1) (push) | O(1) (enqueue) | O(n) (sem tail) |
| Remoção (início) | O(n) (pop) | O(1) (dequeue) | O(1) |
| Remoção (fim) | O(1) (pop) | O(1) (se fila vazia) / O(n) | O(n) |
| Acesso (topo/início) | O(1) | O(1) | O(1) |
| Busca | O(n) | O(n) | O(n) |
Nota: LD = Lista Duplamente Encadeada.
Conclusão e Pontos Principais
Nesta aula, consolidamos a base sobre estruturas de dados lineares. Pilhas (LIFO) e Filas (FIFO) são abstrações poderosas para cenários específicos, enquanto Listas Encadeadas oferecem flexibilidade dinâmica para gerenciamento de coleções. A escolha da estrutura correta depende diretamente do problema: precisamos de acesso rápido? Inserção/remoção frequente? Ordem específica de processamento?
Continue acompanhando a série Ciências da computação para mais conteúdo!
Perguntas Frequentes (FAQ)
Qual a principal diferença entre uma pilha e uma fila?
A diferença fundamental é a ordem de remoção. A pilha opera sob a política LIFO (Last In, First Out), enquanto a fila opera sob FIFO (First In, First Out). Um bom macete é lembrar do "prato" para pilha e da "fila de banco" para fila.
Quando devo usar uma lista encadeada em vez de um array?
Listas encadeadas são superiores quando você precisa de inserções e remoções frequentes no início ou no meio da coleção, ou quando o tamanho total da coleção é desconhecido e varia muito. Arrays são melhores para acesso aleatório frequente por índice.
O que é uma lista duplamente encadeada?
É uma variação da lista encadeada onde cada nó possui dois ponteiros: um para o próximo nó e outro para o nó anterior. Isso permite navegar para frente e para trás, tornando operações como remoção de um nó intermediário mais eficientes (O(1) dado o nó), ao custo de maior uso de memória.
O que é uma fila circular e por que usá-la?
A fila circular é uma implementação de fila usando um array que conecta logicamente o final da fila ao seu início. Ela resolve o problema de desperdício de espaço de uma fila linear baseada em array, onde as posições liberadas pela frente da fila não são reutilizadas. Na fila circular, essas posições são reaproveitadas.
Qual a estrutura de dados mais indicada para implementar o algoritmo de busca em largura (BFS)?
A Fila. O BFS explora os vértices do grafo por nível, e uma fila FIFO é a estrutura perfeita para garantir que os vértices sejam visitados na ordem em que são descobertos.