Nesta aula, mergulhamos nas estruturas de dados lineares fundamentais: listas encadeadas, pilhas e filas. Compreender essas estruturas é crucial para escrever programas eficientes e para entender como os sistemas gerenciam memória e dados. Discutimos suas propriedades, operações, implementações e casos de uso, sempre com exemplos práticos e análise de complexidade.

Listas Encadeadas

Uma lista encadeada é uma coleção de nós, onde cada nó contém um valor e um ponteiro para o próximo nó (no caso de listas simplesmente encadeadas) ou também para o anterior (listas duplamente encadeadas). Diferente de arrays, as listas não exigem um bloco contíguo de memória, permitindo inserções e remoções eficientes em qualquer posição, desde que se tenha referência ao nó anterior. A estrutura de um nó em C pode ser definida como:

struct Node {
    int data;
    struct Node* next;
};

As operações principais são:

  • Inserir no início: O(1) se houver ponteiro para a cabeça da lista.
  • Inserir no final: O(n) sem cauda; O(1) com referência ao final (tail).
  • Remover um nó: O(1) se tivermos referência ao nó anterior.
  • Buscar: O(n) no pior caso, pois é necessário percorrer a lista sequencialmente.

Listas duplamente encadeadas armazenam dois ponteiros (anterior e próximo), permitindo navegação bidirecional e remoção mais flexível, mas consomem mais memória. Vimos exemplos de implementação em Python usando classes, destacando as diferenças entre alocação estática e dinâmica. Trade-offs: listas encadeadas são ideais quando o tamanho dos dados é desconhecido e há muitas inserções/remoções, mas o acesso aleatório é lento.

Pilhas (Stacks)

Uma pilha segue a política LIFO (Last In, First Out). As operações fundamentais são:

  • push: adiciona um elemento ao topo.
  • pop: remove o elemento do topo.
  • top/peek: consulta o topo sem remover.

Pilhas podem ser implementadas com arrays ou listas encadeadas. Em ambas, push e pop têm complexidade O(1) (no caso de array dinâmico, push é amortizado O(1)). Exemplo de implementação simples em Python usando lista nativa:

stack = []
stack.append(1)  # push
top = stack[-1]  # peek
stack.pop()      # pop

Aplicações importantes incluem:

  • Controle de chamadas de funções (pilha de execução) — essencial para entender recursão.
  • Mecanismo de desfazer/refazer (undo/redo) em editores de texto.
  • Avaliação de expressões e conversão para notação polonesa reversa (RPN).
  • Algoritmos de backtracking, como o problema das N-Rainhas visto em aulas anteriores.

Discutimos também o fenômeno de stack overflow quando a pilha atinge seu limite, e como gerenciar a memória em linguagens sem coleta automática.

Filas (Queues)

Uma fila segue a política FIFO (First In, First Out). As operações principais são:

  • enqueue: insere no final da fila.
  • dequeue: remove do início da fila.
  • front: consulta o primeiro elemento.

Filas podem ser implementadas com arrays circulares ou listas encadeadas. A implementação com array circular evita desperdício de espaço e mantém enqueue/dequeue em O(1). Exemplo conceitual:

class CircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.head = 0
        self.tail = 0
        self.size = 0
        self.capacity = k

Aplicações comuns:

  • Escalonamento de processos em sistemas operacionais (fila de prontos).
  • Filas de impressão.
  • Algoritmos de busca em largura (BFS) em grafos.
  • Buffers de dados para transmissão de áudio/vídeo.

Vimos a diferença entre filas simples e circulares, e como a escolha da implementação afeta o desempenho em cenários de alta concorrência.

Comparação e Escolha

A escolha da estrutura de dados correta depende do problema a ser resolvido. Arrays oferecem acesso aleatório O(1) e melhor localidade de cache, mas inserções e remoções no meio são O(n). Listas encadeadas têm inserções e remoções O(1) se a posição for conhecida, mas acesso sequencial O(n) e maior overhead de memória. Pilhas e filas são estruturas restritas que garantem contratos específicos e são fáceis de implementar de forma eficiente.

Quando o problema requer processamento em ordem inversa (como desfazer ações), pilha é a escolha natural. Quando a ordem de chegada deve ser preservada (como em uma fila de tarefas), fila é a ideal. Para cenários que exigem operações frequentes no meio da coleção, listas encadeadas ou estruturas mais avançadas como árvores podem ser mais adequadas. Analisamos trade-offs com exemplos concretos, incluindo a implementação de um pequeno simulador de fila de banco.

Pontos-chave desta aula

  • Listas encadeadas: inserção e remoção eficientes, acesso sequencial.
  • Pilhas: LIFO, push/pop O(1) (com implementação adequada).
  • Filas: FIFO, enqueue/dequeue O(1) com buffer circular.
  • Estruturas lineares são blocos de construção para estruturas mais complexas.
  • A escolha da estrutura impacta diretamente a eficiência do algoritmo.

Perguntas Frequentes

1. Qual a diferença entre pilha e fila?

Pilha segue LIFO (último a entrar, primeiro a sair), enquanto fila segue FIFO (primeiro a entrar, primeiro a sair).

2. Quando usar lista encadeada em vez de array?

Use lista encadeada quando precisar de inserções e remoções frequentes no início ou meio, ou quando o tamanho dos dados é desconhecido e variável. Use array quando o acesso aleatório é frequente e o tamanho é conhecido.

3. Uma fila pode ser implementada com pilhas?

Sim, usando duas pilhas é possível simular uma fila (uma para entrada e outra para saída).

4. O que é uma lista duplamente encadeada?

É uma lista onde cada nó possui ponteiros tanto para o próximo quanto para o anterior, permitindo navegação bidirecional e remoção mais eficiente de um nó quando se tem referência a ele.