Estruturas de dados avançadas: pilha, fila, árvore, grafo e hash

O nível depois do básico: pilha, fila, lista ligada, árvore, grafo e tabela hash, a altura e os tipos de árvore binária, AVL, heap e trie, com os algoritmos BFS, DFS, merge e quick sort, backtracking e memoização, na ordem certa de estudo.

Revisão técnica: Cesar GargiuloMDN Web Docs - JSON.parse / MDN Web Docs - JSON.stringify
Calcule agora: Formatador de JSONResultado na hora, de graça e sem cadastro.

Depois de dominar as estruturas básicas (listas, dicionários, conjuntos) e a busca e ordenação clássicas, vem o nível que separa quem monta programas de quem projeta soluções: pilhas, filas, listas ligadas, árvores, grafos e tabelas hash, com os algoritmos que operam sobre elas. Este guia explica cada estrutura, quando usar qual e em que ordem estudar, sem matemática pesada. Para aprender tudo isso na prática, com um laboratório de algoritmos e projeto final, use o Curso de Lógica de Programação Avançado, que é gratuito e fecha a Trilha Lógica.

Resposta rápida

  • As estruturas avançadas centrais são pilha, fila, lista ligada, árvore, grafo e tabela hash.
  • Os algoritmos que operam nelas são BFS e DFS (percurso de grafos), merge sort e quick sort (ordenação) e backtracking e memoização.
  • Recursão é o motor por trás da maioria: uma função que chama a si mesma até um caso base.
  • Estude na ordem: primeiro as lineares, depois a tabela hash, depois árvores e, por fim, grafos.

Estruturas lineares: pilha, fila e lista ligada

Antes de mergulhar nas estruturas ramificadas, vale firmar as lineares, que guardam itens em sequência mas com regras de acesso próprias. A pilha segue o modelo LIFO: o último item a entrar é o primeiro a sair, como uma pilha de pratos onde você só pega o de cima. Ela é a estrutura do botão desfazer, do histórico de navegação e da forma como o próprio computador controla chamadas de função. A fila segue o oposto, FIFO: quem chega primeiro é atendido primeiro, como a fila do caixa. Serve para processar tarefas na ordem em que surgiram, de mensagens a impressões. Já a lista ligada encadeia elementos onde cada um aponta para o próximo, o que torna inserir e remover no meio barato, sem empurrar todos os vizinhos como uma lista comum faria. O custo é que você não pula direto para uma posição: precisa seguir os ponteiros. Entender ponteiro aqui é o que destrava as árvores e os grafos depois.

Tabela hash: a busca instantânea por trás do dicionário

Quando você usa um dicionário e a linguagem acha o valor de uma chave na hora, quem faz esse trabalho é a tabela hash. A ideia é elegante: uma função de hash converte a chave (um nome, um código) em um número que aponta direto para uma posição na memória. Guardar e recuperar vira acesso direto ao endereço, sem varrer item por item, por isso o custo médio é O(1), tempo constante mesmo com milhões de registros. O detalhe que todo estudante precisa conhecer são as colisões: às vezes duas chaves diferentes geram o mesmo endereço, e a estrutura resolve isso guardando os dois numa pequena lista naquele ponto ou procurando o próximo espaço livre. Saber que a tabela hash existe por baixo do dicionário explica por que buscar por chave é tão mais rápido que buscar por valor, e ajuda a escolher a estrutura certa em vez de varrer listas à toa.

Árvores: hierarquia e busca eficiente

A árvore organiza dados em hierarquia: um nó raiz que se ramifica em filhos, que por sua vez têm filhos, como um organograma ou a estrutura de pastas do computador. A mais estudada é a árvore binária de busca, em que cada nó tem no máximo dois filhos e vale uma regra simples: valores menores vão para a esquerda, maiores para a direita. Isso permite buscar, inserir e remover em cerca de O(log n) passos quando a árvore está equilibrada, muito mais rápido que percorrer uma lista. Percorrer uma árvore também tem seus métodos (em ordem, pré-ordem, pós-ordem), e cada um serve a um propósito, de listar valores ordenados a copiar a estrutura inteira. As árvores são o primeiro contato de verdade com recursão aplicada, porque percorrer uma árvore é naturalmente recursivo: para visitar um nó, você visita suas subárvores, que são árvores menores.

Altura, tipos de árvore binária, AVL, heap e trie

