13. Filas, pilhas e listas encadeadas¶
Vídeos
31 - Filas e Pilhas (introdução) · 32 - Fila simples · 33 - Pilha simples · 34 - Entendendo a lista encadeada · 35 - Criando uma lista encadeada · 36 - Fila mais eficiente · 37 - Pilha mais eficiente
Fila e pilha "simples", com vector¶
Fila (queue): o primeiro que entra é o primeiro que sai (FIFO — first in, first out). Pilha (stack): o último que entra é o primeiro que sai (LIFO — last in, first out). As duas dão para implementar direto em cima de std::vector:
class FilaSimples {
private:
std::vector<int> dados_;
public:
void enfileira(int valor) {
dados_.push_back(valor); // entra no final
}
int desenfileira() {
int primeiro = dados_.front(); // sai do inicio
dados_.erase(dados_.begin()); // O(n) -- todo mundo desloca uma posicao
return primeiro;
}
bool vazia() const { return dados_.empty(); }
};
class PilhaSimples {
private:
std::vector<int> dados_;
public:
void empilha(int valor) {
dados_.push_back(valor); // entra no final
}
int desempilha() {
int topo = dados_.back();
dados_.pop_back(); // sai do final -- O(1)
return topo;
}
bool vazia() const { return dados_.empty(); }
};
Repare a assimetria: em PilhaSimples, tanto empilhar quanto desempilhar mexem no final do vector — push_back/pop_back são O(1) (tempo constante). Em FilaSimples, desenfileira precisa remover do início (dados_.erase(dados_.begin()), o erase do capítulo 8), o que é O(n): todo elemento restante precisa deslocar uma posição para trás — é o custo que o capítulo 4 desenhou, agora com nome. Para pilha, vector já é uma ótima estrutura interna. Para fila, existe algo melhor — e é aí que entra a lista encadeada.
Entendendo a lista encadeada¶
Uma lista encadeada é uma sequência de nós, cada um guardando um valor e um ponteiro para o próximo nó:
Diferente de vector (um bloco contíguo de memória), os nós de uma lista encadeada podem estar espalhados pela memória, conectados só pelos ponteiros proximo. Isso tem um preço (não dá para pular direto para o elemento 50 como em vector[50] — é preciso percorrer nó por nó) e um ganho: inserir/remover no início é O(1), sem precisar deslocar nada.
Construindo uma lista encadeada (com new)¶
struct No {
int valor;
No* proximo;
No(int v) : valor(v), proximo(nullptr) {}
};
class ListaEncadeada {
private:
No* cabeca_;
public:
ListaEncadeada() : cabeca_(nullptr) {}
void insere_inicio(int valor) {
No* novo = new No(valor); // aloca um no na memoria dinamica
novo->proximo = cabeca_; // o novo no aponta para o antigo primeiro
cabeca_ = novo; // o novo no vira o primeiro
}
void imprime() const {
No* atual = cabeca_;
while (atual != nullptr) {
std::cout << atual->valor << " -> ";
atual = atual->proximo;
}
std::cout << "fim\n";
}
};
insere_inicio roda em O(1): sempre cria um nó e reconecta dois ponteiros, não importa quantos elementos já existem na lista.
O vazamento: o motivo de este capítulo vir depois de RAII¶
Olhe de novo para ListaEncadeada: ela chama new No(valor) toda vez que insere_inicio roda. Não existe destrutor. Quando um objeto ListaEncadeada sai de escopo, o campo cabeca_ (um ponteiro) é simplesmente descartado — mas cada No que foi alocado com new continua vivo na memória, sem ninguém mais apontando para ele, e sem jamais ser liberado. Isso é um vazamento de memória: em um programa de vida curta talvez nunca doa; em um programa de longa duração (exatamente o que um sistema embarcado costuma ser — capítulo 14), cada inserção que nunca é destruída consome memória que nunca mais volta, até o programa travar por falta de RAM.
Você pode confirmar isso na prática rodando o programa sob uma ferramenta como AddressSanitizer ou Valgrind — ambas reportam exatamente essa lista de nós como "memória alocada e nunca liberada" quando o programa termina.
Corrigindo com destrutor (aplicando o capítulo 10)¶
A correção segue diretamente o que você aprendeu no capítulo anterior: todo new precisa de um delete correspondente, e o lugar certo para isso é o destrutor.
class ListaEncadeada {
private:
No* cabeca_;
public:
ListaEncadeada() : cabeca_(nullptr) {}
~ListaEncadeada() {
No* atual = cabeca_;
while (atual != nullptr) {
No* proximo = atual->proximo; // guarda o proximo ANTES de destruir o atual
delete atual;
atual = proximo;
}
}
void insere_inicio(int valor) {
No* novo = new No(valor);
novo->proximo = cabeca_;
cabeca_ = novo;
}
};
Agora, quando um ListaEncadeada sai de escopo, o destrutor percorre todos os nós, um por um, dando delete em cada um antes de avançar. A ordem importa: se você desse delete atual e só depois lesse atual->proximo, estaria lendo memória já liberada — por isso o próximo nó é guardado numa variável (proximo) antes do delete.
Só que essa ListaEncadeada, do jeito que está, ainda tem o mesmo problema de cópia rasa do capítulo 10: copiar um ListaEncadeada copia só o ponteiro cabeca_, não os nós — dois objetos apontando para a mesma cadeia, e double free garantido quando ambos saem de escopo. A correção completa exigiria também construtor de cópia e operador de atribuição customizados (a regra dos 3 completa) — fora do escopo deste curso, mas bom saber que existe.
Fila e pilha eficientes, com lista encadeada¶
Com o nó e o destrutor entendidos, dá para reescrever a fila de um jeito O(1) em toda operação, guardando ponteiros para o início e o fim da lista:
class FilaEficiente {
private:
No* inicio_;
No* fim_;
public:
FilaEficiente() : inicio_(nullptr), fim_(nullptr) {}
~FilaEficiente() {
No* atual = inicio_;
while (atual != nullptr) {
No* proximo = atual->proximo;
delete atual;
atual = proximo;
}
}
void enfileira(int valor) {
No* novo = new No(valor);
if (fim_ == nullptr) {
inicio_ = fim_ = novo; // fila estava vazia
} else {
fim_->proximo = novo;
fim_ = novo;
}
}
int desenfileira() {
int valor = inicio_->valor;
No* antigo_inicio = inicio_;
inicio_ = inicio_->proximo;
if (inicio_ == nullptr) fim_ = nullptr; // ficou vazia
delete antigo_inicio;
return valor;
}
bool vazia() const { return inicio_ == nullptr; }
};
enfileira e desenfileira agora são O(1): nenhuma das duas operações precisa percorrer a lista inteira, diferente de FilaSimples::desenfileira (baseada em vector::erase(begin())).
A pilha eficiente é ainda mais direta: empilhar/desempilhar sempre no cabeca_ (início), reaproveitando insere_inicio/uma remoção do início — sem precisar de ponteiro para o fim.
Qual usar na prática?¶
Em código C++ de produção, você quase nunca escreve fila/pilha do zero — usa std::queue/std::stack (adaptadores da STL, por cima de vector/deque) ou, quando o problema pede mesmo uma lista encadeada, std::list/std::forward_list, todas já corretas quanto a RAII e cópia. O valor deste capítulo não é "memorizar como implementar lista encadeada" — é entender, na carne, o que essas estruturas prontas estão fazendo por baixo, e por que RAII (capítulo anterior) não é um detalhe acadêmico: é o que separa um programa que funciona de um que vaza memória silenciosamente até travar.
Erros comuns¶
Segmentation fault ao ler atual->proximo depois de já ter dado delete atual — sempre guarde o próximo nó antes de destruir o atual, como no destrutor acima.
Esquecer de atualizar fim_ para nullptr quando a fila fica vazia — se desenfileira remove o último nó e você não zera fim_, a próxima chamada a enfileira vai tentar fim_->proximo = novo com fim_ apontando para memória já liberada.
Vazamento silencioso (sem crash, só uso de memória crescendo) — sintoma clássico de new sem delete correspondente em algum caminho do código. Ferramentas como AddressSanitizer (-fsanitize=address na compilação) ou Valgrind detectam isso automaticamente — vale rodar em qualquer estrutura de dados que você escrever com ponteiros manuais.
Resumo¶
- Fila (FIFO) e pilha (LIFO) dão para implementar em cima de
vector, mas fila fica O(n) por operação por causa da remoção no início. - Lista encadeada: nós conectados por ponteiro
proximo, permite inserção/remoção em O(1) nas pontas, ao custo de não ter acesso direto por índice. - Toda estrutura que usa
newprecisa de destrutor que percorre e libera todos os nós — sem isso, é vazamento de memória garantido a cada uso. - Guarde o próximo nó antes de destruir o atual, no laço de liberação.
- Fila/pilha eficientes (O(1) em toda operação) usam lista encadeada, guardando ponteiros de início (e, para fila, também fim).
- Na prática, prefira
std::queue/std::stack/std::listda STL — já resolvem RAII e cópia corretamente.