Lista de exercícios

Exercícios resolvidos: pilhas, filas e deques

Exercícios progressivos sobre balanceamento de delimitadores, montanha-russa, dança das cadeiras e palíndromos.

Esta lista exercita as políticas de acesso de pilhas, filas e deques. O encadeamento, a alocação e a liberação de nós já foram praticados na aula anterior. Por isso, os exercícios de implementação usam as estruturas fornecidas como código-base.

Não há entrega, nota ou correção individual. Resolva um exercício por vez e consulte sua solução logo depois. Nas soluções, “Resposta esperada” significa apenas uma resposta completa para comparação.

Convenção visual usada em toda a lista

Pilha:

C, B, A

O primeiro elemento escrito é o topo. A leitura é: topo C, segundo B, terceiro A.

Fila:

A, B, C

O primeiro elemento escrito está no início. O último está no final. A leitura é: primeiro A, segundo B, terceiro e último C.

Deque:

A, B, C

O primeiro elemento escrito está no início. O último está no final.

Exercício 1: escolher a estrutura

Classifique cada situação como pilha, fila ou deque:

atender visitantes na ordem de chegada;
desfazer primeiro a alteração mais recente;
inserir e retirar tarefas nas duas extremidades;
verificar uma palavra comparando o primeiro e o último caractere.

Solução

Explicação

A escolha depende da posição usada para inserir e remover. Fila preserva a ordem de chegada. Pilha retorna primeiro o item mais recente. Deque permite acessar os dois extremos.

Resposta esperada

Fila.
Pilha.
Deque.
Deque.

Exercício 2: rastrear uma pilha

As operações são cumulativas. Comece com uma pilha vazia e execute:

insere_Pilha(A)
insere_Pilha(B)
insere_Pilha(C)
remove_Pilha()

Escreva a pilha do topo para a base após cada operação.

Solução

Explicação

Cada inserção cria um novo topo. A remoção atua somente sobre o topo atual.

Resposta esperada

Após inserir A: A
Após inserir B: B, A
Após inserir C: C, B, A
Após remover: B, A

Exercício 3: rastrear uma fila

As operações são cumulativas. Comece com uma fila vazia e execute:

insere_Fila(A)
insere_Fila(B)
insere_Fila(C)
remove_Fila()

Escreva a fila do início para o final após cada operação.

Solução

Explicação

As inserções ocorrem no final. A remoção retira o elemento que está no início.

Resposta esperada

Após inserir A: A
Após inserir B: A, B
Após inserir C: A, B, C
Após remover: B, C

Exercício 4: rastrear um deque

As operações são cumulativas. Comece com um deque vazio e execute:

insere_final_Deque(B)
insere_inicio_Deque(A)
insere_final_Deque(C)
remove_final_Deque()

Escreva o deque do início para o final após cada operação.

Solução

Explicação

O deque permite modificar qualquer uma das extremidades. Cada operação informa explicitamente qual extremidade deve mudar.

Resposta esperada

Após inserir B no final: B
Após inserir A no início: A, B
Após inserir C no final: A, B, C
Após remover do final: A, B

Exercício 5: reconhecer a regra dos parênteses

Este bloco apresenta uma aplicação nova. Para verificar parênteses, percorra a expressão da esquerda para a direita:

