Ciências da computação dia 210

Nesta aula, exploramos as estruturas de dados lineares fundamentais: listas encadeadas, pilhas e filas. Essas estruturas são a base para a organização eficiente de dados em memória e aparecem em praticamente todos os sistemas computacionais, desde sistemas operacionais até aplicações web.

Listas Encadeadas

Uma lista encadeada é uma estrutura de dados linear em que cada elemento (nó) contém um valor e uma referência para o próximo nó. Diferentemente de arrays, as listas encadeadas não ocupam um bloco contíguo de memória, o que permite inserções e remoções eficientes em qualquer posição.

Existem dois tipos principais:

• Lista simplesmente encadeada: cada nó aponta apenas para o próximo nó. O acesso é sequencial a partir da cabeça.
• Lista duplamente encadeada: cada nó aponta para o próximo e para o anterior, permitindo navegação bidirecional.

Operações básicas incluem:

• inserir(início, meio, fim) – O(1) no início/fim se mantivermos referências, O(n) no meio.
• remover – O(1) se conhecermos o nó anterior.
• buscar – O(n) no pior caso.

class No:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None

class ListaEncadeada:
    def __init__(self):
        self.cabeca = None

    def insere_inicio(self, valor):
        novo = No(valor)
        novo.proximo = self.cabeca
        self.cabeca = novo

Pilhas

Uma pilha segue o princípio LIFO (Last In, First Out). O último elemento inserido é o primeiro a ser removido. As operações fundamentais são push (empilhar) e pop (desempilhar), ambas O(1).

Pilhas são amplamente utilizadas em:

• Gerenciamento de chamadas de funções (pilha de execução)
• Algoritmos de backtracking
• Navegadores (histórico: voltar/avançar)
• Conversão e avaliação de expressões (notação polonesa)

class Pilha:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def topo(self):
        return self.items[-1] if not self.vazia() else None

    def vazia(self):
        return len(self.items) == 0

Filas

Uma fila segue o princípio FIFO (First In, First Out). O primeiro elemento inserido é o primeiro a ser removido. As operações principais são enqueue (inserir no fim) e dequeue (remover do início), ambas O(1) quando implementadas com listas encadeadas ou vetores circulares.

Aplicações comuns:

• Buffers de dados (ex.: buffer de teclado)
• Escalonamento de processos em sistemas operacionais
• Filas de impressão
• BFS (Busca em Largura) em grafos

from collections import deque

class Fila:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.popleft() if not self.vazia() else None

    def vazia(self):
        return len(self.items) == 0

Variações e Implementações Avançadas

Além das estruturas básicas, existem variações importantes que aparecem com frequência em problemas reais:

• Lista Circular: o último nó aponta de volta para o primeiro, formando um ciclo. É ideal para implementar buffers de tamanho fixo (buffer circular) e escalonamento do tipo round‑robin, onde os processos são atendidos em ordem cíclica.
• Deque (Double‑Ended Queue): permite inserção e remoção tanto no início quanto no fim. Combina características de pilha e fila, sendo útil em algoritmos que exigem acesso flexível às extremidades. Em Python, a classe collections.deque fornece uma implementação otimizada com operações O(1) em ambas as pontas.
• Fila Circular: implementada com um array de tamanho fixo e dois índices (início e fim). As operações de enqueue e dequeue são feitas com aritmética modular, eliminando a necessidade de redimensionamento e evitando desperdício de memória. É amplamente usada em sistemas embarcados e drivers de dispositivo.
• Pilha como Validador de Expressões: uma aplicação clássica de pilhas é a verificação de pares de parênteses, colchetes e chaves em expressões matemáticas. Cada caractere de abertura é empilhado; ao encontrar um fechamento, verifica‑se se o topo corresponde.
• Fila em Busca em Largura (BFS): em grafos, a fila é a estrutura central do algoritmo BFS, que visita os vértices por níveis a partir de uma origem. A ordem FIFO garante que os vértices sejam processados em ordem crescente de distância.

Dominar essas variações permite escolher a estrutura mais adequada para cada problema, equilibrando desempenho e simplicidade.

Comparação entre as Estruturas

Perguntas Frequentes

Qual a diferença entre pilha e fila?

Pilha utiliza o princípio LIFO (último a entrar, primeiro a sair), enquanto fila utiliza FIFO (primeiro a entrar, primeiro a sair). Em uma pilha, inserimos e removemos pelo mesmo lado (topo); em uma fila, inserimos por um lado (fim) e removemos pelo outro (início).

Quando usar lista encadeada em vez de array?

Listas encadeadas são preferíveis quando há muitas inserções e remoções em posições arbitrárias, especialmente no início, pois arrays exigem deslocamento de elementos. Por outro lado, arrays oferecem acesso aleatório O(1) e melhor localidade de cache, sendo mais adequados para acesso frequente por índice.

O que é uma lista duplamente encadeada?

É uma variação da lista encadeada em que cada nó possui dois ponteiros: um para o próximo nó e outro para o nó anterior. Isso permite percorrer a lista em ambas as direções e facilita operações de remoção quando se tem apenas a referência ao nó a ser removido (sem precisar do nó anterior).

O que é uma fila circular?

Uma fila circular é uma implementação de fila sobre um array de tamanho fixo, onde os índices de início e fim "dão a volta" ao chegar no final do array (usando operação de módulo). Isso evita o desperdício de espaço que ocorreria se apenas removêssemos do início sem reaproveitar as posições liberadas. É muito usada em buffers de hardware e sistemas de tempo real.

Qual a diferença entre um deque e uma fila comum?

Um deque (double‑ended queue) permite inserir e remover elementos em ambas as extremidades, enquanto uma fila comum só insere no fim e remove no início. O deque é mais flexível e pode ser usado tanto como fila quanto como pilha. No entanto, para cenários estritamente FIFO ou LIFO, as estruturas especializadas são semanticamente mais claras.

---

Essas estruturas formam a base para tópicos mais avançados, como árvores, grafos e tabelas hash. Dominá-las é essencial para qualquer cientista da computação.