Na árvore binária, cada nó tem no máximo dois filhos, o esquerdo e o direito. A medida que mais cai em prova e em entrevista é a altura: o dicionário de algoritmos do NIST, o instituto de padrões dos Estados Unidos, a define como a maior distância de um nó até a raiz, de modo que a árvore com um nó só tem altura zero. O cálculo é recursivo: a altura de um nó é 1 mais a maior altura entre as duas subárvores.

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

def altura(no):
    if no is None:
        return -1   # assim a árvore de um nó só tem altura 0
    return 1 + max(altura(no.esquerda), altura(no.direita))

raiz = No(8, No(3, No(1), No(6)), No(10))
print(altura(raiz))   # 2: o caminho mais longo é 8, 3, 1

Alguns livros contam nós em vez de arestas e chegam a um número uma unidade maior; na prova, siga a convenção do enunciado. Os tipos de árvore binária também têm nomes que variam entre autores: o NIST registra que alguns livros chamam de cheia a árvore que ele chama de perfeita. Na tabela, as três primeiras definições são as do NIST:

TipoRegra
Cheia (full)Todo nó tem zero ou dois filhos
CompletaTodos os níveis cheios, menos talvez o último, que é preenchido da esquerda para a direita
PerfeitaTodas as folhas na mesma profundidade e todo nó interno com dois filhos
DegeneradaCada nó, menos a folha do fim, tem um filho só, e a árvore vira, na prática, uma lista
De busca (BST)Menores à esquerda, maiores à direita, o que permite buscar sem percorrer tudo

A árvore de busca tem um problema: se os valores chegam já em ordem, ela fica degenerada e a busca volta a ser lenta. A árvore AVL resolve isso. Segundo o verbete AVL tree do NIST, ela é uma árvore binária de busca balanceada em que, em todo nó, a altura das duas subárvores difere em no máximo um; quando uma inserção ou remoção quebra essa regra, a árvore se reorganiza com rotações, e busca, inserção e remoção ficam em O(log n). O nome vem dos criadores, os matemáticos soviéticos Georgii Adelson-Velskii e Evgenii Landis, que publicaram a estrutura em 1962.

O heap é outra árvore binária completa, com uma regra diferente: cada pai é menor ou igual aos filhos, no heap de mínimo, ou maior ou igual, no heap de máximo. A raiz guarda sempre o menor (ou o maior) valor, o que faz do heap a estrutura da fila de prioridade e do algoritmo heapsort. Em Python, o módulo heapq da biblioteca padrão monta o heap sobre uma lista comum, e a aula deque, heapq e bisect no Python mostra quando ele vale a pena.

A trie, ou árvore de prefixos, guarda palavras letra por letra: palavras que começam igual dividem o mesmo caminho a partir da raiz. É a estrutura do autocompletar e do corretor ortográfico, porque chegar ao ponto da árvore onde ficam todas as palavras com um prefixo custa o tamanho do prefixo, e não o total de palavras guardadas. O mesmo raciocínio de nós e ponteiros vale para o grafo, que solta a regra da hierarquia, como mostra a aula o que é um grafo, e para a tabela hash por dentro, tema de outro módulo do curso.

Quer aprender com prática guiada? O Curso de Lógica de Programação Avançado cobre pilhas, filas, árvores, grafos e tabelas hash com um laboratório de algoritmos, diagramas em cada aula, exercícios e um projeto final. É gratuito e continua a partir do nível intermediário.

Grafos: representando conexões com BFS e DFS

O grafo é a estrutura mais abstrata e uma das mais poderosas: ele representa coisas (os nós) e as relações entre elas (as arestas). Rede social, mapa de cidades com estradas, dependências entre tarefas, tudo isso é grafo. Diferente da árvore, um grafo pode ter ciclos e vários caminhos entre dois pontos, o que exige algoritmos para percorrê-lo sem se perder. Os dois fundamentais são a busca em largura (BFS), que explora primeiro todos os vizinhos próximos antes de ir fundo, usando uma fila, ideal para achar o caminho com menos passos; e a busca em profundidade (DFS), que segue um caminho até o fim antes de voltar, usando uma pilha ou recursão, boa para explorar todas as possibilidades ou detectar ciclos. Repare como as estruturas lineares reaparecem: BFS usa fila, DFS usa pilha. É por isso que se estuda tudo na ordem certa, cada peça sustenta a seguinte.

Algoritmos que amarram tudo: ordenação, backtracking e memoização

