Antes de avançarmos para as estruturas de dados propriamente ditas (pilhas, filas, listas, árvores), vale a pena entender um pouco melhor como um programa se organiza na memória. Esses conceitos explicam por que algumas estruturas de dados são mais rápidas ou mais lentas que outras, o que será importante quando começarmos a falar de complexidade.

Memória: stack × heap

Em C, variáveis comuns (locais, vetores de tamanho fixo) ficam na pilha (stack), e memória alocada com malloc() fica no heap. As duas regiões diferem no gerenciamento e no tempo de vida dos dados:

Essa diferença de tempo de vida é o motivo pelo qual estruturas de dados dinâmicas (listas, pilhas, filas, árvores) precisam viver no heap: uma variável da pilha deixa de existir assim que a função retorna, mas uma estrutura de dados normalmente precisa continuar existindo depois disso.

A pilha de chamadas de função

Cada vez que uma função é chamada, um novo bloco (chamado quadro de ativação, ou stack frame) é empilhado, contendo os parâmetros e variáveis locais daquela chamada. Quando a função retorna, esse bloco é desempilhado e suas variáveis deixam de existir. Já vimos isso na prática na função recursiva contarAprovados do laboratório de revisão de linguagem C (Material Extra): cada chamada recursiva empilha um novo quadro com o seu próprio n, até chegar ao caso base:

contarAprovados(turma, 3)      // empilha quadro com n=3
  contarAprovados(turma, 2)    // empilha quadro com n=2
    contarAprovados(turma, 1)  // empilha quadro com n=1
      contarAprovados(turma, 0) // caso base, retorna e desempilha

Uma recursão sem caso base (ou com profundidade excessiva) empilha quadros indefinidamente e esgota o espaço da pilha, causando um erro conhecido como stack overflow.

Variáveis globais

Nem toda variável vive na pilha ou no heap: variáveis globais (declaradas fora de qualquer função) ficam em uma região separada da memória, e existem durante toda a execução do programa — não são criadas nem destruídas a cada chamada de função:

int totalAlunosCadastrados = 0; // global: existe do início ao fim do programa

void lerAluno(Aluno *aluno) {
    // ...
    totalAlunosCadastrados++; // acessível de qualquer função
}

Valor × ponteiro

Quando copiamos uma struct por valor (ex: void imprimirAluno(Aluno aluno)), copiamos todos os seus bytes. Quando copiamos um ponteiro (Aluno *aluno), copiamos apenas o endereço — poucos bytes, independente do tamanho da struct apontada.

Essa diferença de custo é um dos motivos pelos quais estruturas de dados costumam ser manipuladas por ponteiro: uma lista encadeada, por exemplo, nada mais é do que structs contendo um dado e um ponteiro para o próximo nó.

Vimos exatamente essa diferença no laboratório de revisão de linguagem C (Material Extra): imprimirAluno(Aluno aluno) recebe uma cópia inteira da struct (nome, matrícula e média), enquanto atualizarMedia(Aluno *aluno, float media) recebe apenas o endereço do aluno original — por isso consegue alterá-lo de verdade, e a um custo bem menor de cópia.

Localidade de memória

Um vetor (estático ou dinâmico) ocupa posições contíguas na memória, o que é muito eficiente para o processador. Já uma lista encadeada, formada por nós ligados por ponteiros, pode ter seus elementos espalhados em qualquer lugar do heap.

Essa diferença de organização é uma das razões pelas quais o desempenho real de uma estrutura de dados pode variar mesmo quando duas operações têm a mesma complexidade teórica.

É o caso do vetor turma usado no laboratório de revisão de linguagem C (Material Extra), na Aula 1b e na Aula 3. Tanto faz se ele é estático (Aluno turma[MAX];, na pilha) ou alocado dinamicamente (Aluno *turma = malloc(n * sizeof(Aluno));, no heap): em ambos os casos, o vetor inteiro é reservado de uma vez, então seus elementos ficam lado a lado na memória, em endereços consecutivos:

Aluno turma[3];              // vetor estático, na pilha
Aluno *turma = malloc(3 * sizeof(Aluno)); // vetor dinâmico, no heap

