Lista Encadeada Simples

// A variável cabeça guarda o início da lista, elem[] armazena os valores, prox[] o ponteiro para o próximo, idx controla o nó atual.

int cabeca, elem[N], prox[N], idx;

// Inicialização
void inicializar() {
    cabeca = -1;
    idx = 0;
}

// Inserir um valor no início da lista
void inserir_inicio(int valor) {
    elem[idx] = valor;
    prox[idx] = cabeca;
    cabeca = idx++;
}

// Remove o nó cabeça (a lista não pode estar vazia)
void remover_inicio() {
    cabeca = prox[cabeca];
}

Lista Encadeada Dupla

// elem[] guarda valores, ant[] o ponteiro anterior, suc[] o ponteiro sucessor, idx endica o nó disponível.

int elem[N], ant[N], suc[N], idx;

// Inicialização: 0 é o nó sentinela esquerdo, 1 o direito.
void inicializar() {
    suc[0] = 1;
    ant[1] = 0;
    idx = 2;
}

// Insere o valor x após o nó a
void inserir_apos(int a, int valor) {
    elem[idx] = valor;
    ant[idx] = a;
    suc[idx] = suc[a];
    ant[suc[a]] = idx;
    suc[a] = idx++;
}

// Remove o nó a
void remover(int a) {
    ant[suc[a]] = ant[a];
    suc[ant[a]] = suc[a];
}

Pilha (Stack)

// O topo da pilha é representado pelo índice topo.

int pilha[N], topo = 0;

// Empilhar um valor
pilha[++topo] = valor;

// Desempilhar
topo--;

// Valor no topo
int valor_topo = pilha[topo];

// Verifica se a pilha está vazia
bool pilha_vazia() { return topo == 0; }

Fila (Queue)

// Uma fila comum usa dois ponteiros: frente e tras.

int fila[N], frente = 0, tras = -1;

// Enfileirar (adicionar no final)
fila[++tras] = valor;

// Desenfileirar (remover da frente)
frente++;

// Elemento na frente
int primeiro = fila[frente];

// Verifica se a fila está vazia
bool fila_vazia() { return frente > tras; }

Fila Circular

// Para reutilizar o espaço, a fila opera em um buffer circular.

int fila[N], frente = 0, tras = 0;

// Enfileirar
fila[tras++] = valor;
if (tras == N) tras = 0;

// Desenfileirar
frente++;
if (frente == N) frente = 0;

// Elemento na frente
int primeiro = fila[frente];

// Verifica se a fila está vazia
bool fila_vazia() { return frente == tras; }

Pilha Monótona

Exemplo típico: encontrar, para cada elemento, o próximo menor (ou maior) à sua esquerda.

int topo = 0;
for (int i = 0; i < n; i++) {
    while (topo > 0 && condicao(pilha[topo], i)) {
        topo--;
    }
    pilha[++topo] = i;
}

Fila Monótona

Usada para calcular o máximo/mínimo em uma janela deslizante.

int frente = 0, tras = -1;
for (int i = 0; i < n; i++) {
    // Remove elementos que saíram da janela
    while (frente <= tras && fila[frente] < i - k + 1) frente++;
    // Mantém a monotonicidade na fila
    while (frente <= tras && condicao(fila[tras], i)) tras--;
    fila[++tras] = i;
}

Algoritmo KMP

Construção da array de falha (próximo):

int falha[N]; // falha[i] comprimento do maior prefixo-sufixo de p[0..i-1]
void construir_falha(const string &padrao) {
    int len = 0; falha[0] = 0;
    int i = 1;
    while (i < padrao.length()) {
        if (padrao[i] == padrao[len]) {
            len++;
            falha[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = falha[len - 1];
            } else {
                falha[i] = 0;
                i++;
            }
        }
    }
}

Busca KMP:

void buscar(const string &texto, const string &padrao) {
    int i = 0, j = 0;
    while (i < texto.length()) {
        if (texto[i] == padrao[j]) {
            i++; j++;
        }
        if (j == padrao.length()) {
            // Ocorrência encontrada em i - j
            j = falha[j - 1];
        } else if (i < texto.length() && texto[i] != padrao[j]) {
            if (j != 0) j = falha[j - 1];
            else i++;
        }
    }
}

Árvore Trie

Uma estrutura para armazenar e recuperar strings de forma eficiente.

int filho[N][26], contagem[N], idx = 0;

// Inserir uma string na Trie
void inserir(const string &s) {
    int no = 0;
    for (char c : s) {
        int indice = c - 'a';
        if (!filho[no][indice]) filho[no][indice] = ++idx;
        no = filho[no][indice];
    }
    contagem[no]++;
}

// Consultar a frequência de uma string
int consultar(const string &s) {
    int no = 0;
    for (char c : s) {
        int indice = c - 'a';
        if (!filho[no][indice]) return 0;
        no = filho[no][indice];
    }
    return contagem[no];
}

Heap (Fila de Prioridade)

Heap mínimo implementado com array. Os filhos de i estão em 2*i e 2*i+1.

int heap[N], tamanho = 0;

void sift_down(int i) {
    int menor = i;
    int esq = 2 * i, dir = 2 * i + 1;
    if (esq <= tamanho && heap[esq] < heap[menor]) menor = esq;
    if (dir <= tamanho && heap[dir] < heap[menor]) menor = dir;
    if (menor != i) {
        swap(heap[i], heap[menor]);
        sift_down(menor);
    }
}

void sift_up(int i) {
    while (i > 1 && heap[i] < heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

// Construir heap em O(n)
for (int i = tamanho / 2; i >= 1; i--) sift_down(i);

Tabela Hash - Método de Encadeamento

int tabela[N], proximo[N], valores[N], idx = 0;

// Inserir valor x
void inserir_hash(int x) {
    int indice = ((x % N) + N) % N;
    valores[idx] = x;
    proximo[idx] = tabela[indice];
    tabela[indice] = idx++;
}

// Verificar se x existe
bool existe(int x) {
    int indice = ((x % N) + N) % N;
    for (int i = tabela[indice]; i != -1; i = proximo[i]) {
        if (valores[i] == x) return true;
    }
    return false;
}

Tabela Hash - Endereçamento Aberto

int tabela[N];

// Encontra a posição de x, ou onde inseri-lo
int encontrar(int x) {
    int idx = ((x % N) + N) % N;
    while (tabela[idx] != NULO && tabela[idx] != x) {
        idx = (idx + 1) % N;
    }
    return idx;
}

Hashing de String

Técnica que permite comparar substrings em tempo O(1). Trata a string como um número em base P.

typedef unsigned long long ULL;
const ULL P = 131;
ULL prefixo[N], potencia[N];

// Pré-cálculo
potencia[0] = 1;
for (int i = 1; i <= n; i++) {
    prefixo[i] = prefixo[i-1] * P + s[i-1];
    potencia[i] = potencia[i-1] * P;
}

// Hash do intervalo [l, r] (0-indexado)
ULL hash_intervalo(int l, int r) {
    return prefixo[r+1] - prefixo[l] * potencia[r - l + 1];
}