Por que estruturas de dados importam em prova e no dia a dia
Estruturas de dados organizam informações para que operações como inserir, buscar, remover e ordenar sejam feitas com eficiência. Em concursos, é comum aparecerem questões que pedem a estrutura “mais adequada” para um cenário (ex.: fila de processamento, pilha de chamadas, controle de duplicidade) e comparações de custo (tempo e memória). Na prática, escolher bem evita lentidão, consumo excessivo de memória e código desnecessariamente complexo.
Vetor (array): acesso rápido por índice
Conceito
Vetor é uma coleção de elementos armazenados de forma contígua, acessados por índice (posição). É ótimo quando você precisa acessar rapidamente o elemento na posição i.
Operações típicas e custo conceitual
- Acessar por índice: muito rápido (tempo constante).
- Buscar valor: pode exigir percorrer (tempo proporcional ao tamanho).
- Inserir/remover no meio: exige deslocar elementos (custo proporcional ao tamanho).
Exemplo em pseudocódigo
// vetor de 5 posições (0..4) com inteiros
V = [10, 20, 30, 40, 50]
// acesso por índice
x = V[2] // x = 30
// busca linear (retorna índice ou -1)
func buscaLinear(V, alvo):
para i de 0 até tamanho(V)-1:
se V[i] == alvo:
retorna i
retorna -1Lista: flexibilidade para inserções/remoções
Conceito
Lista é uma coleção em que inserções e remoções podem ser mais naturais do que em vetores. Em muitas linguagens, “lista” pode ser implementada como vetor dinâmico (array que cresce) ou como lista encadeada (nós ligados por ponteiros). Em prova, o foco costuma ser a ideia: lista facilita inserções/remoções, mas pode perder em acesso direto por índice.
Quando usar
- Quando o tamanho varia bastante e você faz muitas inserções/remoções.
- Quando não precisa de acesso aleatório extremamente rápido por índice.
Pseudocódigo (lista encadeada conceitual)
tipo No:
valor
prox
// inserir no início
func inserirInicio(cabeca, valor):
novo = No(valor)
novo.prox = cabeca
retorna novoPilha (stack): LIFO (último a entrar, primeiro a sair)
Conceito
Pilha segue a regra LIFO: o último elemento inserido é o primeiro removido. É a estrutura natural para desfazer ações, avaliar expressões e modelar chamadas de função (pilha de chamadas).
Operações
- push: empilha (insere no topo)
- pop: desempilha (remove do topo)
- top/peek: consulta o topo sem remover
Passo a passo prático: pilha de chamadas (conceitual)
Imagine funções A chama B, e B chama C:
Continue em nosso aplicativo
Você poderá ouvir o audiobook com a tela desligada, ganhar gratuitamente o certificado deste curso e ainda ter acesso a outros 5.000 cursos online gratuitos.
ou continue lendo abaixo...
Baixar o aplicativo
- Entra em A: empilha “A”.
- A chama B: empilha “B”.
- B chama C: empilha “C”.
- C termina: desempilha “C”.
- B termina: desempilha “B”.
- A termina: desempilha “A”.
Pseudocódigo
pilha = []
func push(pilha, x):
adicionar x ao final de pilha
func pop(pilha):
se pilha vazia: erro
x = ultimo elemento
remover ultimo elemento
retorna xFila (queue): FIFO (primeiro a entrar, primeiro a sair)
Conceito
Fila segue FIFO: o primeiro elemento inserido é o primeiro removido. É ideal para filas de processamento, agendamento e atendimento por ordem de chegada.
Operações
- enqueue: enfileirar (insere no fim)
- dequeue: desenfileirar (remove do início)
- front: consulta o primeiro
Passo a passo prático: fila de processamento
- Chega tarefa T1: entra no fim da fila.
- Chega tarefa T2: entra atrás de T1.
- Processador pega a próxima: remove T1 (primeira).
- Depois remove T2, e assim por diante.
Pseudocódigo (fila com índices)
tipo Fila:
dados
ini
fim
func criarFila():
F.dados = []
F.ini = 0
F.fim = 0
retorna F
func enqueue(F, x):
F.dados[F.fim] = x
F.fim = F.fim + 1
func dequeue(F):
se F.ini == F.fim: erro (vazia)
x = F.dados[F.ini]
F.ini = F.ini + 1
retorna xConjunto (set): unicidade e operações de pertencimento
Conceito
Conjunto armazena elementos sem duplicidade. A operação mais importante é verificar se um elemento pertence ao conjunto. Em implementações comuns (tabelas hash), inserir e verificar pertencimento tendem a ser muito rápidos em média.
Controle de duplicidade (passo a passo)
Cenário: você recebe uma lista de CPFs/IDs e precisa eliminar repetidos ou bloquear cadastros duplicados.
- Crie um conjunto “vistos”.
- Para cada ID recebido: se já está em “vistos”, é duplicado; caso contrário, insira em “vistos”.
Pseudocódigo
vistos = conjuntoVazio()
func processarIDs(listaIDs):
para cada id em listaIDs:
se contem(vistos, id):
imprimir("duplicado", id)
senao:
inserir(vistos, id)Dicionário/Mapa (map): chave → valor
Conceito
Mapa armazena pares (chave, valor). É a estrutura típica para associar um identificador a informações: por exemplo, idCliente → saldo, codigoErro → mensagem, usuario → permissões.
Quando usar
- Quando você precisa recuperar um valor rapidamente a partir de uma chave.
- Quando faz contagens e agregações (frequência de itens).
Exemplo prático: contagem de ocorrências
// contar quantas vezes cada status aparece
contagem = mapaVazio()
para cada status em listaStatus:
se existeChave(contagem, status):
contagem[status] = contagem[status] + 1
senao:
contagem[status] = 1Busca: linear e binária (nível conceitual)
Busca linear
Você percorre elemento por elemento até achar o alvo ou terminar. Funciona em qualquer coleção, mesmo desordenada.
func buscaLinear(V, alvo):
para i de 0 até tamanho(V)-1:
se V[i] == alvo: retorna i
retorna -1Busca binária
Exige coleção ordenada. Você compara com o elemento do meio e descarta metade do espaço de busca a cada passo.
Passo a passo prático (ideia)
- Comece com intervalo [início, fim].
- Calcule meio.
- Se o alvo é menor que o meio, procure na metade esquerda; se maior, na direita.
- Repita até encontrar ou o intervalo ficar vazio.
func buscaBinaria(V_ordenado, alvo):
ini = 0
fim = tamanho(V_ordenado) - 1
enquanto ini <= fim:
meio = (ini + fim) // 2
se V_ordenado[meio] == alvo: retorna meio
se alvo < V_ordenado[meio]:
fim = meio - 1
senao:
ini = meio + 1
retorna -1Ordenação: noções básicas para prova
Ideia geral
Ordenar é reorganizar elementos segundo um critério (crescente, decrescente, por chave). Em questões, costuma-se cobrar: por que ordenar ajuda na busca (habilita busca binária) e o custo relativo de métodos simples.
Ordenação por seleção (conceitual e simples)
Em cada posição i, encontre o menor elemento do trecho restante e troque para a posição i.
func selectionSort(V):
n = tamanho(V)
para i de 0 até n-2:
min = i
para j de i+1 até n-1:
se V[j] < V[min]:
min = j
trocar V[i] com V[min]Ordenação por inserção (conceitual)
Constrói uma parte ordenada e insere cada novo elemento na posição correta (bom para listas quase ordenadas).
func insertionSort(V):
para i de 1 até tamanho(V)-1:
chave = V[i]
j = i - 1
enquanto j >= 0 e V[j] > chave:
V[j+1] = V[j]
j = j - 1
V[j+1] = chaveComplexidade: comparando soluções (tempo e espaço)
Conceito
Complexidade de tempo estima como o número de operações cresce com o tamanho da entrada n. Complexidade de espaço estima a memória adicional usada. Em prova, o foco é comparar ordens de grandeza (Big-O), não contagens exatas.
Ordens comuns (intuição)
- O(1): não cresce com n (ex.: acessar V[i]).
- O(log n): cresce devagar (ex.: busca binária).
- O(n): cresce proporcionalmente (ex.: busca linear).
- O(n log n): típico de ordenações eficientes (conceito geral).
- O(n²): cresce rápido (ex.: selection/insertion no pior caso).
Tabela de comparação (operações típicas)
| Estrutura | Acesso por índice | Inserir/Remover (extremidade) | Inserir/Remover (meio) | Buscar (sem ordem) | Pertencimento (set/map) | Observação |
|---------------------|-------------------|--------------------------------|-------------------------|--------------------|--------------------------|------------|
| Vetor (array) | O(1) | fim: ~O(1)* | O(n) | O(n) | n/a | *amortizado se dinâmico |
| Lista (encadeada) | O(n) | início: O(1) | O(1) se tem referência | O(n) | n/a | sem acesso direto |
| Pilha (stack) | n/a | push/pop: O(1) | n/a | O(n) | n/a | LIFO |
| Fila (queue) | n/a | enqueue/dequeue: O(1) | n/a | O(n) | n/a | FIFO |
| Conjunto (hash set) | n/a | inserir/remover: ~O(1) | n/a | n/a | ~O(1) | sem duplicidade |
| Mapa (hash map) | n/a | inserir/remover: ~O(1) | n/a | n/a | ~O(1) por chave | chave→valor |Observação: ~O(1) indica custo médio esperado em estruturas baseadas em hash; no pior caso pode degradar, mas em questões costuma-se considerar o caso médio.
Tabela de comparação (busca e ordenação)
| Técnica | Pré-requisito | Tempo (ordem) | Ideia-chave |
|---------------------|--------------------------|---------------|------------|
| Busca linear | nenhum | O(n) | varre tudo |
| Busca binária | coleção ordenada | O(log n) | divide ao meio |
| Selection sort | nenhum | O(n^2) | seleciona o menor a cada passo |
| Insertion sort | nenhum | pior: O(n^2) | insere na parte ordenada |Escolhendo a estrutura adequada: cenários típicos de concurso
1) Fila de processamento (FIFO)
Problema: tarefas chegam e devem ser processadas na ordem de chegada (ex.: eventos, requisições, impressão).
- Estrutura indicada: fila.
- Por quê: remove sempre o mais antigo (dequeue) e adiciona no fim (enqueue).
2) Pilha de chamadas / desfazer ações (LIFO)
Problema: a última operação deve ser revertida primeiro (undo) ou a última função chamada deve retornar primeiro.
- Estrutura indicada: pilha.
- Por quê: o topo representa o contexto mais recente.
3) Controle de duplicidade
Problema: impedir repetição de IDs/CPFs/itens em uma lista de entradas.
- Estrutura indicada: conjunto.
- Por quê: garante unicidade e teste de pertencimento rápido.
4) Consulta rápida por identificador
Problema: dado um código, recuperar dados associados (ex.: idCliente → dados).
- Estrutura indicada: mapa/dicionário.
- Por quê: acesso por chave é direto e eficiente.
5) Preciso de acesso por posição e iteração simples
Problema: armazenar valores e acessar frequentemente por índice (ex.: posição i).
- Estrutura indicada: vetor.
Exercícios (escolha a estrutura adequada)
Questões objetivas
1) Um sistema recebe solicitações e deve processá-las exatamente na ordem em que chegaram. Qual estrutura é mais adequada?
- A) Pilha
- B) Fila
- C) Conjunto
- D) Mapa
2) Você precisa implementar “desfazer” em um editor: a última ação realizada deve ser a primeira a ser revertida. Qual estrutura é mais adequada?
- A) Fila
- B) Vetor
- C) Pilha
- D) Conjunto
3) Dada uma lista de identificadores, você precisa detectar rapidamente se um identificador já apareceu antes (sem armazenar duplicados). Qual estrutura é mais adequada?
- A) Conjunto
- B) Fila
- C) Pilha
- D) Vetor
4) Você precisa associar cada matrícula de funcionário ao seu perfil (objeto com dados). Qual estrutura é mais adequada?
- A) Pilha
- B) Mapa/Dicionário
- C) Fila
- D) Lista apenas
5) Em uma coleção ordenada, qual técnica de busca reduz o espaço de procura pela metade a cada passo?
- A) Busca linear
- B) Busca binária
- C) Busca por seleção
- D) Busca por inserção
Exercícios práticos (pseudocódigo)
6) Escreva um pseudocódigo que leia uma lista de números e imprima apenas os que não se repetem (primeira ocorrência), usando um conjunto.
7) Escreva um pseudocódigo que simule uma fila de atendimento: enfileire nomes e desenfileire um por vez, imprimindo quem será atendido.
8) Dado um vetor ordenado de inteiros, escreva um pseudocódigo de busca binária e indique o que acontece quando o elemento não existe.