ao encontrar (, empilhe esse caractere;
ao encontrar ), desempilhe um (;
se não existir ( para desempilhar, a expressão é inválida;
ao terminar, a pilha precisa estar vazia.

Considere a expressão ((). As aberturas estão nas posições 1 e 2. Ao ler o ) da posição 3, indique qual abertura deve ser removida e justifique pela ordem das aberturas ainda não fechadas.

Solução

Explicação

Depois das duas primeiras posições, a abertura da posição 2 está no topo porque foi a mais recente. O fechamento da posição 3 remove essa abertura. A abertura da posição 1 continua pendente.

Resposta esperada

O ) da posição 3 remove o ( da posição 2, pois essa é a abertura mais recente ainda não fechada. O ( da posição 1 permanece na pilha.

Exercício 6: rastrear parênteses balanceados

Rastreie a expressão (()()). As operações são cumulativas. Depois de cada caractere, registre somente o conteúdo da pilha, do topo para a base.

Solução

Explicação

Cada ( entra no topo. Cada ) retira exatamente um (. Nenhuma remoção ocorre sobre uma pilha vazia.

Resposta esperada

Caractere 1, (: (
Caractere 2, (: (, (
Caractere 3, ): (
Caractere 4, (: (, (
Caractere 5, ): (
Caractere 6, ): vazia

A expressão é válida porque nenhuma remoção falhou e a pilha terminou vazia.

Exercício 7: detectar um fechamento sem abertura

Rastreie ())( somente até ser possível concluir que a expressão é inválida. Indique o caractere que produz o erro.

Solução

Explicação

O primeiro ( entra na pilha. O primeiro ) retira esse elemento. O próximo ) tenta retirar de uma pilha vazia, portanto o restante da expressão não pode corrigir esse erro.

Resposta esperada

Caractere 1, (: (
Caractere 2, ): vazia
Caractere 3, ): erro, não é possível desempilhar uma pilha vazia

O erro ocorre no terceiro caractere, ), porque não existe uma abertura pendente na pilha.

Exercício 8: detectar uma abertura sem fechamento

Rastreie (() até o final e explique por que a expressão é inválida.

Solução

Explicação

As duas aberturas são empilhadas. O único fechamento remove apenas uma delas.

Resposta esperada

Caractere 1, (: (
Caractere 2, (: (, (
Caractere 3, ): (

Ao final, a pilha ainda contém um (. A expressão é inválida porque uma abertura não recebeu fechamento.

Exercício 9: relacionar delimitadores

Agora também serão aceitos colchetes e chaves. Relacione cada abertura ao único fechamento válido:

(    [    {

Solução

Explicação

Um fechamento não pode apenas retirar qualquer abertura. O tipo localizado no topo precisa corresponder ao tipo do fechamento atual.

Resposta esperada

( corresponde a )
[ corresponde a ]
{ corresponde a }

Exercício 10: rastrear delimitadores diferentes

As operações são cumulativas. Rastreie ([{}]) e registre a pilha do topo para a base depois de cada caractere.

Solução

Explicação

As três aberturas entram na pilha. Os fechamentos aparecem na ordem inversa e sempre correspondem ao topo atual.

Resposta esperada

Após (: (
Após [: [, (
Após {: {, [, (
Após }: [, (
Após ]: (
Após ): vazia

A expressão é válida.

Exercício 11: diagnosticar tipos incompatíveis

Analise ([)] e indique o primeiro fechamento incompatível com o topo.

Solução

Explicação

Depois de ( e [, o topo contém [. O caractere seguinte é ), que só poderia fechar (. Retirar [ nesse ponto aceitaria uma estrutura incorreta.

Resposta esperada

O primeiro erro ocorre no terceiro caractere, ). Nesse momento, o topo contém [, mas o fechamento esperado seria ].

Exercício 12: implementar o balanceamento

Implemente expressao_balanceada. A função recebe uma string terminada por \0, ignora caracteres que não sejam delimitadores e devolve 1 somente quando (), [] e {} estiverem corretamente balanceados.

Use PilhaChar como código-base. Teste pelo menos:

(a+b)              válido
([a+b] * {c-d})    válido
([)]               inválido
((a+b)             inválido

Solução

Explicação

A implementação percorre a string uma vez. Aberturas entram na pilha. Um fechamento exige consulta o topo, verifica a correspondência e só então remove. No final, qualquer elemento restante representa uma abertura sem fechamento.

Resposta esperada

A solução deve:

rejeitar fechamento com pilha vazia;
rejeitar tipos incompatíveis;
rejeitar pilha não vazia ao final;
liberar a pilha em todos os caminhos de saída.

Arquivos completos para comparação:

Exercício 13: formar a fila da montanha-russa

Uma montanha-russa possui quatro assentos. Os visitantes chegaram nesta ordem:

Ana, Bruno, Carla, Diego, Eva, Fábio, Gabi, Hugo, Iara

Indique os ponteiros inicio e fim depois que todos entrarem na fila.

Solução

Explicação

O primeiro visitante permanece no início. Cada nova chegada entra depois do final atual.

Resposta esperada

inicio aponta para Ana
fim aponta para Iara
ordem: Ana, Bruno, Carla, Diego, Eva, Fábio, Gabi, Hugo, Iara

Exercício 14: embarcar uma viagem

Use a fila do exercício anterior. Uma viagem embarca até quatro visitantes. Remova os visitantes da primeira viagem e registre a fila restante.

Solução

Explicação

Cada assento ocupado exige uma consulta ao início seguida de uma remoção. A capacidade limita a quatro remoções nesta viagem.

Resposta esperada

Primeira viagem: Ana, Bruno, Carla, Diego
Fila restante: Eva, Fábio, Gabi, Hugo, Iara

Exercício 15: processar todas as viagens

Continue cumulativamente a partir da fila restante. Registre os passageiros da segunda e da terceira viagem.

Solução

Explicação

A segunda viagem ainda ocupa os quatro assentos. Na terceira, a fila fica vazia depois do primeiro embarque, então os três assentos restantes não devem provocar novas remoções.

Resposta esperada

Segunda viagem: Eva, Fábio, Gabi, Hugo
Terceira viagem: Iara
Estado final: fila vazia

Exercício 16: implementar a montanha-russa

Implemente embarca_vagao. A função deve receber a fila, a capacidade do vagão e o número da viagem. Embarque no máximo capacidade visitantes e interrompa antes se a fila ficar vazia.

Depois, use a função até transportar todos os nove visitantes dos exercícios anteriores.

Solução

Explicação

O laço interno representa os assentos de uma viagem. O laço externo inicia uma nova viagem somente enquanto ainda existir alguém na fila. A última viagem não exige tratamento separado.

Resposta esperada

Viagem 1: Ana Bruno Carla Diego
Viagem 2: Eva Fabio Gabi Hugo
Viagem 3: Iara

Arquivos completos para comparação:

Exercício 17: movimentar a dança das cadeiras

Na dança das cadeiras, uma passagem pela frente da fila executa:

consultar o participante do início;
removê-lo do início;
inseri-lo novamente no final.

Comece com Ana, Bruno, Carla, Diego, Eva. Execute duas passagens cumulativas e registre a fila.

Solução

Explicação

Na primeira passagem, Ana sai do início e volta ao final. Na segunda, o mesmo acontece com Bruno. Nenhum participante é eliminado durante essas duas passagens.

Resposta esperada

Após uma passagem: Bruno, Carla, Diego, Eva, Ana
Após duas passagens: Carla, Diego, Eva, Ana, Bruno

Exercício 18: eliminar um participante

Continue a partir de Carla, Diego, Eva, Ana, Bruno. A música parou. Remova o participante do início sem inseri-lo novamente. Indique o eliminado e a fila restante.

Solução

Explicação

A eliminação usa consulta e remoção, mas não realiza a reinserção que representa uma passagem normal da música.

Resposta esperada

Eliminada: Carla
Fila restante: Diego, Eva, Ana, Bruno

Exercício 19: rastrear o jogo completo

As rodadas são cumulativas. Comece novamente com Ana, Bruno, Carla, Diego, Eva. Antes de cada eliminação, execute esta quantidade de passagens:

Rodada 1: 2
Rodada 2: 3
Rodada 3: 1
Rodada 4: 2

Registre a ordem de eliminação e o vencedor.

Solução

Explicação

Cada passagem remove o primeiro participante e o reinsere no final. Depois da quantidade indicada, o participante que estiver no início é removido definitivamente. Cada linha abaixo mostra a fila completa do início para o final.

Resposta esperada

Início: Ana, Bruno, Carla, Diego, Eva

Rodada 1, passagem 1: Bruno, Carla, Diego, Eva, Ana
Rodada 1, passagem 2: Carla, Diego, Eva, Ana, Bruno
Rodada 1, eliminada: Carla
Fila restante: Diego, Eva, Ana, Bruno

Rodada 2, passagem 1: Eva, Ana, Bruno, Diego
Rodada 2, passagem 2: Ana, Bruno, Diego, Eva
Rodada 2, passagem 3: Bruno, Diego, Eva, Ana
Rodada 2, eliminado: Bruno
Fila restante: Diego, Eva, Ana

Rodada 3, passagem 1: Eva, Ana, Diego
Rodada 3, eliminada: Eva
Fila restante: Ana, Diego

Rodada 4, passagem 1: Diego, Ana
Rodada 4, passagem 2: Ana, Diego
Rodada 4, eliminada: Ana
Vencedor: Diego

Exercício 20: implementar a dança das cadeiras

Implemente executa_rodada. A função recebe a fila e a quantidade de passagens. Ela deve movimentar os participantes, eliminar exatamente um participante e preservar a fila dos demais.

O programa termina quando tamanho_Fila(fi) == 1.

Solução

Explicação

Uma passagem combina remoção e reinserção. A eliminação realiza somente a remoção. Separar essas duas ações evita eliminar o participante errado ou diminuir a fila durante a música.

Resposta esperada

A função deve produzir a ordem de eliminação do exercício anterior e manter exatamente um participante ao final.

Arquivos completos para comparação:

Exercício 21: comparar os extremos de um deque

Um palíndromo possui a mesma sequência quando lido do início para o final ou do final para o início. Considere arara armazenada em um deque.

Compare e remova cumulativamente os caracteres das duas extremidades até sobrar no máximo um caractere.

Solução

Explicação

O primeiro par contém a e a. Depois dessas remoções, o próximo par contém r e r. O caractere central não precisa de par.

Resposta esperada

Primeira comparação: a == a
Deque restante: r, a, r
Segunda comparação: r == r
Deque restante: a
Resultado: palíndromo

Exercício 22: detectar um não palíndromo

Repita o procedimento para abelha. Interrompa na primeira diferença e indique os caracteres comparados.

Solução

Explicação

Não é necessário comparar toda a palavra. Uma única diferença entre as extremidades já impede o palíndromo.

Resposta esperada

Na primeira comparação, os dois extremos contêm a, então ambos são removidos. A comparação seguinte encontra b != h. A palavra não é palíndroma.

Exercício 23: implementar o palíndromo

Implemente palavra_palindroma. Considere somente palavras não vazias, formadas por letras minúsculas e sem espaços ou acentos. A função deve usar um deque e interromper na primeira diferença.

Teste arara, radar, abelha e osso.

Solução

Explicação

Todos os caracteres entram pelo final. Enquanto existirem pelo menos dois, a função consulta os dois extremos. Se forem iguais, remove ambos. Se forem diferentes, encerra com falha.

Resposta esperada

arara: palindromo
radar: palindromo
abelha: nao palindromo
osso: palindromo

Arquivos completos para comparação: