Revisão: Estruturas de Dados Lineares Essenciais

1. O Arsenal do Maratonista: Java Collections

Para AED II e competições, você não vai re-implementar uma Lista Encadeada do zero a cada problema. Você usará o Java Collections Framework. Saber qual ferramenta usar pode reduzir seu tempo de execução de \(O(N)\) para \(O(1)\) ou \(O(\log N)\).

classDiagram
    direction BT
    class Collection { <<interface>> }
    class List { <<interface>> }
    class Queue { <<interface>> }
    class Deque { <<interface>> }
    class Set { <<interface>> }
    class Map { <<interface>> }
    
    List --|> Collection
    Queue --|> Collection
    Set --|> Collection
    Deque --|> Queue
    
    class ArrayList
    class LinkedList
    class ArrayDeque
    class PriorityQueue
    class HashSet
    class HashMap
    class TreeMap
    
    ArrayList ..|> List
    LinkedList ..|> List
    LinkedList ..|> Deque
    ArrayDeque ..|> Deque
    PriorityQueue ..|> Queue
    HashSet ..|> Set
    HashMap ..|> Map
    TreeMap ..|> Map

2. Listas: A Batalha Contínua vs Encadeada

O Vetor Dinâmico: ArrayList (Seu melhor amigo)

É um wrapper sobre um array padrão tipo[]. Quando enche, ele cria um novo array com o dobro do tamanho e copia tudo (\(O(N)\)), mas isso acontece tão raramente que a complexidade amortizada é \(O(1)\). - Vantagem: Acesso aleatório (get(i)) em \(O(1)\). - Desvantagem: Remover ou inserir no meio é \(O(N)\) (tem que empurrar todo mundo). - Segredo: Muito amigável ao Cache da CPU (dados contíguos na RAM).

A Lista Encadeada: LinkedList (O incompreendido)

Cada elemento é um objeto Node espalhado na memória, ligado por ponteiros. - Vantagem: Inserir/Remover no início ou fim é \(O(1)\). - Desvantagem: Acesso aleatório (get(i)) é \(O(N)\) – péssimo! - Segredo: Só use se você precisa remover muito no meio da lista usando um Iterator. Se for para usar índice, esqueça.

Operação ArrayList LinkedList
get(i) \(O(1)\) \(O(N)\)
add(e) (final) \(O(1)\) \(O(1)\)
add(0, e) (início) \(O(N)\) \(O(1)\)
remove(i) \(O(N)\) \(O(N)\) (mas \(O(1)\) com Iterator)

3. Pilhas e Filas: As Ferramentas de Trabalho

Fila (Queue) - FIFO (First-In First-Out)

Imagine uma fila de banco. Quem chega primeiro, é atendido primeiro. Aplicação Crítica: BFS (Busca em Largura) em Grafos. Implementação: Use LinkedList ou ArrayDeque.

Queue<String> fila = new LinkedList<>();
fila.add("Cliente A"); // Enfileira
fila.add("Cliente B");
String prox = fila.poll(); // Desenfileira ("Cliente A")

Pilha (Stack) - LIFO (Last-In First-Out)

Imagine uma pilha de pratos. Você só tira o do topo. Aplicação Crítica: DFS (Busca em Profundidade), recursão, validar parênteses, desfazer (Ctrl+Z). Implementação: EVITE a classe Stack (ela é antiga e sincronizada/lenta). Use ArrayDeque.

Deque<Integer> pilha = new ArrayDeque<>();
pilha.push(10); // Empilha
pilha.push(20);
int topo = pilha.pop(); // Desempilha (20)

Por que ArrayDeque? É mais rápida que Stack e consome menos memória que LinkedList. É híbrida (pode ser Pilha ou Fila).

4. Mapas e Conjuntos (Visão Rápida)

Embora não sejam “lineares”, vamos usá-los tanto que vale citar. - HashSet / HashMap: Usam Tabela Hash. Inserção e Busca em \(O(1)\) médio. A ordem é aleatória. - TreeSet / TreeMap: Usam Árvore Rubro-Negra. Inserção e Busca em \(O(\log N)\). Mantêm os dados ordenados.

5. Dicas de Ouro para Java

Wrapper Classes e Autoboxing

Java não permite ArrayList<int>. Temos que usar ArrayList<Integer>. Isso tem um custo de memória absurdo. - int: 4 bytes. - Integer: ~24 bytes (Cabeçalho de objeto + referência + valor). Dica: Se o limite de memória for apertado (ex: 256MB) e \(N=10^7\), use arrays primitivos int[] em vez de ArrayList.

Fast I/O (Leitura Rápida)

O Scanner é lento porque faz muito parsing. Para problemas com \(N > 10^5\), use BufferedReader.

Template para Maratonas:

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        StringTokenizer st = new StringTokenizer("");
        
        // Exemplo: Ler N
        String linha = br.readLine();
        if (linha == null) return;
        int N = Integer.parseInt(linha);
        
        // Ler N inteiros na mesma linha
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            int x = Integer.parseInt(st.nextToken());
            out.println(x * 2); // Bufferiza a saída
        }
        
        out.flush(); // Importante! Despeja o buffer no final.
    }
}

6. Problemas Clássicos para Treinar

  1. Pilhas: Beecrowd 1068 - Balanço de Parênteses (Verificar se expressão matemática fecha corretamente).
  2. Filas: Beecrowd 1110 - Jogando Cartas Fora (Simular descarte de cartas).
  3. Mapas: Beecrowd 1281 - Ida à Feira (Somar preços de produtos usando nomes como chave).
Back to top