Com as estruturas na mão, alguns algoritmos merecem estudo próprio porque ensinam padrões que se repetem. O merge sort e o quick sort ordenam dados dividindo o problema em partes menores, resolvendo cada uma e juntando o resultado, a estratégia de dividir para conquistar, com custo O(n log n). O backtracking resolve problemas testando caminhos e voltando atrás quando um deles não leva a lugar nenhum, como montar um labirinto de decisões ou preencher um sudoku: é a base de quebra-cabeças e de buscas com restrição. Já a memoização guarda resultados de cálculos já feitos para não repetir trabalho, o que transforma soluções recursivas lentas em rápidas, um primeiro passo em direção à programação dinâmica. Os três têm a recursão como fio condutor, e é aí que aquele conceito de função que chama a si mesma finalmente mostra a que veio.

Como estudar estruturas avançadas na ordem certa

A sequência que rende começa pelas estruturas lineares (pilha, fila, lista ligada), porque elas firmam a ideia de ponteiro e de ordem de acesso. Em seguida vem a tabela hash, que conecta com o dicionário que você já domina do nível intermediário. Depois entram as árvores (binária de busca e os percursos), primeiro grande exercício de recursão aplicada. Por último, os grafos com BFS e DFS, que reúnem fila, pilha e recursão num só lugar. Os algoritmos de ordenação, backtracking e memoização se estudam junto das estruturas em que aparecem, nunca soltos. Estudar assim, um pouco por dia, com um diagrama para visualizar e código para testar, fixa muito mais que uma maratona. É exatamente essa progressão que o curso avançado de lógica segue, com laboratório e um projeto que junta tudo no fim.

Erros comuns de quem chega no nível avançado

O primeiro é tentar decorar implementações em vez de entender a ideia: você esquece o código, mas o raciocínio de dividir para conquistar ou de percorrer em largura fica para sempre. O segundo é ignorar a eficiência e escolher a estrutura errada por costume, como varrer uma lista quando uma tabela hash resolveria na hora. O terceiro é escrever recursão sem caso base claro, o que gera laços infinitos e estouro de pilha. O quarto é estudar grafos antes de firmar fila e pilha, e travar por falta de base. Conhecer esses tropeços de antemão poupa horas de frustração, e cada um deles vira um hábito melhor com prática guiada e feedback.

Estruturas de dados avançadas e seus algoritmos são o passo que transforma quem resolve exercícios em quem projeta sistemas, e o conteúdo aparece em entrevistas técnicas e em qualquer linguagem. Para aprender com método, laboratório de algoritmos e diagramas, continue pelo Curso de Lógica de Programação Avançado e, quando quiser conhecer os outros temas, veja todos os cursos gratuitos do ValorFinal.

Calculadoras deste guia

As ferramentas de tecnologia mais procuradas no Google: teste de velocidade da internet, letras diferentes, horário de Brasília, cronômetro online, gerador de QR Code, roleta de sorteio, meu IP e gerador de CPF.

Leia também

Fontes das calculadoras relacionadas

Links externos para o que foi consultado na construção desta página, com a natureza de cada fonte identificada. O conteúdo delas pode mudar sem aviso; em caso de divergência, vale sempre a fonte primária.

Como citar esta página

Vai citar este guia em uma matéria, post ou trabalho? Copie a referência pronta. O conteúdo é baseado em MDN Web Docs - JSON.parse() e revisado pela equipe editorial.

ValorFinal. Estruturas de dados avançadas: pilha, fila, árvore, grafo e hash. Disponível em: https://valorfinal.com.br/guia/estruturas-de-dados-avancadas. Atualizado em: 06/11/2026.

ValorFinal VIP: Sem anúncios no portal inteiro, cenários salvos e alertas por e-mail.

Como validamos este conteúdo

Base deste guia: MDN Web Docs - JSON.parse / MDN Web Docs - JSON.stringify. Padrões, APIs, versões e recomendações técnicas evoluem. O conteúdo reflete a documentação de referência na data de atualização; confira sempre a documentação oficial da versão que você usa. Entenda nossa metodologia em como validamos os cálculos.

Perguntas frequentes