Endereço      Conteúdo
E1000         turma[0]   // sizeof(Aluno) = 60 bytes, por exemplo
E1060         turma[1]   // E1000 + 60
E1120         turma[2]   // E1060 + 60

A única diferença entre as duas versões é onde esse bloco contíguo fica (pilha ou heap) e quem o libera (automático ou free()) — a forma de acessar turma[i] é idêntica nos dois casos, porque em ambos o compilador só precisa somar i * sizeof(Aluno) ao endereço inicial.

Isso é bem diferente do que acontece quando cada elemento é alocado separadamente, um de cada vez, como faríamos ao montar uma lista encadeada — nesse caso, nada garante que os blocos fiquem próximos na memória:

Aluno *a0 = malloc(sizeof(Aluno)); // primeira chamada a malloc()
Aluno *a1 = malloc(sizeof(Aluno)); // segunda chamada a malloc()
Aluno *a2 = malloc(sizeof(Aluno)); // terceira chamada a malloc()

Endereço      Conteúdo
E1000         *a0
E19000        *a1        // bem longe de a0
E8500         *a2        // entre a0 e a1, sem relação fixa

Para "andar" de a0 até a1 não basta somar um deslocamento fixo ao endereço, como no vetor — é preciso guardar explicitamente o endereço do próximo elemento (um ponteiro dentro da struct), que é exatamente a ideia por trás de uma lista encadeada.

Tipagem em C

C é uma linguagem de tipagem estática: o tipo de cada variável é fixado em tempo de compilação e nunca muda durante a execução.

int x = 10;
x = "dez"; // erro de compilação: "x" é (e sempre será) int

Ainda assim, o programador pode forçar conversões entre tipos através de casts, mesmo entre ponteiros de tipos diferentes. É esse recurso que sustenta o uso de void *: um ponteiro genérico, sem tipo definido, que precisa ser convertido (cast) para o tipo correto antes de ser desreferenciado. Foi assim que implementamos imprimirVetor na Aula 3, recebendo qualquer vetor como void *vetor e fazendo o cast correto dentro da função imprimirInt:

void imprimirInt(void *elemento) {
    printf("%d ", *((int *) elemento)); // cast de void * para int *
}

Resumo

Exercícios

1. Explique por que uma função nunca deve retornar um ponteiro para uma variável local (alocada na pilha) dessa mesma função.
2. Considere uma função recursiva sem caso base (ou com um caso base que nunca é alcançado). O que acontece com a pilha de chamadas nesse cenário? Como se chama o erro resultante?
3. Por que variáveis globais não devem ser usadas, mesmo sendo tecnicamente permitidas em C? Dê um cenário concreto em que uma variável global tornaria um bug mais difícil de encontrar.
4. Explique, em termos de bytes copiados, por que void atualizarMedia(Aluno *aluno, float media) é mais barata de chamar do que seria uma versão hipotética Aluno atualizarMedia(Aluno aluno, float media) que recebesse e retornasse o aluno por valor.
5. Por que um vetor de structs tem melhor localidade de memória do que uma coleção de structs alocadas uma a uma, individualmente, com várias chamadas separadas de malloc()?
6. C é uma linguagem de tipagem estática. Isso significa que o compilador sempre impede erros relacionados a tipos? Justifique usando o conceito de cast.
7. Escreva uma função em C, void imprimirFloat(void *elemento), análoga a imprimirInt, capaz de ser usada com a função imprimirVetor vista na Aula 3 para imprimir um vetor de float.
8. Escreva um pequeno trecho de código em C que declare um vetor de 4 posições de double na pilha, e imprima o endereço de cada posição (usando &vetor[i] e printf com %p). O que se espera observar na diferença entre os endereços impressos?

Sugestões de Respostas dos Exercícios

void imprimirFloat(void *elemento) {
    printf("%.2f ", *((float *) elemento)); // cast de void * para float *
}

int main() {
    double vetor[4];
    int i;

    for (i = 0; i < 4; i++) {
        printf("Endereco de vetor[%d]: %p\n", i, (void *) &vetor[i]);
    }

    return 0;
}