Em ciência da computação, estruturas de dados são formas de organizar, gerenciar e armazenar dados de maneira que possam ser utilizados de forma eficiente. Nesta aula, exploramos três estruturas fundamentais: listas encadeadas, pilhas e filas. Compreender cada uma delas, suas operações e complexidades, é essencial para construir algoritmos robustos e para o sucesso em disciplinas mais avançadas.

Embora existam muitas estruturas, estas três são a base para tópicos como alocação dinâmica, gerenciamento de memória, algoritmos de busca e ordenação, e sistemas operacionais. Vamos detalhar cada uma a seguir.

Listas encadeadas

Uma lista encadeada (linked list) é uma estrutura linear composta por nós, onde cada nó contém um valor e uma referência (ponteiro) para o próximo nó da sequência. Diferente de arrays, as listas encadeadas não exigem um bloco contínuo de memória, permitindo inserções e remoções eficientes em qualquer posição (desde que se tenha acesso ao ponto desejado).

Existem variações comuns:

  • Lista simplesmente encadeada: cada nó aponta apenas para o próximo. A navegação é unidirecional.
  • Lista duplamente encadeada: cada nó possui ponteiros para o próximo e para o anterior, permitindo percorrer nos dois sentidos.
  • Lista circular: o último nó aponta de volta para o primeiro, formando um ciclo.

As operações básicas incluem inserção (no início, no fim ou no meio), remoção e busca. Em uma lista simplesmente encadeada, a inserção no início é O(1), enquanto a inserção no fim exige percorrer até o último nó (O(n)). A busca, no pior caso, é O(n). 

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

    def exibe(self):
        atual = self.cabeca
        while atual:
            print(atual.valor, end=' > ')
            atual = atual.proximo
        print('None')

Listas encadeadas são usadas em implementações de pilhas e filas (como veremos), em gerenciamento de memória do sistema operacional, em tabelas hash com encadeamento separado para tratar colisões, entre outros.

Pilhas (Stacks)

Uma pilha é uma estrutura linear que segue a política LIFO (Last In, First Out): o último elemento inserido é o primeiro a ser removido. As duas operações fundamentais são push (inserir no topo) e pop (remover do topo). Também é comum a operação peek (consultar o topo sem remover).

Pilhas podem ser implementadas com arrays (com capacidade fixa) ou com listas encadeadas (crescimento dinâmico). A versão com lista encadeada tem inserção e remoção no topo em O(1) e não sofre com redimensionamento. 

class Pilha:
    def __init__(self):
        self.topo = None

    def push(self, valor):
        novo = No(valor)
        novo.proximo = self.topo
        self.topo = novo

    def pop(self):
        if self.topo is None:
            return None
        valor = self.topo.valor
        self.topo = self.topo.proximo
        return valor

    def peek(self):
        return self.topo.valor if self.topo else None

Aplicações clássicas de pilhas incluem: reversão de strings, verificação de parênteses balanceados, execução de desfazer/refazer (undo/redo), avaliação de expressões (notação polonesa reversa) e gerenciamento de pilha de chamadas (call stack) em linguagens de programação.

Filas (Queues)

Uma fila é uma estrutura linear que segue a política FIFO (First In, First Out): o primeiro elemento inserido é o primeiro a ser removido. As operações principais são enqueue (inserir no final) e dequeue (remover do início). Também podemos ter front para consultar o início sem remover.

Assim como as pilhas, filas podem ser implementadas com arrays (fila circular para reaproveitar espaço) ou com listas encadeadas. A implementação com lista encadeada mantém ponteiros para o início (head) e para o fim (tail) para que ambas as operações sejam O(1). 

class Fila:
    def __init__(self):
        self.inicio = None
        self.fim = None

    def enqueue(self, valor):
        novo = No(valor)
        if self.fim:
            self.fim.proximo = novo
        else:
            self.inicio = novo
        self.fim = novo

    def dequeue(self):
        if self.inicio is None:
            return None
        valor = self.inicio.valor
        self.inicio = self.inicio.proximo
        if self.inicio is None:
            self.fim = None
        return valor

Filas são amplamente utilizadas: escalonamento de processos em sistemas operacionais, gerencia de filas de impressão, buffers de dados, algoritmos de busca em largura (BFS) e processamento de tarefas assíncronas.

Comparação de complexidades

Operação Lista encadeada (início) Pilha (topo) Fila (início/fim)
Inserção O(1) O(1) O(1) (no fim)
Remoção O(1) O(1) O(1)
Busca O(n) — (não usual) — (não usual)
Acesso ao topo/início O(1) O(1) O(1)

Perguntas frequentes

Qual a diferença entre pilha e fila?

A principal diferença está na política de remoção: pilha usa LIFO (último a entrar, primeiro a sair), enquanto fila usa FIFO (primeiro a entrar, primeiro a sair). Isso reflete diretamente nas aplicações: pilha é adequada para tarefas que exigem reversão (undo) e chamadas recursivas; fila é adequada para processamento por ordem de chegada.

Quando usar lista encadeada em vez de array?

Listas encadeadas são preferíveis quando há muitas inserções e remoções no meio da estrutura, pois essas operações são O(1) após localizar a posição (com array, remover/inserir no início ou no meio exige deslocar elementos, O(n)). Arrays são melhores para acesso aleatório (O(1)) e quando o tamanho é conhecido antecipadamente.

Pilha com array ou com lista encadeada?

Arrays oferecem melhor localidade de cache e menor overhead de memória, mas podem exigir redimensionamento. Listas encadeadas crescem sob demanda e cada push/pop é O(1) sem realocação. A escolha depende do contexto: para profundidade máxima conhecida, array é mais eficiente; para uso geral, prefere-se lista encadeada.

Como implementar uma fila com duas pilhas?

É um exercício clássico: para enfileirar, basta empilhar na primeira pilha. Para desenfileirar, se a segunda pilha estiver vazia, transfira todos os elementos da primeira para a segunda (invertendo a ordem) e então desempilhe o topo da segunda. Essa abordagem garante um custo amortizado O(1) por operação.

Estas estruturas são a base para muitas outras, como árvores, grafos e tabelas hash. Dominá-las é essencial para qualquer estudante de ciência da computação. Para mais aulas como esta, confira a página de Posts ou explore outros tópicos em Tags.