Hoje, no dia 170 do nosso curso de Ciências da Computação, vamos mergulhar em um dos tópicos mais importantes da computação: estruturas de dados. Durante nossas aulas, já vimos diversos conceitos fundamentais sobre algoritmos e programação, e agora chegou a hora de entender como organizar e manipular dados de forma eficiente. Estruturas de dados são formas padronizadas de armazenar e gerenciar informações em um computador, permitindo que operações como inserção, remoção, busca e ordenação sejam realizadas de maneira controlada e com complexidades previsíveis.

Nesta aula, vamos focar em três estruturas clássicas e amplamente utilizadas: listas encadeadas, pilhas e filas. Cada uma delas resolve um conjunto específico de problemas e possui características próprias de acesso, inserção e remoção de elementos.

Listas Encadeadas

Começamos com listas encadeadas. Uma lista encadeada é uma estrutura de dados linear composta por nós, onde cada nó contém um valor — o dado propriamente dito — e uma referência (ponteiro) para o próximo nó da sequência. Diferentemente dos arrays, que vimos em aulas passadas, as listas encadeadas não ocupam espaço contíguo na memória. Isso significa que inserções e remoções podem ser feitas sem a necessidade de realocar ou deslocar uma quantidade grande de elementos.

Existem dois tipos principais: listas simplesmente encadeadas, onde cada nó aponta apenas para o próximo elemento; e listas duplamente encadeadas, onde cada nó possui referências tanto para o próximo quanto para o anterior, permitindo navegação bidirecional.

As operações básicas em uma lista encadeada incluem:

  • Inserção no início: O(1) — basta criar um novo nó e ajustar o ponteiro da cabeça da lista.
  • Inserção no final: O(n) em uma lista simples sem referência ao último nó; O(1) se mantivermos um ponteiro para a cauda.
  • Remoção: similar à inserção — remover do início é O(1), remover do final ou de uma posição específica exige percorrer a lista.
  • Busca: O(n) no pior caso, pois precisamos percorrer os nós sequencialmente até encontrar o elemento desejado.

Vamos ver um exemplo simples de implementação em Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Listas encadeadas são especialmente úteis quando precisamos de inserções e remoções frequentes em posições arbitrárias, e quando o tamanho dos dados é dinâmico e imprevisível. Elas também servem como base para implementar estruturas mais complexas, como tabelas hash com encadeamento separado e alocadores de memória.

Pilhas (Stacks)

A segunda estrutura que estudamos hoje foi a pilha. Uma pilha segue o princípio LIFO (Last In, First Out): o último elemento inserido é o primeiro a ser removido. A analogia clássica é uma pilha de pratos — você coloca pratos no topo e retira do topo também.

As operações fundamentais de uma pilha são:

  • Push: insere um elemento no topo da pilha.
  • Pop: remove e retorna o elemento do topo.
  • Peek ou Top: consulta o elemento do topo sem removê-lo.
  • isEmpty: verifica se a pilha está vazia.

Todas essas operações têm complexidade O(1) em uma implementação eficiente, seja usando arrays dinâmicos ou listas encadeadas.

As aplicações de pilhas são inúmeras no dia a dia da computação:

  • Sistema de undo/redo em editores de texto e IDEs.
  • Call stack dos programas: o mecanismo que gerencia chamadas de funções e retornos.
  • Avaliação de expressões matemáticas, especialmente em notação polonesa reversa (RPN).
  • Algoritmos de backtracking, como o problema das N-Rainhas e busca em profundidade (DFS).
  • Parser e validação de sintaxe, como verificar se parênteses, colchetes e chaves estão balanceados.

Exemplo de implementação simples em Python:

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

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

    def size(self):
        return len(self.items)

Percebam como a implementação com lista (array dinâmico) do Python já nos dá push e pop eficientes no final. Para problemas onde o tamanho máximo é conhecido e queremos evitar realocações, podemos implementar com um array de tamanho fixo e um índice de topo.

Filas (Queues)

A terceira estrutura da aula foi a fila. Diferente da pilha, a fila segue o princípio FIFO (First In, First Out): o primeiro elemento que entra é o primeiro a sair. A analogia aqui é uma fila de pessoas em um banco ou supermercado — quem chega primeiro é atendido primeiro.

