Estruturas de Dados Clássicas

Organizar dados na memória, não só guardar

O módulo Ponteiros e Memória Lógica já mostrou onde os dados vivem na memória (Call Stack, Heap) e como apontar para eles. Esta página responde a próxima pergunta: de que formas organizamos vários dados relacionados, de um jeito que torne inserir, remover e buscar informação eficiente para o problema em questão? Cada estrutura abaixo é um Tipo Abstrato de Dados (ADT) — uma forma de organizar dados definida pelas operações que permite, não pela implementação exata.

Pilha (Stack) e Fila (Queue)

Pilha e fila são as estruturas lineares mais simples — a diferença entre elas é por qual ponta você remove um elemento.

Pilha — LIFO

Last In, First Out: o último elemento que entrou é o primeiro a sair. Usada em histórico de "desfazer" (Ctrl+Z), na própria Call Stack de chamadas de função, e na navegação "voltar" do navegador.

Fila — FIFO

First In, First Out: o primeiro elemento que entrou é o primeiro a sair. Usada em filas de impressão, filas de mensagens entre sistemas, e no escalonamento de tarefas de um sistema operacional.

Experimente

Simulador de Pilha e Fila

Estruturas de Dados Lineares (LIFO vs FIFO)

Pilha: o último elemento a entrar é o primeiro a sair (Last In, First Out) — como uma pilha de pratos.

TOPOtarefa2

tarefa1

Exemplos rápidos:

Lista Encadeada (Linked List)

Diferente de um array (bloco contíguo de memória, acesso direto por índice em $O(1)$), uma lista encadeada é uma sequência de nós espalhados pela memória, onde cada nó guarda um valor e um ponteiro para o próximo nó.

[ Dado: 10 | Próximo: 0x006 ] ──▶ [ Dado: 20 | Próximo: 0x00A ] ──▶ [ Dado: 30 | Próximo: NULL ]

Operação	Array	Lista Encadeada
Acesso por posição	$O(1)$ — direto	$O(n)$ — precisa percorrer nó a nó
Inserção no início	$O(n)$ — precisa deslocar todo mundo	$O(1)$ — só reaponta o ponteiro
Uso de memória	Contíguo, previsível	Espalhado, um ponteiro extra por nó

A vantagem da lista encadeada é justamente essa inserção/remoção em $O(1)$ em qualquer ponto, sem precisar mover os outros elementos — o custo é perder o acesso direto por índice.

Árvore Binária de Busca (Binary Search Tree)

Uma árvore binária de busca organiza dados de forma hierárquica: cada nó tem no máximo dois filhos, e mantém a regra "esquerda é menor, direita é maior" em relação ao nó pai.

Essa organização torna a busca muito mais rápida do que percorrer uma lista: a cada comparação, metade da árvore é descartada — o mesmo princípio da busca binária que você já viu, só que aplicado a uma estrutura de dados em vez de um array ordenado.

Operação	Lista Encadeada	Árvore Binária de Busca (balanceada)
Busca	$O(n)$	$O(\log n)$
Inserção	$O(1)$ no início, $O(n)$ em posição ordenada	$O(\log n)$

A palavra "balanceada" importa

Se os dados forem inseridos numa ordem que deixa a árvore "torta" (ex.: sempre inserindo o maior valor), ela degenera numa lista encadeada disfarçada, e a busca volta a ser $O(n)$. Árvores auto-balanceadas (AVL, Red-Black) resolvem isso reorganizando a estrutura automaticamente — fora do escopo introdutório desta página.

Tabela Hash (Hash Table)

Uma tabela hash combina um array com uma função hash: uma função que transforma uma chave (um texto, um número) em um índice do array, permitindo acesso direto em tempo médio $O(1)$ — sem precisar comparar a chave com todas as outras, como uma busca linear faria.

chave "maria"  ──▶  função hash  ──▶  índice 7  ──▶  array[7] = dados de "maria"

Colisões: duas chaves diferentes podem, por coincidência, produzir o mesmo índice. Estratégias comuns para resolver isso incluem guardar uma lista encadeada em cada posição do array (chaining) ou procurar a próxima posição livre (open addressing). Tabelas hash são a estrutura por trás de dicionários/objetos em praticamente toda linguagem de programação moderna (dict em Python, Object/Map em JavaScript).

Qual estrutura usar?

Preciso de...	Estrutura mais adequada
Desfazer a última ação	Pilha
Processar na ordem de chegada	Fila
Inserir/remover muito no início, sem acesso aleatório	Lista Encadeada
Manter dados ordenados com busca rápida	Árvore Binária de Busca
Busca por chave o mais rápido possível	Tabela Hash

Não existe uma estrutura "melhor" — existe a estrutura certa para o padrão de acesso que o problema exige. Essa é a mesma lógica de custo-benefício que apareceu na escolha entre Busca Linear e Busca Binária: a estrutura certa depende do que você vai fazer com os dados, não só de guardá-los.