Lista 12 · Filas, pilhas e listas encadeadas¶
Exercícios da Semana 12 — Filas, pilhas e listas encadeadas. Nos exercícios com new/delete (3 a 5), o No já vem com um contador estático de "nós vivos" — se o seu destrutor esquecer de liberar algum nó, o teste detecta o vazamento automaticamente, porque o contador não volta a zero.
Como resolver
Copie o bloco de código de cada exercício, cole no seu compilador online, preencha a parte marcada como ESCREVA SUA SOLUCAO AQUI e rode. A saída mostra quais testes passaram.
ex01¶
Complete a classe PilhaComVector (campo privado dados_, std::vector<int>, já declarado). Implemente empilha(int valor), desempilha() (remove e retorna o topo — assuma que a pilha não está vazia), topo() const e vazia() const.
PilhaComVector p;
p.empilha(1);
p.empilha(2);
p.empilha(3);
p.desempilha(); // -> 3
p.topo(); // -> 2
// ex01 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
#include <vector>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX01_H
#define EX01_H
class PilhaComVector {
private:
std::vector<int> dados_;
public:
void empilha(int valor);
int desempilha();
int topo() const;
bool vazia() const;
};
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void PilhaComVector::empilha(int valor) {
// TODO: adicione "valor" ao final de dados_.
}
int PilhaComVector::desempilha() {
// TODO: guarde dados_.back(), remova com pop_back(), retorne o valor guardado.
return 0;
}
int PilhaComVector::topo() const {
// TODO: retorne dados_.back().
return 0;
}
bool PilhaComVector::vazia() const {
// TODO: retorne dados_.empty().
return true;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
PilhaComVector p;
assert(p.vazia());
p.empilha(1);
p.empilha(2);
p.empilha(3);
assert(!(p.vazia()));
assert(p.desempilha() == 3);
assert(p.topo() == 2);
assert(p.desempilha() == 2);
assert(p.desempilha() == 1);
assert(p.vazia());
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex02¶
Complete a classe FilaComVector (campo privado dados_, std::vector<int>, já declarado). Implemente enfileira(int valor), desenfileira() (remove e retorna o primeiro elemento — assuma que a fila não está vazia) e vazia() const.
FilaComVector f;
f.enfileira(1);
f.enfileira(2);
f.enfileira(3);
f.desenfileira(); // -> 1
f.desenfileira(); // -> 2
// ex02 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
#include <vector>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX02_H
#define EX02_H
class FilaComVector {
private:
std::vector<int> dados_;
public:
void enfileira(int valor);
int desenfileira();
bool vazia() const;
};
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void FilaComVector::enfileira(int valor) {
// TODO: adicione "valor" ao final de dados_.
}
int FilaComVector::desenfileira() {
// TODO: guarde dados_.front(), remova com dados_.erase(dados_.begin()),
// retorne o valor guardado.
return 0;
}
bool FilaComVector::vazia() const {
// TODO: retorne dados_.empty().
return true;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
FilaComVector f;
assert(f.vazia());
f.enfileira(1);
f.enfileira(2);
f.enfileira(3);
assert(!(f.vazia()));
assert(f.desenfileira() == 1);
assert(f.desenfileira() == 2);
assert(f.desenfileira() == 3);
assert(f.vazia());
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex03¶
Complete a classe ListaEncadeada (a struct No já está pronta — inclusive com um contador estático No::total_vivos, que sobe a cada No construído e desce a cada No destruído; é assim que o teste consegue detectar vazamento).
Implemente insere_fim(int valor) e ~ListaEncadeada().
insere_fim é o oposto do que o capítulo mostrou. Inserir no início é barato: o nó novo aponta para a cabeça e vira a nova cabeça, e pronto — três linhas, sem laço. Inserir no fim exige percorrer a lista inteira até achar o último nó (aquele cujo proximo é nullptr) para só então pendurar o nó novo nele. E há um caso especial: se a lista estiver vazia, não existe último nó, e o nó novo vira a própria cabeça.
O destrutor percorre e dá delete em todos os nós — lembrando de guardar o próximo nó antes de destruir o atual, porque depois do delete o campo proximo não existe mais.
tamanho() e em(int indice) já vêm prontos no .h: são eles que o teste usa para conferir a ordem.
{
ListaEncadeada l;
l.insere_fim(1);
l.insere_fim(2);
l.insere_fim(3);
l.tamanho(); // -> 3
l.em(0); // -> 1 (o primeiro inserido continua na frente)
} // l sai de escopo aqui -- ~ListaEncadeada() deve liberar os 3 nos
// No::total_vivos deve voltar a 0 depois disso
// ex03 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX03_H
#define EX03_H
struct No {
static inline int total_vivos = 0;
int valor;
No* proximo;
No(int v) : valor(v), proximo(nullptr) { total_vivos++; }
~No() { total_vivos--; }
};
class ListaEncadeada {
private:
No* cabeca_;
public:
ListaEncadeada() : cabeca_(nullptr) {}
~ListaEncadeada();
void insere_fim(int valor);
int tamanho() const {
int contagem = 0;
No* atual = cabeca_;
while (atual != nullptr) {
contagem++;
atual = atual->proximo;
}
return contagem;
}
// Valor guardado na posicao indice (0 e o primeiro no).
// Assume que o indice existe.
int em(int indice) const {
No* atual = cabeca_;
for (int i = 0; i < indice; i++) {
atual = atual->proximo;
}
return atual->valor;
}
};
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
ListaEncadeada::~ListaEncadeada() {
// TODO: percorra a lista a partir de cabeca_, guardando o proximo no
// ANTES de dar delete no atual, ate atual virar nullptr.
}
void ListaEncadeada::insere_fim(int valor) {
// TODO: crie um novo No(valor) com "new".
// Se cabeca_ for nullptr, a lista esta vazia: o novo no vira a cabeca.
// Senao, ande com um ponteiro auxiliar ate o no cujo proximo e nullptr
// (o ultimo) e faca o proximo dele apontar para o novo no.
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
No::total_vivos = 0;
{
ListaEncadeada l;
assert(l.tamanho() == 0);
// primeira insercao: a lista esta vazia, o no novo vira a cabeca
l.insere_fim(1);
assert(l.tamanho() == 1);
assert(l.em(0) == 1);
l.insere_fim(2);
l.insere_fim(3);
assert(l.tamanho() == 3);
assert(No::total_vivos == 3);
// a ordem e a de insercao: quem entrou primeiro fica na frente
assert(l.em(0) == 1);
assert(l.em(1) == 2);
assert(l.em(2) == 3);
}
assert(No::total_vivos == 0);
// lista que nunca recebeu nada: o destrutor nao pode estourar
{
ListaEncadeada vazia;
assert(vazia.tamanho() == 0);
}
assert(No::total_vivos == 0);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex04¶
Complete a classe ListaEncadeada implementando remove(int valor), que remove a primeira ocorrência do valor e devolve true; se o valor não estiver na lista, não altera nada e devolve false.
Tudo o mais já está pronto no .h — construtor, destrutor, insere_fim, tamanho() e em(). O exercício é só a remoção, porque é aqui que a lista encadeada cobra o preço dela.
Remover um nó é religar o ponteiro do nó anterior: se anterior->proximo aponta para o nó que sai, ele passa a apontar para no_que_sai->proximo, e só depois disso o nó é destruído com delete. Duas coisas a cuidar:
- O primeiro nó não tem anterior. Quando o valor procurado está na cabeça, quem muda é
cabeca_, e não oproximode ninguém. É umifseparado, antes do laço. - Guarde o ponteiro antes de religar. Depois de
anterior->proximo = atual->proximo, ninguém mais aponta paraatual: se você não tiver guardado o endereço dele numa variável, o nó fica perdido na memória, vivo para sempre. O contadorNo::total_vivosdo teste existe para pegar exatamente esse vazamento.
ListaEncadeada l;
l.insere_fim(1);
l.insere_fim(2);
l.insere_fim(3);
l.remove(2); // -> true; a lista vira {1, 3}
l.remove(99); // -> false; nada muda
l.remove(1); // -> true; removeu a cabeca, a lista vira {3}
// ex04 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX04_H
#define EX04_H
struct No {
static inline int total_vivos = 0;
int valor;
No* proximo;
No(int v) : valor(v), proximo(nullptr) { total_vivos++; }
~No() { total_vivos--; }
};
class ListaEncadeada {
private:
No* cabeca_;
public:
ListaEncadeada() : cabeca_(nullptr) {}
~ListaEncadeada() {
No* atual = cabeca_;
while (atual != nullptr) {
No* proximo = atual->proximo;
delete atual;
atual = proximo;
}
}
void insere_fim(int valor) {
No* novo = new No(valor);
if (cabeca_ == nullptr) {
cabeca_ = novo;
return;
}
No* ultimo = cabeca_;
while (ultimo->proximo != nullptr) {
ultimo = ultimo->proximo;
}
ultimo->proximo = novo;
}
int tamanho() const {
int contagem = 0;
No* atual = cabeca_;
while (atual != nullptr) {
contagem++;
atual = atual->proximo;
}
return contagem;
}
int em(int indice) const {
No* atual = cabeca_;
for (int i = 0; i < indice; i++) {
atual = atual->proximo;
}
return atual->valor;
}
// O exercicio e este.
bool remove(int valor);
};
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool ListaEncadeada::remove(int valor) {
// TODO:
// 1. lista vazia (cabeca_ == nullptr): nao ha o que remover, devolva false.
// 2. o valor esta na cabeca: guarde o no antigo numa variavel, avance
// cabeca_ para cabeca_->proximo, de delete no no antigo, devolva true.
// 3. senao, ande com "anterior" enquanto anterior->proximo nao for nullptr:
// se anterior->proximo->valor for o alvo, guarde esse no, religue
// anterior->proximo para no->proximo, de delete no no e devolva true.
// 4. chegou ao fim sem achar: devolva false.
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
No::total_vivos = 0;
{
ListaEncadeada l;
// remover de uma lista vazia nao estoura e devolve false
assert(!(l.remove(1)));
l.insere_fim(1);
l.insere_fim(2);
l.insere_fim(3);
assert(No::total_vivos == 3);
// do meio: religa o proximo do anterior
assert(l.remove(2));
assert(l.tamanho() == 2);
assert(l.em(0) == 1);
assert(l.em(1) == 3);
assert(No::total_vivos == 2); // pega o no perdido sem delete
// valor que nao existe: nada muda
assert(!(l.remove(99)));
assert(l.tamanho() == 2);
assert(No::total_vivos == 2);
// da cabeca: quem muda e cabeca_, nao o proximo de ninguem
assert(l.remove(1));
assert(l.tamanho() == 1);
assert(l.em(0) == 3);
// o ultimo elemento, que deixa a lista vazia
assert(l.remove(3));
assert(l.tamanho() == 0);
assert(No::total_vivos == 0);
assert(!(l.remove(3)));
}
assert(No::total_vivos == 0);
// apenas a PRIMEIRA ocorrencia sai
No::total_vivos = 0;
{
ListaEncadeada l;
l.insere_fim(7);
l.insere_fim(4);
l.insere_fim(7);
assert(l.remove(7));
assert(l.tamanho() == 2);
assert(l.em(0) == 4);
assert(l.em(1) == 7);
}
assert(No::total_vivos == 0);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex05¶
Complete a classe PilhaEficiente, implementada com lista encadeada (empilhar e desempilhar sempre pelo início — não precisa de ponteiro para o fim). Implemente empilha(int valor), desempilha() (assuma que a pilha não está vazia), vazia() const e ~PilhaEficiente().
PilhaEficiente p;
p.empilha(1);
p.empilha(2);
p.empilha(3);
p.desempilha(); // -> 3
p.desempilha(); // -> 2
// ex05 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX05_H
#define EX05_H
struct No {
static inline int total_vivos = 0;
int valor;
No* proximo;
No(int v) : valor(v), proximo(nullptr) { total_vivos++; }
~No() { total_vivos--; }
};
class PilhaEficiente {
private:
No* cabeca_;
public:
PilhaEficiente() : cabeca_(nullptr) {}
~PilhaEficiente();
void empilha(int valor);
int desempilha();
bool vazia() const;
};
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
PilhaEficiente::~PilhaEficiente() {
// TODO: percorra a partir de cabeca_, guardando o proximo no ANTES de
// dar delete no atual, ate atual virar nullptr.
}
void PilhaEficiente::empilha(int valor) {
// TODO: crie um No(valor) com "new", conecte o proximo dele a cabeca_
// atual, e atualize cabeca_ para o novo no.
}
int PilhaEficiente::desempilha() {
// TODO: guarde cabeca_->valor, avance cabeca_ para cabeca_->proximo,
// de delete no no antigo, e retorne o valor guardado.
return 0;
}
bool PilhaEficiente::vazia() const {
// TODO: retorne true se cabeca_ for nullptr.
return true;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
No::total_vivos = 0;
{
PilhaEficiente p;
assert(p.vazia());
p.empilha(1);
p.empilha(2);
p.empilha(3);
assert(!(p.vazia()));
assert(p.desempilha() == 3);
assert(p.desempilha() == 2);
assert(No::total_vivos == 1);
assert(p.desempilha() == 1);
assert(p.vazia());
}
assert(No::total_vivos == 0);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex06¶
Escreva parenteses_balanceados, que devolve true se os parênteses do texto estiverem corretamente casados. Caracteres que não são parênteses devem ser ignorados.
Este é o exercício clássico de pilha, e vale entender por quê: ao encontrar um (, empilhe; ao encontrar um ), desempilhe o ( correspondente. Duas coisas tornam o texto inválido — um ) chegando com a pilha vazia, e a pilha não estar vazia no fim.
Repare que o caso ")(" é o que separa a solução com pilha de uma que apenas conta os parênteses: a contagem bate, e mesmo assim o texto está errado.
parenteses_balanceados("((a) + (b))") // -> true
parenteses_balanceados("(a + b") // -> false
parenteses_balanceados(")(") // -> false
// ex06 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
#include <string>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX06_H
#define EX06_H
// Retorna true se os parenteses do texto estiverem balanceados:
// cada "(" tem um ")" correspondente, e nenhum ")" aparece sem par antes.
bool parenteses_balanceados(const std::string& texto);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool parenteses_balanceados(const std::string& texto) {
// TODO: use um vector<char> como pilha. Ao ver "(", empilhe.
// Ao ver ")", desempilhe -- e se a pilha estiver VAZIA nessa hora,
// ja pode devolver false. No fim, a pilha precisa estar vazia.
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(parenteses_balanceados("(a + b)"));
assert(parenteses_balanceados("((a) + (b))"));
assert(parenteses_balanceados("sem parenteses"));
assert(parenteses_balanceados(""));
assert(!(parenteses_balanceados("(a + b")));
assert(!(parenteses_balanceados("a + b)")));
assert(!(parenteses_balanceados(")(")));
assert(!(parenteses_balanceados("((a)")));
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex07¶
Complete a classe PilhaDeAcoes — o "desfazer" de um editor, feito com lista encadeada. A struct No, com o contador No::total_vivos, já está pronta. Implemente empilha(const std::string& acao), desfaz() (remove e devolve a ação do topo — assuma que a pilha não está vazia) e ~PilhaDeAcoes().
O contador total_vivos existe para o teste conferir que nenhum nó ficou para trás: depois que a pilha é destruída, ele precisa voltar a zero. É o destrutor que garante isso.
PilhaDeAcoes p;
p.empilha("digitar");
p.empilha("colar");
p.desfaz(); // -> "colar"
p.desfaz(); // -> "digitar"
// ex07 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.
#include <cassert>
#include <iostream>
#include <string>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX07_H
#define EX07_H
struct No {
static inline int total_vivos = 0;
std::string acao;
No* proximo;
No(std::string a) : acao(a), proximo(nullptr) { total_vivos++; }
~No() { total_vivos--; }
};
class PilhaDeAcoes {
private:
No* cabeca_;
public:
PilhaDeAcoes() : cabeca_(nullptr) {}
~PilhaDeAcoes();
void empilha(const std::string& acao);
std::string desfaz();
};
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
PilhaDeAcoes::~PilhaDeAcoes() {
// TODO: percorra a partir de cabeca_, guardando o proximo no ANTES de
// dar delete no atual, ate atual virar nullptr.
}
void PilhaDeAcoes::empilha(const std::string& acao) {
// TODO: crie um No(acao) com "new", conecte-o ao inicio da lista
// (igual insere_inicio da lista encadeada do capitulo 12).
}
std::string PilhaDeAcoes::desfaz() {
// TODO: guarde cabeca_->acao, avance cabeca_, de delete no no antigo,
// retorne o valor guardado.
return "";
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
No::total_vivos = 0;
{
PilhaDeAcoes p;
p.empilha("digitar");
p.empilha("colar");
p.empilha("apagar");
assert(No::total_vivos == 3);
assert(p.desfaz() == std::string("apagar"));
assert(p.desfaz() == std::string("colar"));
assert(No::total_vivos == 1);
assert(p.desfaz() == std::string("digitar"));
}
assert(No::total_vivos == 0);
std::cout << "Todos os testes passaram!\n";
return 0;
}