Operações básicas de uma fila:

  • Enqueue: insere um elemento no final (cauda) da fila.
  • Dequeue: remove e retorna o elemento do início (cabeça) da fila.
  • Front: consulta o elemento do início sem removê-lo.
  • Rear ou Back: consulta o elemento do final da fila.
  • isEmpty: verifica se a fila está vazia.

Existem variações importantes de filas:

  • Fila circular: otimiza o uso de espaço em implementações baseadas em array, reutilizando posições que já foram removidas.
  • Fila de prioridades: elementos com maior prioridade são atendidos primeiro, independentemente da ordem de chegada. Geralmente implementada com uma heap.
  • Deque (Double-Ended Queue): permite inserções e remoções em ambas as extremidades, com complexidade O(1).

Aplicações comuns de filas incluem:

  • Escalonamento de processos em sistemas operacionais — fila de prontos, fila de dispositivos.
  • Buffers de dados, como em streaming de áudio/vídeo e pipes entre processos.
  • Filas de mensagens em sistemas distribuídos e microsserviços.
  • Algoritmos de busca em largura (BFS) em grafos.
  • Gerenciamento de impressão e outras filas de recursos compartilhados.

Implementação usando a classe deque do Python, que oferece operações eficientes nas duas pontas:

from collections import deque

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

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

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

    def front(self):
        if not self.is_empty():
            return self.items[0]
        return None

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

    def size(self):
        return len(self.items)

Comparação e Escolha da Estrutura

Uma dúvida comum é: quando usar cada uma dessas estruturas? A escolha depende do problema que estamos resolvendo e do padrão de acesso aos dados.

  • Listas encadeadas são ideais quando precisamos de inserções e remoções frequentes em posições arbitrárias, especialmente no início da lista, e quando o tamanho dos dados é muito dinâmico. O custo é a busca sequencial O(n) e o overhead de memória dos ponteiros.
  • Pilhas são a escolha natural quando a ordem de processamento exige que o elemento mais recente seja processado primeiro. Problemas como histórico de navegação, undo/redo, parsing de expressões e DFS se encaixam perfeitamente.
  • Filas devem ser usadas quando a ordem de chegada precisa ser preservada. Processos em SO, BFS em grafos, buffers e sistemas de atendimento são exemplos clássicos.

Vale notar que essas três estruturas podem ser implementadas umas a partir das outras. Por exemplo, podemos implementar uma fila usando duas pilhas, e uma pilha pode ser implementada com uma lista encadeada. Essa interconexão mostra como esses conceitos são fundamentais e versáteis.

Perguntas Frequentes

Qual a diferença principal entre array e lista encadeada?

Arrays armazenam elementos em posições contíguas de memória, permitindo acesso aleatório O(1) pelo índice, mas inserções e remoções no meio custam O(n) por exigir deslocamento. Listas encadeadas armazenam nós dispersos com ponteiros, oferecendo inserções e remoções O(1) quando já temos a referência ao nó, mas o acesso sequencial é O(n) e há overhead de memória para os ponteiros.

Pilhas e filas podem ser implementadas com arrays?

Sim. Ambas podem ser implementadas com arrays (ou listas em Python). A implementação com array é mais eficiente em termos de cache e alocação contígua, mas requer gerenciamento de capacidade — precisamos redimensionar quando a estrutura cresce. A implementação com listas encadeadas oferece crescimento dinâmico sem realocação, mas com overhead de ponteiros e possível perda de localidade de referência.

O que é uma fila circular e quando usar?

Fila circular é uma implementação baseada em array onde os ponteiros de início (front) e fim (rear) "dão a volta" ao chegar no final do array, reutilizando posições que já foram removidas. Isso evita o desperdício de espaço que ocorre em filas lineares baseadas em array, onde posições no início ficam ociosas após operações de dequeue. É amplamente usada em buffers circulares e implementações de baixo nível.

Para que serve um Deque?

Deque (Double-Ended Queue) permite inserções e remoções eficientes (O(1)) em ambas as extremidades. É útil em algoritmos como busca em largura com pesos 0-1 (0-1 BFS), implementação de janelas deslizantes para encontrar máximos/mínimos em subarrays, problemas de palíndromos e situações onde precisamos de uma estrutura que combine características de pilha e fila.

Essas três estruturas — listas encadeadas, pilhas e filas — formam a base para grande parte dos algoritmos que veremos nas próximas aulas. Dominar os conceitos de operações, complexidades e aplicações de cada uma é essencial para o restante do curso.