O que são estruturas de dados avançadas?
São formas de organizar dados que vão além da lista e do dicionário simples, pensadas para operações específicas serem rápidas. Pilha e fila controlam a ordem de entrada e saída; a lista ligada encadeia elementos por ponteiros; a árvore organiza dados em hierarquia; o grafo representa conexões entre coisas; e a tabela hash acha um valor quase na hora pela chave. Cada uma resolve um tipo de problema que as estruturas básicas resolvem mal ou de forma lenta.
Qual a diferença entre pilha e fila?
As duas guardam itens em ordem, mas atendem por regras opostas. A pilha é LIFO (last in, first out): o último que entra é o primeiro que sai, como uma pilha de pratos. A fila é FIFO (first in, first out): o primeiro que entra é o primeiro que sai, como a fila do banco. Use pilha para desfazer ações ou avaliar expressões; use fila para processar tarefas na ordem em que chegaram.
Quando usar uma árvore em vez de uma lista?
Use árvore quando os dados têm hierarquia natural (pastas dentro de pastas, categorias e subcategorias) ou quando você precisa buscar, inserir e remover mantendo tudo ordenado com eficiência. Numa árvore binária de busca equilibrada, achar um item custa cerca de log n passos, muito menos que percorrer uma lista inteira. A lista continua melhor quando a ordem de inserção é o que importa e você percorre tudo de ponta a ponta.
O que é uma tabela hash e por que ela é tão rápida?
A tabela hash é a estrutura por trás do dicionário. Ela usa uma função de hash para transformar a chave (um nome, um CPF) em uma posição na memória, então guarda e recupera o valor direto naquele endereço, sem procurar item por item. Por isso a busca custa em média O(1), tempo constante. O preço é lidar com colisões (quando duas chaves caem na mesma posição), resolvidas com listas ou reendereçamento por baixo dos panos.
Como se calcula a altura de uma árvore binária?
A altura de uma árvore binária é a maior distância, contada em arestas, entre a raiz e um nó, e a árvore com um nó só tem altura zero, como define o dicionário de algoritmos do NIST. O cálculo é recursivo: a altura de um nó é 1 mais a maior altura entre a subárvore da esquerda e a da direita, e o nó vazio vale -1 nessa conta. Alguns livros contam nós em vez de arestas e chegam a um número uma unidade maior, então siga a convenção do enunciado.
Quais são os tipos de árvore binária?
Os tipos de árvore binária mais cobrados são a cheia, em que todo nó tem zero ou dois filhos; a completa, com todos os níveis cheios menos talvez o último, preenchido da esquerda para a direita; a perfeita, com todas as folhas na mesma profundidade; a degenerada, em que cada nó tem um filho só e a árvore vira uma lista; e a de busca, com os menores à esquerda e os maiores à direita. Os nomes variam entre autores: há livros que chamam de cheia a árvore perfeita.
O que é uma árvore AVL e quem a criou?
A árvore AVL é uma árvore binária de busca que se mantém balanceada: em todo nó, a altura das duas subárvores difere em no máximo um, e uma inserção ou remoção que quebra a regra dispara rotações que reorganizam os nós. Assim, busca, inserção e remoção ficam em O(log n), mesmo quando os valores chegam em ordem. O nome vem dos criadores, Georgii Adelson-Velskii e Evgenii Landis, que publicaram a estrutura em 1962, como registra o dicionário de algoritmos do NIST.
Para que serve um heap?
O heap serve para achar rápido o menor ou o maior valor de uma coleção que muda o tempo todo. Ele é uma árvore binária completa em que cada pai é menor ou igual aos filhos, no heap de mínimo, ou maior ou igual, no de máximo, então a raiz guarda sempre o extremo. É a estrutura da fila de prioridade, usada para atender primeiro a tarefa mais urgente, e do algoritmo heapsort. Em Python, o módulo heapq da biblioteca padrão monta o heap sobre uma lista comum.
O que é recursão e onde ela aparece nos algoritmos?
Recursão é uma função que resolve um problema chamando a si mesma em versões menores dele, até chegar num caso simples que ela sabe responder direto. Ela aparece em quase tudo que é avançado: percorrer árvores, o merge sort e o quick sort, o backtracking e a memoização. O segredo é sempre ter um caso base (a condição de parada) e garantir que cada chamada se aproxima dele, senão a função nunca termina.
Preciso decorar os algoritmos de ordenação?
Decorar não; entender sim. No dia a dia você usa a ordenação pronta da linguagem, que já é rápida. Mas estudar merge sort e quick sort ensina o raciocínio de dividir para conquistar, que se repete em muitos problemas, e ensina a ler a eficiência (O(n log n) é o piso da ordenação por comparação). É a diferença entre saber apertar um botão e entender o que ele faz, e isso aparece em entrevistas e em decisões de projeto.
Em que ordem devo estudar estruturas de dados avançadas?
Comece pelas lineares (pilha, fila, lista ligada), porque elas firmam a ideia de ponteiro e ordem de acesso. Depois vá para a tabela hash, que conecta com o dicionário que você já usa. Em seguida entram as árvores (binária de busca, e a noção de percurso) e, por último, os grafos com BFS e DFS, que são os mais abstratos. Os algoritmos de recursão, ordenação e backtracking se estudam junto das estruturas em que aparecem, não isolados.