Seu navegador não oferece leitura em voz alta. Você pode ler o guia normalmente.
Estruturas de dados organizam informação para que certas operações sejam simples e rápidas. Pilha, fila e lista encadeada são as três mais cobradas em provas de TI, geralmente com uma sequência de operações que o candidato precisa simular. Os resultados abaixo foram obtidos executando o código em um teste.
Pilha (stack): último a entrar, primeiro a sair
Na pilha, inserção e remoção acontecem no mesmo extremo, o topo. A regra é LIFO (last in, first out). As operações clássicas são push (empilhar), pop (desempilhar) e topo (consultar sem remover). Pense numa pilha de processos físicos sobre a mesa: o último que você colocou é o primeiro que sai.
Simulação com a sequência push 10, push 20, push 30, pop, pop:
| Operação | Estado da pilha (base à esquerda, topo à direita) | Retorno |
|---|---|---|
| push 10 | 10 | |
| push 20 | 10, 20 | |
| push 30 | 10, 20, 30 | |
| pop | 10, 20 | 30 |
| pop | 10 | 20 |
Ao final, o topo é 10. Tentar pop numa pilha vazia gera a condição de underflow; tentar push numa pilha com capacidade fixa cheia gera overflow.
Para que serve a pilha
- Chamadas de função: o programa guarda onde voltar numa pilha de chamadas; recursão infinita causa estouro dessa pilha.
- Desfazer (Ctrl+Z) e o histórico de navegação “voltar”.
- Conferir parênteses: abre-se com push, fecha-se com pop.
- Avaliar expressões em notação pós-fixa.
Teste de parênteses balanceados, empilhando as aberturas e comparando com cada fechamento:
| Expressão | Balanceada? |
|---|---|
(a+b)*[c-d] |
sim |
(a+b] |
não: o ] não casa com o ( do topo |
((a) |
não: sobra uma abertura na pilha no fim |
{[()]} |
sim |
Notação pós-fixa
Na pós-fixa, o operador vem depois dos operandos, e dispensa parênteses. O algoritmo: leia da esquerda para a direita; número vai para a pilha; operador desempilha dois valores (o primeiro desempilhado é o segundo operando), calcula e empilha o resultado.
Expressão 3 4 + 2 *:
| Símbolo | Pilha após |
|---|---|
| 3 | 3 |
| 4 | 3, 4 |
| + | 7 |
| 2 | 7, 2 |
| * | 14 |
Resultado 14, equivalente a (3 + 4) x 2. Outro teste: 5 1 2 + 4 * + 3 - resulta em 14, equivalente a 5 + ((1 + 2) x 4) - 3.
Fila (queue): primeiro a entrar, primeiro a sair
A fila insere num extremo (fim) e remove no outro (início). A regra é FIFO (first in, first out). Operações: enqueue (enfileirar) e dequeue (desenfileirar).
Sequência enqueue 10, 20, 30, dequeue, dequeue:
| Operação | Fila (início à esquerda) | Retorno |
|---|---|---|
| enqueue 10 | 10 | |
| enqueue 20 | 10, 20 | |
| enqueue 30 | 10, 20, 30 | |
| dequeue | 20, 30 | 10 |
| dequeue | 30 | 20 |
Usos: fila de impressão, atendimento por ordem de chegada, filas de tarefas de um sistema operacional. Variações: a fila circular reaproveita o espaço do vetor, a fila de prioridade retira primeiro o elemento de maior prioridade, e o deque permite inserir e remover em ambos os extremos.
Comparação direta com a mesma entrada 10, 20, 30: a pilha devolve 30, 20, 10 (ordem inversa); a fila devolve 10, 20, 30 (ordem de entrada). Essa inversão é o que a banca costuma testar.
Lista encadeada
Na lista encadeada, cada nó guarda o dado e uma referência (ponteiro) para o próximo nó. Diferente do vetor, os nós podem estar em posições distantes da memória.
| Operação | Vetor | Lista encadeada |
|---|---|---|
| Acessar o elemento da posição k | direto, O(1) | percorre k nós, O(n) |
| Inserir no início | desloca todos, O(n) | ajusta ponteiros, O(1) |
| Inserir no meio, já tendo o nó anterior | desloca, O(n) | ajusta ponteiros, O(1) |
| Memória | blocos contíguos | cada nó carrega ponteiro extra |
Teste: inserindo 3, depois 2, depois 1 sempre no início de uma lista, a lista final percorrida do início ao fim é 1, 2, 3. Inserir no início inverte a ordem de chegada.
Variações: lista duplamente encadeada (cada nó aponta para o anterior e o próximo), circular (o último aponta para o primeiro) e a lista com cabeça. Pilhas e filas podem ser implementadas sobre vetor ou sobre lista encadeada.
Resumo para prova
| Estrutura | Regra | Operações | Exemplo de uso |
|---|---|---|---|
| Pilha | LIFO | push, pop, topo | desfazer, chamadas de função |
| Fila | FIFO | enqueue, dequeue | impressão, atendimento |
| Lista encadeada | acesso sequencial | inserir, remover, percorrer | sequências que mudam muito |
Erros comuns
- Trocar LIFO por FIFO (ou pilha por fila) ao ler o enunciado.
- Dizer que o
popconsulta o topo sem remover; quem só consulta é otopo(oupeek). - Esquecer o operando invertido ao avaliar pós-fixa com subtração ou divisão: em
5 3 -, o resultado é 5 menos 3. - Achar que lista encadeada tem acesso direto por posição.
- Confundir overflow (estrutura cheia) com underflow (estrutura vazia).
Fontes e atualização
Não há norma oficial brasileira sobre estruturas de dados; o conteúdo segue a literatura clássica da área. Os estados e resultados foram obtidos executando o código em um teste. Nomes de operações variam entre livros e linguagens: confira o edital e o enunciado.
Próximos passos
- Veja a escolha de estruturas na busca em busca sequencial e binária e Big O.
- Continue com árvore binária de busca e percursos.
- Aplique a ideia de fila em escalonamento de processos: FCFS, SJF e Round Robin.